The Legendary Todai Entrance Exam Problem

Problem Statement

Origin Tokyo University entrance exam, science branch, 1998 second semester, Problem 3 (show derivations). The book 入試数学伝説の良問100 describes this problem as the most difficult entrance exam problem in the history. Online sources seem to agree. Note that this is a loose translation.

A graph $G = (V, W)$ is a tuple of a node set $V = \{P_1,\dots,P_n\}$ and an edge set $E = \{E_1,\dots,E_m\}$. Each node is colored either white or black.

From any graph $G=(V,W)$, define two operations for creating a new graph $G'=(V',W')$ with one additional node $P'$:

Operation 1 picks a node $P \in V$ and then adds an edge $(P, P')$. The color of $P$ is flipped, while $P'$ is painted white.

Operation 2 picks an edge $E = (P, \tilde P) \in W$, removes the edge, and then adds two new edges $(P,P')$ and $(\tilde P,P')$. The color of $P$ is flipped, the color of $\tilde P$ is also flipped, and $P'$ is painted white.

Let the starting graph contain a single white node:

(1) Prove that each of the graphs below can be obtained via the two operations above. (All nodes are white.)

(2) Find the necessary and sufficient condition for $n \in \NN$ such that the graph below with $n$ nodes can be obtrained via the two operations. (All nodes are white.)

...
(n nodes)

Solution

(1) All steps are Operation 1 unless indicated.

Op. 2

(2) We will aim for induction.

It's easier to think in reverse. Starting from the target graph with $n$ nodes lying on a single line:

Reverse of Operation 1: Pick a white end node $P$, flip the color of the adjacent node, and then remove $P$.

Reverse of Operation 2: Pick a white intermediate node $P$, flip the colors of the adjacent nodes, and then remove $P$.

In addition, with all nodes in the same line, we can merge the two operations by adding auxiliary nodes to both ends. These nodes cannot be operated upon, and the goal is to collapse all nodes except these auxiliary nodes (which do not have to end up white).

When $n = 0$ or $n = 1$ all nodes can be collapsed uniquely.

When $n = 2$, the nodes cannot be collapsed completely.

Now consider the general case with $n$ nodes. Suppose we succeed, and the last node we remove is $P$, with $l$ nodes on the left and $r = n-l-1$ nodes on the right:

$l$ nodes
$r$ nodes
$P$
$\vdots$
?
$P$
?
?
?

This breaks the problem into 2 subproblems of sizes $l$ and $r$ ($0 \leq l \leq n-1$). The order in which we remove the nodes from these subproblems does not matter. The only requirement is that after both subproblems are solved, $P$ must be white; i.e., have been flipped an even number of times.

Based on the small cases, we make a hypothesis:

  • If $n = 3u$, then all $n$ nodes can be collapsed, and both auxiliary nodes will always become white (i.e., have been flipped even numbers of times).
  • If $n = 3u + 1$, then all $n$ nodes can be collapsed, and both auxiliary nodes will always become black (i.e., have been flipped odd numbers of times).
  • If $n = 3u + 2$, then we will fail to collapse all $n$ nodes.

We will prove by induction. The base cases ($n = 0,1,2$) are already proven. For the inductive step, we consider the 3 cases separately. Due to the inductive hypothesis, a subproblem (red or blue) cannot have size $3v+2$.

  • If $n = 3u$, we can only do $l = 3v + 1$ and $r = 3w + 1$. This flips $P$ (odd + odd) = even number of times, and flips both auxiliary nodes (odd + 1) = even number of times.
  • If $n = 3u+1$, we can only do $l = 3v$ and $r = 3w$. This flips $P$ (even + even) = even number of times, and flips both auxiliary nodes (even + 1) = odd number of times.
  • If $n = 3u+2$, one of $l$ and $r$ must be $3v$ and the other must be $3w+1$. This flips $P$ (even + odd) = odd number of times, and thus we will always fail to collapse all nodes.

Therefore, all $n$ nodes can be collapsed if and only if $n \not\equiv 2 \pmod 3$.

Epilogue

The original problem statement is very verbose, making it look deceptively scary. On top of that, the book uses group theory to prove (2), which makes the problem look even scarier. (Well, the solution above also uses ideas from group theory without referring to group theory.)

Another thing: here is International Mathematical Olympiad 2005 Shortlist, Problem C5:

There are $ n$ markers, each with one side white and the other side black. In the beginning, these $ n$ markers are aligned in a row so that their white sides are all up. In each step, if possible, we choose a marker whose white side is up (but not one of the outermost markers), remove it, and reverse the closest marker to the left of it and also reverse the closest marker to the right of it. Prove that, by a finite sequence of such steps, one can achieve a state with only two markers remaining if and only if $ n - 1$ is not divisible by $3$.

Err... it's exactly the same problem! Somehow it managed to get to the shortlist.

Exported: 2017-06-10T05:02:15.338085