IMO 1983 SL 8

Origin: SPA

Problem

In a test, 3n students participate, who are located in three rows of n students in each. The students leave the test room one by one. If N1(t), N2(t), N3(t) denote the numbers of students in the first, second, and third row respectively at time t, find the probability that for each t during the test, |Ni(t) −Nj(t)| < 2, i ̸= j, i, j = 1, 2, . . . .

Solution

Situations in which the condition of the statement is fulfilled are the fol- lowing: S1: N1(t) = N2(t) = N3(t) S2: Ni(t) = Nj(t) = h, Nk(t) = h + 1, where (i, j, k) is a permutation of the set {1, 2, 3}. In this case the first student to leave must be from row k. This leads to the situation S1. S3: Ni(t) = h, Nj(t) = Nk(t) = h + 1, ((i, j, k) is a permutation of the set {1, 2, 3}). In this situation the first student leaving the room belongs to row j (or k) and the second to row k (or j). After this we arrive at the situation S1. Hence, the initial situation is S1 and after each triple of students leaving the room the situation S1 must recur. We shall compute the probability Ph that from a situation S1 with 3h students in the room (h \leqn) one arrives at a situation S1 with 3(h −1) students in the room: Ph = (3h) \cdot (2h) \cdot h (3h) \cdot (3h −1) \cdot (3h −2) = 3!h3 3h(3h −1)(3h −2). Since the room becomes empty after the repetition of n such processes, which are independent, we obtain for the probability sought P = n

h=1 Ph = (3!)n(n!)3 (3n)! .