IMO 1963 · Problem 6

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.

Official text of the problem. Official problem paper (PDF)

Answer

The contestants finished in the order \[ \boxed{EDACB}. \]

Solution

Write \(XY\) for the consecutive pair in which \(X\) finishes immediately before \(Y\). The first prediction tells us that \[ A\ne1,\quad B\ne2,\quad C\ne3,\quad D\ne4,\quad E\ne5, \] where each inequality excludes the indicated finishing position. It also forbids the consecutive pairs \(AB,BC,CD,DE\).

The second prediction gives the consecutive pairs \[ DA,\quad AE,\quad EC,\quad CB. \] The only ways to choose two disjoint pairs from this list are \[ \{DA,EC\},\qquad \{DA,CB\},\qquad \{AE,CB\}. \]

We first rule out the last possibility. Suppose \(AE\) and \(CB\) both occur. Since \(A\) cannot finish first and \(E\) cannot finish fifth, the pair \(AE\) must occupy positions \(2,3\) or \(3,4\).

  • If \(AE\) occupies positions \(2,3\), the pair \(CB\) must occupy positions \(4,5\), leaving \(D\) first. The order is then \(DAECB\), so all five positions in the second prediction are correct, a contradiction.
  • If \(AE\) occupies positions \(3,4\), the pair \(CB\) must occupy positions \(1,2\). This puts \(B\) second, contradicting the first prediction’s failure.

Consequently, \(DA\) must occur. There are four possible positions for this pair.

  • Positions \(1,2\): Both \(D\) and \(A\) are correctly placed by the second prediction. The third contestant cannot be \(E\), since that would give a third correct position; cannot be \(C\), since the first prediction incorrectly placed \(C\) third; and cannot be \(B\), since that would create the forbidden pair \(AB\). Thus this case is impossible.
  • Positions \(3,4\): Of the positions predicted by \(DAECB\), only \(B\) in fifth place could be correct. This contradicts the requirement of exactly two correct positions.
  • Positions \(4,5\): This puts \(D\) fourth, contradicting the first prediction’s failure.
  • Positions \(2,3\): The first three positions predicted by \(DAECB\) are all incorrect. Hence its two correct positions must be \(C\) fourth and \(B\) fifth. The remaining student, \(E\), is first.

Thus the only possible order is \(EDACB\).

Finally, this order satisfies every condition. None of its contestants occupies the position predicted by \(ABCDE\), and its consecutive pairs \[ ED,\ DA,\ AC,\ CB \] include none of \(AB,BC,CD,DE\). Compared with \(DAECB\), exactly \(C\) and \(B\) occupy their predicted positions, and precisely the two disjoint consecutive pairs \(DA\) and \(CB\) occur.

The solution was checked against John Scholes' IMO solution archive (Kalva).