All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Marked squares (Posted on 2014-12-24)
Consider a n by n square board, where n is a fixed even positive integer. The board is divided into n^2 unit squares. We say that two different squares on the board are adjacent if they have a common side.
M unit squares on the board are marked in such a way that every square (marked or unmarked) on the board is adjacent to at least one marked square.

Determine the smallest possible value of M.

Source: IMO 1999

 See The Solution Submitted by Ady TZIDON No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 Solution Comment 1 of 1
Split the squares on the board into two groups by checkerboard parity, call then white and black.  Every white square must be adjacent to a marked black square and similarly every black square must be adjacent to a marked white square.

By symmetry any pattern which minimizes the number of marked white squares will also minimize the number of marked black squares.  So determining which white squares need to be marked and doubling the result will yield the answer.

Mark alternating white diagonals parallel to the longest black diagonal (example: n=6, NW-SE orientation):
`bMb.bM.bMb.bb.bMb.Mb.bMbbMb.bM.bMb.b`
Every black tile is adjacent to at least one marked tile.  For any even n there are 1 + 3 + ... + (n-1) = (n/2)^2 white marked tiles.

But an improvement can be made; notice that other than on the edges every black tile is adjacent to two marked tiles.  Almost half of those tiles can be unmarked.  Specifically for a marked diagonal with 2k+1 tiles, k of them can be unmarked.
`bMb.bM.b.b.bb.bMb.Mb.b.bb.b.bM.bMb.b`
Every black tile is adjacent to exactly one marked white tile.  Now there are only 1 + 2 + ... + (n/2) = (n/2)*(n/2+1)/2 = (n^2+2n)/8 marked white tiles.  Marking the black tiles similarly makes a total number of marked tiles equal to (n^2+2n)/4 = M.

 Posted by Brian Smith on 2016-02-26 12:30:01

 Search: Search body:
Forums (0)
Random Problem
Site Statistics
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox: