# Which theorems and definitions do I need to know to prove the impossible chessboard puzzle has a solution for every number of squares?

Mathematics Asked by bob_the_fat on September 4, 2020

I saw this problem on the youtube channel called 3blue1brown.

The problem is the following:

There is a 8 x 8 chessboard, two prisoners (Prisoner 1 and prisoner 2), a key and a warden. Each of the squares has a coin on top of it.
The warden turn over the coins to be heads or tails according to whichever pattern he would like and puts the key inside one of the chessboard’s squares. Prisoner 1 sees where the key is while prisoner 2 cannot.

The goal of prisoner 1 is to get prisoner 2 to also know where the key is and then both of them can be free afterwards.

But the only thing which is allowed to do for prisoner 1, is turning over one and only one coin(but he may not) then he leaves the room and prisoner 2 comes in. Prisoner 2 have to know where the key is by just looking at the chessboard. Of course they can make a plan beforehand.

In that video , owner of the channel presented a proof asserts that if the number of squares isn’t in the form of $$2^n$$ there is no exact solution . But when I investigated the 3 square case I found a solution but I don’t know how to generalize this to a arbitrary number of squares so my question is what definitions and theorems or observations I need to know and notice to prove that the following method can be used for any number of squares? And if there is other ways of solve this I would love to receive some hints and again definitions, theorems needed to solve it.

First , let’s represent the chessboard as an squence of numbers. If a square has a tails on it then it is 1 otherwise it is 0. Prisoners can start writing the squence starting from top left corner and after finishing every row they can continue from bottom leftmost square than repeat.

I created three sets A, B and C containing these sequences like so,

A = {111 , 000}

B = {110 , 001}

C = {101 , 100 ,010, 011}

Now I’m going to use an array to represent the solution for every possible case.

$$begin{array}{c|lcr} text{Case} & text{First} & text{Second} & text{Third} \ hline 000 & 000 & 001 & 010 \ 001 & 000 & 001 & 011 \ 010 & 000 & 110 & 011 \ 011 & 111 & 001 & 011 \ 100 & 000 & 110 & 101 \ 101 & 111 & 001 & 101 \ 110 & 111 & 110 & 100 \ 111 & 111 & 110 & 101 end{array}$$

If prisoner 1 sees that the squence is ,for example, 110 and the key is in the first square he just needs to find corresponding solution from the array(of course both of them need to memorize it) and flips the necessary coin or not if he doesn’t need to flip. And then prisoner 2 convert the chessboard to the squence ,sees the message and immediately knows where the key is prisoner 2 cannot.