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

Home > Just Math
Marked squares (Posted on 2014-12-24) Difficulty: 3 of 5
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 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.b
b.bMb.
Mb.bMb
bMb.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.b
b.bMb.
Mb.b.b
b.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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information