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.

Get help from others!

Recent Answers

- Lex on Does Google Analytics track 404 page responses as valid page views?
- haakon.io on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP