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.
Problem
Source: IMO 1963, Day 2, Problem 6
Tags: combinatorics, permutations, IMO, IMO 1963
E^(pi*i)=-1
01.07.2008 19:13
We use casework on the first place student.
It is impossible for $ A$ to be first, as this would agree with Prediction 1.
If $ B$ is first, then $ (CB)$ could not have finished consecutively. So the possible pairs from Prediction 2 are $ (DA)$, $ (AE)$, and $ (EC)$. Only $ (DA)$ and $ (EC)$ are disjoint. We cannot start with $ BEC$, as this would place $ C$ as predicted in Prediction 1. So our order is $ BDAEC$, which has no agreement with Prediction 2. So $ B$ cannot be first.
If $ C$ is first, then the possible pairs from Prediction 2 are $ (DA)$, $ (AE)$, and $ (CB)$. We cannot use $ (CB)$ because it would place $ B$ as predicted by Prediction 1. This leaves only $ (DA)$ and $ (AE)$, which are not disjoint, so it is impossible for $ C$ to be first.
If $ D$ is first, we can either use $ (DA)$ or not. If we do, then we must choose either $ (EC)$ or $ (CB)$ as our second pair. If we use $ (EC)$, we cannot start $ DAEC$, as this agrees in four places with Prediction 2. So we have $ DABEC$, which shares $ (AB)$ with Prediction 1, so it is impossible. If we use $ (CB)$, we cannot start $ DACB$, as $ C$ agrees with Prediction 1. So we are left with $ DAECB$, which agrees in five places with Prediction 2.
So we cannot use $ (DA)$. The possible pairs from Prediction 2 are $ (AE)$, $ (EC)$, and $ (CB)$. Only $ (AE)$ and $ (CB)$ are disjoint. We cannot place $ (AE)$ right after $ D$, as $ (DA)$ is forbidden. So we must have $ DCBAE$, in which $ E$ agrees with Prediction 1. So $ D$ cannot be first.
Thus, $ E$ is first. The possible pairs from Prediction 2 are $ (DA)$, $ (EC)$, and $ (CB)$. If we use $ (EC)$, then we must also use $ (DA)$. But $ ECBDA$ and $ ECDAB$ have only zero and one correspondences with Prediction 2, respectively. So we cannot use $ (EC)$
If we don't use $ (EC)$, then we must have $ EDACB$ (preventing $ (EC)$ by not placing $ (CB)$ right after $ E$). This clearly satisfies all requirements, so it is the desired order.
1=2
29.03.2012 18:19
Wouldn't that order be wrong, though? B and C finish consecutively, as do D and E. Or is it that they must finish consecutively in the order that was predicted? So A can't be right before B, but B can be right before A?
sunjae62700
13.01.2016 04:43
Why there are no pure combinatorics questions in the early IMOs?
ayan_mathematics_king
01.05.2019 08:43
sunjae62700 wrote: Why there are no pure combinatorics questions in the early IMOs? Do you want to mean counting??