What I'll do is that:
- I will decide with my friend that we map the board from top-left to bottom-right from 0 to 63
- I'll decide with him that we count only Tails (Heads also will work :-) )
- Now what we'll do is XoR between all the Tails and get a result
- Flip the coin that needed to fix the XoR to the wanted square - your penny
Example: lets say that there are tails only on 3,7,20,61 and the chosen sqare is 8:
XoR on them {3,7,20,61} will be: 45.
now what number XoR 45 will give us 8? 37!!
I'll flip 37 :-)
that's it...
This is actually interesting.
Let's say there are $n$ coins, and we want to find the maximum flips.
It turns out that,
for $n$ even, the maximum is attained at TT...THH..H, with $n/2$ T and $n/2$ H;
for $n$ odd, the maximum is attained at T...THH...H, with $(n - 1)/2$ T and $(n + 1)/2$ H.
In both cases, the maximun number of flips is $n(n+1)/2$, and the configuration attaining the max is unique.
I'll leave the proof to others, because it's time for bed...
Seems nobody else wants to give a proof ...
OK here we go.
Let $M(n)$ be the maximum number of flips among all configurations of $n$ coins. For such a configuration, there are two possibilities:
The $n$-th coin is T. Then the $n$-th coin will always remain T, until the end of the game. Hence it is essentially a game with $n - 1$ coins and the maximum number of flips is no more than $M(n - 1)$.
The $n$-th coin is H. Then the $n$-th coin will still remain H, until the configuration HH...H is reached. After that, it's easy to see that $n$ more flips leads to the final configuration TT...T.
Therefore it suffices to consider the number of flips until the configuration HH...H.
Now we reindex the coins: previously they were indexed $1, 2, \dotsc, n$, and now we index them as $n - 1, \dotsc, 1, 0$. Under this new index system, the rule of flipping becomes: if there are $k$ tails among the first $n - 1$ coins, then we flip the coin with new index $k$. The procedure continues until all the first $n - 1$ coins are H, i.e. we reach the configuration HH...H.
This is then exactly the same game with $n - 1$ coins, and with heads and tails exchanged. Thus the maximum number of flips until the configuration HH...H is $M(n - 1)$, and hence the total maximum number of flips (until the configuration TT...T) is $M(n - 1) + n$.
Combining 1. and 2., we get $M(n) = M(n - 1) + n$, and the maximum is attained only when the last coin is H, and the first $n - 1$ coins attain the maximum for the game with $n - 1$ coins, with H and T switched and order inversed.
By induction on $n$, this proves exactly our claims.
Best Answer
For the follow-up you have to assume that success will be announced after each try if you manage. We assume that a malevolent adversary controls the rotation, but you can flip a single coin, an opposite pair, or an adjacent pair at your option. You just can't keep track of anything except relative position between flips. You start knowing they are not all heads or all tails. Flip two opposite coins. If that doesn't work, you either have an odd number of heads or two adjacent heads. Flip two neighboring coins. If that doesn't work, you either have two opposite heads or an odd number of heads. Flip two opposite coins. If that doesn't work, you have an odd number of heads. Note that so far, we have always flipped an even number, so the parity hasn't changed. Flip one coin. If that doesn't work, you have two heads and two tails. Flip two opposite coins. If that doesn't work, you have two neighboring heads. Flip two adjacent. If that doesn't work, you have two opposite heads. Flip two opposite. Guaranteed to work.
If success is all heads instead of all the same, put flip all four at the start and after every step of the above.