IMO 1983 SL 5

Origin: BRA

Problem

Consider the set of all strictly decreasing sequences of n natural numbers having the property that in each sequence no term divides any other term of the sequence. Let A = (aj) and B = (bj) be any two such sequences. We say that A precedes B if for some k, ak < bk and ai = bi for i < k. Find the terms of the first sequence of the set under this ordering.

Solution

Each natural number p can be written uniquely in the form p = 2q(2r−1). We call 2r −1 the odd part of p. Let An = (a1, a2, . . . , an) be the first sequence. Clearly the terms of An must have different odd parts, so those parts must be at least 1, 3, . . ., 2n −1. Being the first sequence, An must have the numbers 2n −1, 2n −3, . . ., 2k + 1 as terms, where k = [n + 1/3] (then 3(2k −1) < 2n −1 < 3(2k + 1)). Smaller odd numbers 2s + 1 (with s < k) obviously cannot be terms of An. In this way we have obtained the n −k odd numbers of An. The other k terms must be even, and by the same reasoning as above they must be precisely the terms of 2Ak (twice the terms of Ak). Therefore An is defined recursively as A0 = \emptyset, A1 = {1}, A2 = {3, 2}; An = {2n −1, 2n −3, . . . , 2k + 1} \cup2Ak.