Anton Shepelev <
anto...@gmail.com> writes:
> Mike Terry to Anton Shepelev:
>
>> > I hoped this would not transpire, but we did it with a
>> > 2x2 board, which is elementary. With Jonathan's two-
>> > dimensional decomposition, 3x3 seems possible as well,
>> > after a little drilling.
>>
>> You mean 4x4? (The method works for sides 2,4,8, etc..)
>
> You are right. It is time I gave my solution, which works
> with a linear array of 2^n cells, with C(i) denoting the
> cell value -- zero or unity. I index the cells from 0 to
> n-1, and consider the resulting bit array as encoding an
> integer K:
>
> K = XOR( C(i) * i ), for i = 0 to n-1
>
> where XOR is, well, the bit-wise exclusinve OR operation
> upon a binary number. K is of the same size, and takes the
> same values, as the array indices. It can be changed to any
> other value by iversion of the cell at the index whose
> binary value has zeros where the corresponding bits of K
> should be preserved and unities where they should be
> inverted. Inverting the cell as index zero does not affect
> K.
8x8 is a lot to remember, but the binary decomposition does
mean that you can keep the calculations mostly trivial. Does
a subset of the board have odd or even parity? Repeat for the
various different subsets. 6 in the case of 8x8. If you can
remember 7 separate parity values, then you can perform the
3 calculations even more easily.
For 4x4, the 4 subsets are
YYYY
YYYY
....
....
YYYY
....
YYYY
....
YY..
YY..
YY..
YY..
Y.Y.
Y.Y.
Y.Y.
Y.Y.
As you can see, you only need the parity value of 3 rows to create 2 of
the decision values.
If the parity of the subset is 1, then the coin you're interested in
is in that subset. So when setting up the board and selecting which
coin to flip, if the interesting cell is in a subset, ensure that subset
has odd parity. If it already has the right parity, flip something in the
complement of that subset instead.
So if the parity values of all the subsets start in the perfect
configuration such that they identify the appropriate grid location,
then you flip this coin:
....
....
....
...X
because it doesn't take part in any of the parity calculation, and so
won't change the communicated square.
I really wouldn't want to do it on 8x8, to be honest, in particular as I
have terrible short term memory, but 4x4 seems easy, as you can see each
subset in one glance - if you forget anything, you can work it out again
instantly. Cognitively, 32 is a way bigger number than 8.
Phil
--
We are no longer hunters and nomads. No longer awed and frightened, as we have
gained some understanding of the world in which we live. As such, we can cast
aside childish remnants from the dawn of our civilization.
-- NotSanguine on SoylentNews, after Eugen Weber in /The Western Tradition/