3
$\begingroup$

[The first part of this puzzle was inspired by a puzzle I found on fivethirtyeight.com, but the rest is novel]

Part 1
There is a square table with a coin on each corner. You cannot see the table. The only way you can affect it is by telling the person controlling the table which coins in which corners to flip. This can be as many coins as you want, but all will be done at once. For example, a valid answer would be to 'flip the bottom left and top right coin'. After every move, or order, is executed, the person controlling the table will SPIN it to a new, random orientation that is indistinguishable from the original one.
Your goal: to make it reach the state of all heads. If, at any point, you reach this stage, you will immediately be told and you will win.
How do you do it in a finite number of moves?

Part 2
Find a general solution to the case where instead of having a table with 4 corners, the coins are placed on a $n\times n$ board, which follows the same rules. Again, you can specify your move as before, it will be spun as before, and your goal remains the same.
For any $n$, can it be done in a finite number of moves? If so, how? How does the number of moves increase with $n$?

Part 3
Instead of a square table, the table is now of the form of a regular $n$-gon. For which $n$ is this possible, and again, how does the number of moves vary with $n$?

I have solved the first part, and have a solution for the second part, but it is incomplete. The third part is completely up for grabs. I will post my answers to this below, with a brief explanation of why they work and why I think they are optimal. I suggest you try the first two parts yourself before seeing my solution. I would prefer if the answers to this followed notation consistent with my answers, but feel free to introduce new notation.

$\endgroup$
1
$\begingroup$

Part 1

The first key observation is to note that the actual positions of the coins don't really matter, as we will spin the table after every move. This means that all moves that are the same on rotation are in fact the same move, as their results are indistinguishable. This means the moves we have are to either flip the whole board (W), to flip any single coin (S), to flip two adjacent coins (A) and to flip two diagonally opposite coins (D).
Now, there are four possibilities for the initial state of the board.
$\begin{matrix} T & T\\ T & T \end{matrix}$(call this state 1)
$\begin{matrix} T & H\\ H & T \end{matrix}$(call this state 2)
$\begin{matrix} H & H\\ T & T \end{matrix}$(call this state 3)
$\begin{matrix} H & H\\ H & T \end{matrix}$(call this state 4)
Now, we first solve state 1, by flipping the whole thing(W). If it was initially in state 1, it is now solved, and if it was in state 2,3 or 4, it remains so(can be verified manually).
Next, we solve state 2. This can be done by first flipping a diagonal(D). This move either solves state 2, or brings it to state 1, which we solve by again solving state 1, or flipping the whole thing. Thus, our move sequence up till now has been W DW. It can easily be verified that this move sequence leaves state 3 and 4 unchanged.
Next, we solve state 3. We do this by flipping two coins along adjacent coins(A). This either solves it or brings it to state 1 or 2, which means we repeat the entire solution up till state 2. Thus, our move sequence is now W DW ADW
For the fourth part, we flip a single coin(S). This brings it to either state 1, 2 or 3. Now, we can simply repeat our solution up till state 3.
Thus, the final move sequence is
W DW ADW SWDWADW

Part 2
The next step is to solve it for an $n \times n$ grid. The trick we will use is to split every $n \times n$ grid into squares, which we already know the solution to. For example, we can split the following 3 by 3 grid as the 3 independent objects $S1$= ABCD, $S2$= EFGH and the independent point $S3$= I. Now, we can technically solve each one of the squares independently.
However, the issue is that our solution for a single square relies on the controlling person stopping us every time we hit the 4 heads condition, but now we only get a stop once all the 9 coins are heads. To get around this, we nest the solutions within one another. That is to say, to solve the 3 by 3 grid, we first do the first move of the $S1$, then execute the entire solution of $S2$ and $S3$ together. The solution of $S2$ and $S3$ consists of doing $S3$ after every move of $S2$. Thus, if at any point one of $S1, S2$ or $S3$ is solved, the rest will be checked too and solved. This again follows a recursive principle that the first solution needed. To finish the solution for a general $n \times n$ grid, we can merely note that any such grid can be subdivided into some combination of grids of smaller sizes.
Thus, the number of moves needed seems to exponentially grow.

