Chessboard Greatness

Logic Level 5

Consider a 8 × 8 8 \times 8 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.


The answer is 20.

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.

2 solutions

Alan Yan
Aug 23, 2015

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 20 20 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 20 \boxed{20} .

(A valid tiling is shown in the picture)

(Source: David Arthur)

The diagonal tiles are adjacent, aren't they?

Joseph Ponce - 5 years, 9 months ago

Log in to reply

No...................diagonal tiles are not adjacent.

Alan Yan - 5 years, 9 months ago

Log in to reply

I googled the definition of adjacent in the context of grids. The definitions are not uniform. Some say the diagonals are included as adjacent, some don't. So i believe it should have been specified in the problem.

Joseph Ponce - 5 years, 9 months ago
Adam Donadille
Nov 20, 2018

I find it by thinking of the chessboard tiles with their color since tokens positionned on a black tile will only make white tiles "shining" and vice versa so that I only have to consider one half of the chessboard, ie. only white tiles for example.

Because there are 32 tiles and every token can take 4 of them the minimum number of tokens required is 32/4 = 8. It is impossible to have only 8 tokens because the 2 corner tiles will make 2 tokens covering only 3 tiles instead of 4 and by going step by step or by doing a very long and boring reasoning (which i didn't do) we can also see that more than 2 others tokens will be only covering 3 tiles and thus using 9 tiles is impossible. But it is pretty easy to do it with 10 tokens and there are several ways to do it.

Finally we need to cover 2 times 32 tiles and therefore we need 10x2 = 20 tokens minimum to make the chessboard "brilliant".

💖brilliant

Yoshihiro Iida - 2 months, 1 week ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...