How many cards do you have to flip without looking to get four arbitrarily turned playing cards all facing down.

Matt Parker, the creator of The Parker Square, regularly poses online math puzzles. Below is the video in which he explains the problem I’m trying to solve.

Can you construct such a sequence of flipping cards that if given four arbitrarily turned cards there will be a point in the sequence where all four cards are facing down?

Each card can be either face up or face down. Lets denote the possible states with $S$ and define $$S = \Big\{🂠, 🂱\Big\},\ \text{where}\\ \neg🂠 = 🂱 \ \\\text{and}\\ \neg 🂱 = 🂠.$$ Then all possible four card configurations are $S^4$, e.g. $$\Big(🂠, 🂠, 🂠, 🂠\Big), \Big(🂠, 🂱, 🂱, 🂠\Big), \Big(🂱, 🂠, 🂱, 🂱\Big) \in S^4$$ For $i \in \{1, 2, 3, 4\}$ lets define a single card flip $F_i \colon S^4 \rightarrow S^4$ with $$ F_i\colon \mathbf{C} = (C_1, C_2, C_3, C_4) \mapsto (C_1', C_2', C_3', C_4')\\ C_j' = \begin{cases}\neg C_j & i = j \\ C_j & i\neq j \end{cases},\ \forall j \in \{1, 2, 3, 4\}\ .$$ The goal is to find the smallest $n$ for which there exists a sequence of flips $\mathbf{H} = (H_1, H_2, ..., H_n) \in \{F_1, F_2, F_3, F_4\}^n$ such that $$ \forall \mathbf{C} \in S^4, \ \exists m \leq n \colon H_m \circ H_{m-1} \circ ... \circ H_2 \circ H_1 (\mathbf{C}) = \Big(🂠, 🂠, 🂠, 🂠\Big)\ .$$

Show/hide formal definition.

Firstly we can see that each sequence of flipping cards is it’s own inverse. Which means that we can think of the problem as inverse. Instead of translating each card configuration into face down cards, we can start with all face down cards and translate it into every configuration.

For any $n$ and $\mathbf{H} = (H_1, H_2, ..., H_n) \in \{F_1, F_2, F_3, F_4\}^n$ $$ \underline{\forall \mathbf{C} \in S^4, \ \exists m \leq n \colon H_m \circ H_{m-1} \circ ... \circ H_2 \circ H_1 (\mathbf{C}) = \Big(🂠, 🂠, 🂠, 🂠\Big)} \\ \underline{\iff}\\ \underline{\forall \mathbf{C} \in S^4, \ \exists m \leq n \colon H_m \circ H_{m-1} \circ ... \circ H_2 \circ H_1 \Big(🂠, 🂠, 🂠, 🂠\Big) = \mathbf{C}}$$ For any sequence of flips a card will be in the starting position if we flip it an even number of times. Regardless of the order in which we flip other cards the only thing that matters is the count (mod 2) of each flip.

That automatically means that any sequence applied twice will be an identity and will not change any of the cards, i.e. every sequence is it's own inverse.

$\underline{\implies}$
for any $\mathbf{C} \in S^4$ we have $H^{(m)}=\colon H_m \circ H_{m-1} \circ ... \circ H_2 \circ H_1$ $$ H^{(m)}(\mathbf{C}) = \Big(🂠, 🂠, 🂠, 🂠\Big) $$ apply $H^{(m)}$ on both sides $$ \not H^{(m)}(\not H^{(m)}(\mathbf{C})) = H^{(m)}\Big(🂠, 🂠, 🂠, 🂠\Big) \\ \mathbf{C} = H^{(m)}\Big(🂠, 🂠, 🂠, 🂠\Big) $$

$\underline{\impliedby}$
for any $\mathbf{C} \in S^4$ we have $H^{(m)}=\colon H_m \circ H_{m-1} \circ ... \circ H_2 \circ H_1$ $$ H^{(m)}\Big(🂠, 🂠, 🂠, 🂠\Big) = \mathbf{C} $$ apply $H^{(m)}$ on both sides $$ \not H^{(m)}\left(\not H^{(m)}\Big(🂠, 🂠, 🂠, 🂠\Big)\right) = H^{(m)}(\mathbf{C}) \\ \Big(🂠, 🂠, 🂠, 🂠\Big) = H^{(m)}(\mathbf{C}) $$ □

Show/hide formal proof.

We can visualize the problem as graph traversal where each of the nodes represents a specific configuration of cards and edges represent single card flips. This is equivalent to a four dimensional hypercube.

Let's define graph $G = (V, E)$ such that vertexes are all possible card combinations $$ V = S^4 $$ and edges connect all card states that can be reached with a single card flip $$ \forall \mathbf{C}, \mathbf{C'} \in V \colon (\mathbf{C}, \mathbf{C'}) \in E \iff \exists i\ F_i(\mathbf{C}) = \mathbf{C'} \ .$$ A 4D Hypercube graph $Q_4$ is constructed in the exact same manner. Only difference is swapping 🂠 for 0 and 🂱 for 1. Only points that differ in one coordinate are connected, same as $G$. Therefore the two graphs are isomorphic. $$G \cong Q_4$$ □

Show/hide formal proof.

Below is a tool I built to make this easier to understand. We can change the number of cards in the game to change the dimensionality of the hypercube graph. We can traverse it flipping cards or by clicking on nodes to load that state.

The thicker lines between cubes represent all the connections between nodes in the same corner to prevent overcrowding the graph with edges.

  • Click cards to flip them.
  • Click -/+ to remove or add cards.
  • Click nodes below to jump to card state.
cursor

The problem as we now understand it can be posed as “How many steps does it take to traverse all corners of a 4D hypercube?” We know that we have to visit $2^4=16$ corners, which will take at minimum $15$ steps. Can we visit all of them without repeating any corners?

A path over a graph that visits all vertexes exactly once is called a Hamiltonian path. Does a 4D hypercube have a Hamiltonian path? The answer is a resounding yes. Not only can we traverse all vertexes in 15 steps, we can end our journey adjacent to our starting point, i.e. the graph has a Hamiltonian cycle.

Below is an example of such a path. Horizontal lines ⸺ equate to flipping the first card, vertical lines | represent flipping the second card, diagonals \ flip the third, and jumping between the two cubes means flipping the fourth card.

hypercube_traversal

All the arguments we made above are not limited to four cards or four dimensions. In fact, if we have $N$ cards we can solve the problem by traversing the Hamilton path in a $N$-dimensional hypercube which we can do in $2^N-1$ steps.

We can construct an optimal solution recursively. Let’s denote $S_N$ as an optimal sequence of flips for $N$ cards.

End condition
For one card it’s easy. We only have one card and therefore only one winning move.

\[S_1 = (1)\]

Recursive step
For any number of cards $N>1$ we can first traverse all possibilities for the first $N-1$ cards, flip the $N$-th card, and again repeat the sequence for the first $N-1$ cards.

\[S_N = (S_{N-1}, N, S_{N-1})\]

Analysis
I want to look at the size of each solution to confirm that they are indeed the minimum size.

\[|S_1| = 1 \land |S_N| = 2 |S_{N-1}| + 1 \iff |S_N| = 2^N-1\]

□

Show/hide formal solution.

Number of cards $N$ Optimal flipping sequence $S_N$ Length of the sequence $|S_N| = 2^N-1$
1 1 1
2 1, 2, 1 3
3 1, 2, 1, 3, 1, 2, 1 7
4 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1 15
5 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1 31
6 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1 63
7 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1 127
8 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 8, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1 255