Consider a grid. Several of the tiles have tokens on them and there can only be one token on any tile. Call any tile "brilliant" if there exists an adjacent tile with a token on it.
What is the minimum number of tokens needed so that all tiles of the chessboard are brilliant?
Note: 2 tiles are adjacent if they share a common side. Tiles that only share a common corner are not considered adjacent.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Tile the chessboard as shown such that every region has two "central squares". The central square can only become "brilliant" by being next to the other central square or other tiles from its region. Additionally, each non-central square is next to exactly one central square.
(The boundary of the regions are slightly more bolded)
As you can see there are ten regions and each region as two tokens, therefore 2 0 tokens is a valid number. Now we must prove there can be no less.
For the sake of contradiction, assume there is less than one token in a region. WLOG let's say there is only one token.
If this token is on a central square, then that square cannot be brilliant since no one else from its region has a token.
If this token is on a non-central square, only one of the central squares will become brilliant, and the other one would be not brilliant.
Therefore there must be at least two tokens in each region leading to the least number of tokens to be 2 0 .
(A valid tiling is shown in the picture)
(Source: David Arthur)