This is all I have right now, and I hope for some further help for the hivemind!

$\endgroup$
1
$\begingroup$

Part 3?

Say we consider the table spinning game on a $n$-gon. Which solutions exist?

Let $n = 2^k$ for some $k \in \mathbb{N}$ then there exists a solution. The proof is of the same flavor as your answer. As a base case, assume that there is a solution for $k = 2$. As the induction hypothesis assume that the $2n$-gon has a solution.

Let's consider a $2 n$-gon. First, label the sides as a tuple $(v_1 , \ldots, v_{2 n})$. A side can be either 'heads' $1$ or 'tails' $0$. Rotations, also represented as tuples, swap the indices in a cyclical fashion. Next, note that every solution can be given as a sequence of reorientations $C(n) = \lbrace c_i \rbrace$ each of which is a XOR operator. As an example,

$$c = (0, \ldots, 0)$$

will be the null reorientation.

The basic idea will be to partition the $2n$-gon into blocks of size two. Each block is either matching or not matching. The miracle is that this means there are both $2^n$ ways to label the blocks and $2^n$ ways to label the internals (matching/not matching). Consider an arbitrary reorientation $c_i$ on a $n$-gon and two augmentations of the reorientation to a $2n$-gon reorientation,

$$c_i = (f_1(i),f_2(i),\ldots,f_{n}(i)) \to_{\phi} (f_1(i),f_1(i),\ldots,f_{n}(i),f_{n}(i))$$

$$d_i = (f_1(i),f_2(i),\ldots,f_{n}(i)) \to_{\psi} (f_1(i), 0, f_2(i), 0, \ldots, f_{n}(i), 0)$$

The internal labeling is not affected by applications of $\phi(c_i)$. I encourage you to check this. On the other hand, internal labeling can be switched by applications of $\psi(d_i)$. At this point, the natural solution is to first bring the block internal labeling to matching and then to align the block labels. Since we can't see anything we'll have to work under the assumption that any application of $\psi(d_i)$ could've matched internal orientations which would mean aligning blocks could start.

By induction, we have the solution sequence $C = \lbrace c_i \rbrace$ for the $n$-gon. Since our augmented reorientations respect this symmetry also we can bring each block through each label possibility by applying $\phi(I)$. We then apply $\psi(d_1)$ to switch internal labels followed by $\phi(C)$ again, and so on. As a sequence of applications,

$$\phi(C) \to \psi(d_1) \to \phi(C) \to \psi(d_2) \to \ldots \to \psi(d_n) \to \phi(C)$$

If the above explanation confuses you, remember the symmetry. One operation respects the block symmetry and there are $2^n$ of those. The other operation does not respect the symmetry and there are also $2^n$ of those. Thus, the $2n$-gon will be brought through $2^n \cdot 2^n = 2^{2n}$ states.

For $n = 1$ we can just abbreviate, $$1$$

For $n = 2$, $$11 \to 10 \to 11$$

For $n = 4$, $$1111 \to 1010 \to 1111 \to 1010 \to 1111 \to 1010 \to 1111 \to 1000 \to 1111 \to 1010 \to 1111 \to 1100 \to 1111 \to 1010 \to 1111$$

The recursion for length is,

$$l_{k+1} = (l_k+1) \cdot l_k + l_k = l_k^2 + l_k, \quad n_1 = 1$$

$$\Rightarrow l_k = 2^{2^{k-1}}-1$$

so larger problems are completely infeasible.

$\endgroup$
  • $\begingroup$ For $n=4$, the third step should be $1100$, not $1010$. (The strategy is a palindrome.) $\endgroup$ – Peter Kagey Jul 29 '20 at 3:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.