HMMT 十一月 2015 · 冲刺赛 · 第 13 题

HMMT November 2015 — Guts Round — Problem 13

[ 9 ] Consider a 4 × 4 grid of squares, each of which are originally colored red. Every minute, Piet can jump on one of the squares, changing the color of it and any adjacent squares (two squares are adjacent if they share a side) to blue. What is the minimum number of minutes it will take Piet to change the entire grid to blue?

解析

[ 9 ] Consider a 4 × 4 grid of squares, each of which are originally colored red. Every minute, Piet can jump on one of the squares, changing the color of it and any adjacent squares (two squares are adjacent if they share a side) to blue. What is the minimum number of minutes it will take Piet to change the entire grid to blue? Proposed by: Alexander Katz Answer: 4 Piet can change the colors of at most 5 squares per minute, so as there are 16 squares, it will take him at least four minutes to change the colors of every square. Some experimentation yields that it is indeed possible to make the entire grid blue after 4 minutes; one example is shown below: X X X X Here, jumping on the squares marked with an X provides the desired all-blue grid.