## Eight by eight matrix, flip a coin.

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

mathocean149
Posts: 2
Joined: Fri Dec 25, 2015 8:13 am UTC

### Eight by eight matrix, flip a coin.

Say we have an eight by eight matrix, and each entry has a coin, heads or tails, determined by Randall Monroe. Randall Monroe points at a coin he deems "worthy." Then, we must flip exactly 1 coin. A partner with whom I have conspired with before must be able to tell which coin is "worthy." Is this possible or not?

emlightened
Posts: 42
Joined: Sat Sep 26, 2015 9:35 pm UTC
Location: Somewhere cosy.

### Re: Eight by eight matrix, flip a coin.

So there's an 8x8 matrix of values, heads or tails, and you can look at the entire matrix before Randall selects a coin and flips it over. Can't you just memorise the entire matrix, tell it to your partner, and leave them to determine which coin was flipped? If not, then they can't know any prior knowledge about the matrix, just what methods could be used. None, as it happens, as if this isn't a lateral thinking problem, you're partner's just looking at a 8x8 array of coins, with no idea which to turn.

For instance, all of the coins could be heads, except for the one Randall deems worthy, which is then also flipped to be heads. your partner now has to pick the worthy coin from 64 heads, with nothing to distinguish between them. Either it's impossible, a memory task, requires lateral thinking, or I've misunderstood the problem.

"Therefore it is in the interests not only of public safety but also public sanity if the buttered toast on cats idea is scrapped, to be replaced by a monorail powered by cats smeared with chicken tikka masala floating above a rail made from white shag pile carpet."

curiosityspoon
Posts: 35
Joined: Wed Sep 24, 2014 5:01 pm UTC

### Re: Eight by eight matrix, flip a coin.

Randall sets the initial array of heads and tails and selects a coin, then based on that choice, you select any coin (not necessarily the same one) and flip it over, then the partner (who has not looked at the initial array of coins, and has not communicated with you since you were first able to see it) gets to look at the array as it exists after you flipped a coin over. From that information, the partner has to determine which coin is the one Randall chose.

Spoiler:
A success rate of at least 64/67 is definitely possible: treat the array not as a square, but as a linear string of 64 binary digits. The numbers 2^0, 2^1, ... , 2^63 all fall into different residue classes mod-67, so flipping each individual bit to add or subtract the appropriate power of 2 will result in a different value for the mod-67 of the overall number, and if the starting array is all tails for 00000, the only values that cannot be reached with exactly one heads are 0, 17, and 34. 65 is unfortunately not prime, and there are only 13 values that get repeated across all the coins, so 67 is the smallest number of buckets you can have under this scheme that's still enough to disambiguate at least 64 values.

If necessary for obfuscation, you and the partner can agree on a secret constant beforehand that you'll add to the actual binary value derived from the 64 coins, and if possible, you flip over a coin that will make that adjusted value, mod-67, equal to the index number of the coin you want to point to.

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

### Re: Eight by eight matrix, flip a coin.

Spoiler:
Number the coins 0-63. Take the bitwise XOR of all coins showing heads, and XOR the result with the position of the worthy coin. This will give you the coin you should flip. In the new configuration, the worthy coin will be the one corresponding to the bitwise XOR of all heads.