Here's a puzzle I worked through a while ago:
Alice and Bob are in prison, and the warden poses the following game. Alice will be lead alone into a room with an 8x8 chessboard. The warden will place a coin on each square, either heads or tails up. Any configuration of heads and tails is possible. The warden will then tell Alice that one of the squares is "special". Alice then must flip one coin on the board. The warden then leads Alice out of the room. Now the warden leads Bob into the room. Bob must look at the board, and guess which square is the "special" square. If he succeeds, both are set free. If he fails, their incarceration continues.
There is no communication between Alice and Bob during the game, and Bob cannot see/hear what's going on in the room when Alice is inside. However, they can discuss a strategy beforehand. Also, you may assume the board is oriented in such a way that Alice and Bob can agree on which side is the "bottom".
My Question:
Now I'm not going to write the answer I came up with in case anyone wants to solve this for themselves. I want to talk about proving the existence of a solution. The existence of a solution can be re-framed in the following way:
Let $(\mathbb{Z}_2^{64},+)$ be the group where the underlying set is 64-bit binary strings, and operation is bitwise-XOR. Let $e_j \in \mathbb{Z}_2^{64}$ denote the string with $1$ in position $j$ and $0$ everywhere else. Prove there exists a function $f:\mathbb{Z}_2^{64} \rightarrow \{0,1,\cdots,63\}$ with the property that for any $M \in \{0,1,\cdots,63\}$ and any $B \in \mathbb{Z}_2^{64}$, there exists $j$ such that $f(B + e_j) = M$.
My question is, without finding an actual example of such a function, could you prove that such a function exists via the probabilistic method? You have an enormous set of possible functions to be working over, so it seems likely that you could. However my attempts at getting the bounds to work have all failed so far. Any thoughts?