IMO shortlist 1983/5 solution

24th IMO 1983 shortlist

Problem 5

Let S_n be the set of all strictly decreasing sequences of n positive integers such that no term divides any other term. Given two sequences A = (a_i) and B = (b_j) we say that A < B if for some k, a_k < b_k and a_i = b_i for i < k. For example, (7, 5, 3) < (9, 7, 2) < (9, 8, 7). Find the sequence A in S_n such that A < B for any other B in S_n.

Solution

Note that any integer can be written (uniquely) as the product of an odd integer (the odd part) and a power of 2. Two members of a sequence in S_n must have different odd part, otherwise one would divide the other. So we cannot do better than start the minimal sequence with 2n-1, 2n-3, ... . However, we cannot go further than 2k+1, where k = [(n+1)/3] in this way, or we would get one term 3x another. To check this we need to consider three cases: (1) n=3m, so k = m and 3(2k-1) = 2n-3; (2) n=3m+1, so k=m, and 3(2k-1) = 2n-5; (3) n=3m+2, so k=m+1 and 3(2k-1)=2n-1. So for the final k terms we need to stop them dividing any of the preceding terms. The way to do this whilst keeping them as small as possible is to take 2 x the terms in A_k. (Note that we clearly need to multiply the odd terms in A_k by 2, but could we get away without doubling the even terms? They already do not divide the early odd terms in A_n, but if we fail to double them they will divide one of the newly doubled terms from A_k.)

Thus we get:
A₁ = {1}
A₂ = {3,2}
A₃ = {5,3.2}
A₄ = {7,5,3,2}
A₅ = {9,7,6,5,4}
A₆ = {11,9,7,6,5,4}

24th IMO shortlist 1983