A magician places n coins on a table and walks down off the stage. A volunteer comes, turns over whichever coins he wishes, selects one coin and whispers its number to the apprentice. Then the apprentice turns over one coin aiming to assist the magician to know the selected coin.
For which values of n the magic will always succeed? What if the apprentice may turn at most one coin?
For the first question: (For which values of n the magic will always succeed?)
Answer: We have $n$ coins which can be in $2$ different states - hands or tails, thus there's $2^n$ coin states.
Let's make the coin's number as its binary representation with number of bits that is equal to the chosen $n$.
The assistant will do the XOR operation with the coins that their heads match the coin that has selected. This will be achieved by using the bitwise XOR of current state with the coin that was selected (by the volunteer) and flipping the coin with that number.
To conclude, $n$ has to be a factor of $2^n$, meaning that $n$ has to be a power of $2$. Flipping the $0$ coin is free, so the assistant can flip a coin whenever he wants.
I thought also about approach with representing the $2^n$ states with a hypercube, we'll give each vertex a color to represent one of the $n$ named coins. There must be one of each color adjacent to any starting position, so there are equal number of each color. Thus, as stated above $n$ must be a factor of $2^n$, thus $n$ must be a power of $2$.
I'm interested to know for which values of $n$ the magic will succeed when the apprentice may turn at most one coin.
This means that each monochromatic set is a dominating set for the hypercube graph $Q_n$. The domatic number $d(G)$ of a graph $G$ is the maximum number of elements in a partition of the set of vertices of $G$ into dominating sets. Thus the question is whether $d(Q_n)\ge n$. According to [JBM], Zelinka in [Z] proved that if $n=2^k$ for a positive integer $k$ then graphs $Q_n$ and $Q_{n-1}$ both have the domatic number $n$, so in this case the answer to your question is positive. On the other hand, for each graph $G$ we have $d(G)\le |G|/\gamma(G)$, where $|G|$ is the number of vertices in $G$ and $\gamma(G)$ is the number of vertices in a smallest dominating set for $G$. According to [KM] “Unfortunately, the exact domination number is known only for small dimensional hypercubes and two infinite families: $\gamma(Q_3) = 2$, $\gamma(Q_4) = 4$, $\gamma(Q_5) = 7$, $\gamma(Q_6) = 12$, and $\gamma(Q_n) = 2^{n−k}$ for $n = 2^k − 1$ or $n = 2^k$, see [HL]. In general, $\gamma(Q_n) \le 2^{n−3}$ for $n\ge 7$ [AK]”. Thus we have $d(Q_5)\le 4$ and $d(Q_6)\le 5$, so for these values of $n$ the answer to your question is negative.
References
[AK] S. Arumugam, R. Kala, Domination parameters of hypercubes, J. Indian Math. Soc. (N.S.) 65 (1998), 31–38.
[HHW] Frank Harary, John P. Hayes, Horng-Jyh Wu, A survey of the theory of hypercube graphs, Comput. Math. Applic. 15:4 (1988), 277-289.
[HL] F. Harary, M. Livingston, Independent domination in hypercubes, Appl. Math. Lett. 6 (1993), 27–28.
[JBM] T.N.Janakiraman, M.Bhanumathi, S.Muthammai, Domination Parameters Of Hypercubes, International Journal of Engineering Science, Advanced Computing and Bio-Technology, 1:1 (January -March 2010), 19–28.
[KM] Sandi Klavžar, Meijie Ma, The domination number of exchanged hypercubes.
[Z] B.Zelinka, Domination numbers of cube graphs, Math Slovaca, 32:2 (1982), 117–1. (unfortunalety, I failed to find this paper).