IMO 1987 SL 11

Origin: POL

Problem

Find the number of partitions of the set {1, 2, . . ., n} into three subsets A1, A2, A3, some of which may be empty, such that the following conditions are satisfied: (i) After the elements of every subset have been put in ascending order, every two consecutive elements of any subset have different parity. (ii) If A1, A2, A3 are all nonempty, then in exactly one of them the minimal number is even.

Solution

Let A1 be the set that contains 1, and let the minimal element of A2 be less than that of A3. We shall construct the partitions with required properties by allocating successively numbers to the subsets that always obey the rules. The number 1 must go to A1; we show that for every subsequent number we have exactly two possibilities. Actually, while A2 and A3 are both empty, every successive number can enter either A1 or A2. Further, when A2 is no longer empty, we use induction on the number to be placed, denote it by m: if m can enter Ai or Aj but not Ak, and it enters Ai, then m + 1 can be placed in Ai or Ak, but not in Aj. The induction step is finished. This immediately gives us that the final answer is 2n−1.