Problem 42619. Flip the right coin to survive!

It suffices to convey 6 bits of information to determine the magic key on a 8*8 chessboard. However, different bit mapping/coding schemes require different coins to be flipped. Under different coding schemes, it is possible to identify the magic key by flipping a coin different from the one specified in your test suite. Thus, it is not a good idea to check the index of the flipped coin.

Peng, there is one and onyly one index for the flipping coin given the chessboard and the magic key. Therefore the problem is valid. Cheers.

Hi, Omer, thanks for submitting this interesting problem to Cody, which makes Cody an interesting game. But I am sure you are missing some important thing here, i.e., the coding/decoding rule to convey the 6 bits of information is not unique, and consequently, the flipping coin which is determined by the coding rule is not unique either. To elaborate on this, let’s consider the simplest 1*2 chessboard example. There are a total of 4 possible initial coin states on the 1*2 chessboard: HH, HT, TT, TH, where H stands for “head” and T stands for “tail”. The warden may choose either coin as the magic key. Now here comes the first possible coding/decoding rule which is predetermined and agreed by the two prisoners. If the 1st coin is the magic key, the first prisoner always flips one coin such that the 1st coin shows H. If the 2nd coin is the magic key, the first prisoner always flips one coin such that the 1st coin shows T. This is the coding rule applied by the first prisoner. The decoding rule applied by the second prisoner is like this: whenever the second prisoner sees H on the 1st coin, he declares the 1st coin as the magic key; whenever he sees T on the 1st coin, he declares the 2nd coin as the magic key. For simplicity of explanation, suppose that the first coin is chosen by the warden as the magic key. Then under the above coding rule, the flipping coins corresponding to the 4 initial states HH, HT, TH, TT are 2, 2, 1, 1, respectively. Now, let’s consider a different coding/decoding rule predetermined by the prisoners. The coding procedure works as follows: If the 1st coin is the magic key, the first prisoner always flips one coin such that the 1st coin shows T (not H). If the 2nd coin is the magic key, the first prisoner always flips one coin such that the 1st coin shows H (not T). The decoding rule also needs to be updated: whenever the second prisoner sees T (not H) on the 1st coin, he declares the 1st coin as the magic key; whenever he sees H (not T) on the 1st coin, he declares the 2nd coin as the magic key. Under this set of rule, again consider that the first coin is chosen as the magic key. Then the flipping coins corresponding to the 4 initial states HH, HT, TH, TT are 1, 1, 2, 2, respectively. Obviously, we see different flipping coins corresponding to the above two different coding/decoding methods. The 8*8 chessboard is just a generalization of the above simple 1*2 example; thus, it has many more different coding/decoding rules which correspond to different flipping coins.