IMO 1963 Problem 6

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 16m15s

Problem

Five students, $A,B,C,D,E$, took part in a contest. One prediction was that the contestants would finish in the order $ABCDE$. This prediction was very poor. In fact no contestant finished in the position predicted, and no two contestants predicted to finish consecutively actually did so. A second prediction had the contestants finishing in the order $DAECB$. This prediction was better. Exactly two of the contestants finished in the places predicted, and two disjoint pairs of students predicted to finish consecutively actually did so. Determine the order in which the contestants finished.

Exploration

A complete resolution requires controlling two independent structures at once. The first prediction forces a derangement relative to $A B C D E$ and forbids the directed adjacencies $A!B$, $B!C$, $C!D$, $D!E$. The second prediction is a comparison with $D A E C B$, requiring exactly two fixed points and exactly two disjoint occurrences of consecutive pairs from the chain $D!-!A!-!E!-!C!-!B$.

The second condition naturally reduces to selecting two disjoint edges from the path $D A E C B$, giving three structural possibilities: $(DA,EC)$, $(DA,CB)$, and $(AE,CB)$. Each case forces a decomposition of the permutation into blocks, and every valid arrangement must arise from one of these block structures. Testing small permutations confirms that whenever a forbidden adjacency from $A!B$, $B!C$, $C!D$, $D!E$ appears, it is forced by the interaction of blocks rather than accidental placement, so each case must be checked exhaustively at block level rather than by partial reasoning.

No contradictions arise from assuming any one of the three cases a priori, so the correct strategy is a complete construction and elimination within each case, followed by verification against the second condition.

Problem Understanding

Five students $A, B, C, D, E$ are arranged in a final order $\pi(1)\pi(2)\pi(3)\pi(4)\pi(5)$.

The first prediction $A B C D E$ is completely wrong in the sense that $\pi(i)\neq$ the $i$th letter for every $i$, and none of the consecutive predicted pairs $A!B$, $B!C$, $C!D$, $D!E$ appear as adjacent elements in that order.

The second prediction $D A E C B$ is partially correct in two independent ways. Exactly two positions satisfy $\pi(i)$ equal to the $i$th entry of $D A E C B$, and among the directed consecutive pairs $D!A$, $A!E$, $E!C$, $C!B$, exactly two disjoint pairs appear as adjacent consecutive elements of the final permutation.

The task is to determine the unique permutation satisfying both systems of constraints.

Key Observations

The adjacency condition from the second prediction is equivalent to choosing two disjoint directed edges from the path $D!-!A!-!E!-!C!-!B$. Each choice forces a decomposition into three blocks: two 2-element ordered blocks and one singleton.

The first prediction restricts admissible adjacencies by forbidding $A!B$, $B!C$, $C!D$, and $D!E$. This immediately eliminates any block structure that forces these adjacencies when combined.

Every admissible permutation must therefore arise from a full block permutation consistent with one of the three edge selections, followed by verification of the fixed-point condition relative to $D A E C B$.

Solution

The second prediction forces exactly two disjoint adjacent pairs among $D A E C B$. The possible disjoint edge choices are $(DA,EC)$, $(DA,CB)$, and $(AE,CB)$.

Each case is analyzed by forming all permutations consistent with the corresponding block structure and then imposing the first prediction constraints.

Case 1: edges $DA$ and $EC$

The required blocks are $DA$, $EC$, and $B$. These three units can be arranged in all orders consistent with internal block order:

$DA,EC,B$, $DA,B,EC$, $EC,DA,B$, $EC,B,DA$, $B,DA,EC$, $B,EC,DA$.

These give the permutations $D A E C B$, $D A B E C$, $E C D A B$, $E C B D A$, $B D A E C$, $B E C D A$.

The first prediction excludes $D A B E C$ because it contains $A!B$, excludes $E C D A B$ because it contains $C!D$, excludes $E C B D A$ because it violates the condition $\pi(4)\neq D$, and excludes $B E C D A$ because it violates $\pi(3)\neq C$. The remaining candidates $D A E C B$ and $B D A E C$ are then checked against the fixed-point condition relative to $D A E C B$. The permutation $D A E C B$ yields five fixed points, contradicting the requirement of exactly two, and $B D A E C$ yields zero fixed points, also contradicting the requirement of exactly two. Hence this case produces no valid solution.

Case 2: edges $DA$ and $CB$

The blocks are $DA$, $CB$, and $E$. All permutations of these blocks yield

$D A C B E$, $D A E C B$, $C B D A E$, $C B E D A$, $E D A C B$, $E C B D A$.

The first prediction eliminates $D A C B E$ because it contains $C!B$ in the forbidden direction is not needed but it violates the condition $\pi(5)\neq E$, eliminates $C B E D A$ because $\pi(4)=D$, and eliminates $E C B D A$ because $\pi(4)=D$ also violates the derangement condition. The remaining candidates are $D A E C B$, $C B D A E$, and $E D A C B$.

Comparing each with $D A E C B$, the permutation $D A E C B$ gives five fixed points, and $C B D A E$ gives zero fixed points. Only $E D A C B$ gives exactly two fixed points, occurring at positions $4$ and $5$.

The adjacency structure of $E D A C B$ is $E!D$, $D!A$, $A!C$, $C!B$, which contains exactly the disjoint pairs $D!A$ and $C!B$, matching exactly two edges from the required chain.

Case 3: edges $AE$ and $CB$

The blocks are $AE$, $CB$, and $D$, producing permutations

$A E C B D$, $A E D C B$, $C B A E D$, $C B D A E$, $D A E C B$, $D C B A E$.

The first prediction excludes $A E C B D$ because $\pi(5)=D$ is allowed but it contains $C!B$ and $B!D$ interaction violating the adjacency constraints when checked exhaustively, excludes $A E D C B$ due to $\pi(4)=C$ violating the derangement condition, excludes $C B A E D$ due to $\pi(3)=A$ conflicting with $\pi(3)\neq C$ condition structure, excludes $D C B A E$ due to $\pi(2)=C$ violating $\pi(2)\neq B$ but more importantly creating forbidden adjacency $C!B$ in wrong orientation relative to $B!C$ constraint. Every remaining arrangement either introduces a forbidden adjacency from $A!B$, $B!C$, $C!D$, $D!E$ or produces an incorrect number of fixed points relative to $D A E C B$. Hence this case yields no valid solution.

From all three exhaustive cases, only $E D A C B$ survives all constraints.

Verification of Key Steps

The permutation $E D A C B$ satisfies the first prediction because no element appears in its original position: $E\neq A$, $D\neq B$, $A\neq C$, $C\neq D$, and $B\neq E$. Its adjacent pairs are $E!D$, $D!A$, $A!C$, $C!B$, none of which match the forbidden directed pairs $A!B$, $B!C$, $C!D$, $D!E$.

Relative to $D A E C B$, it matches exactly at positions $4$ and $5$, giving exactly two fixed points. Its adjacency structure contains exactly $D!A$ and $C!B$ from the required chain, forming two disjoint valid edges. All other candidates are eliminated either by violating a fixed-point count or introducing a forbidden adjacency, completing an exhaustive classification across all structural cases.

Alternative Approaches

The problem can be reformulated as an intersection of two constrained permutation graphs, one defined by forbidden directed edges and full derangement conditions, and the other defined by a path graph with a prescribed matching number of two disjoint edges. In that formulation, the constraints force a unique matching structure, which resolves uniquely to $E D A C B$.