IMO 2002 SL A6

Origin: IRN | Category: Algebra

Problem

Let A be a nonempty set of positive integers. Suppose that there are positive integers b1, . . . , bn and c1, . . . , cn such that (i) for each i the set biA + ci = {bia + ci | a \inA} is a subset of A, and (ii) the sets biA + ci and bjA + cj are disjoint whenever i ̸= j. Prove that b1

• \cdot \cdot \cdot + 1 bn \leq1.

Solution

Assume to the contrary that b1 + \cdot \cdot \cdot + bn > 1. Certainly n \geq2 and A is infinite. Define fi : A \toA as fi(x) = bix+ci for each i. By condition (ii), fi(x) = fj(y) implies i = j and x = y; iterating this argument, we deduce that fi1(. . . fim(x) . . . ) = fj1(. . . fjm(x) . . . ) implies i1 = j1, . . . , im = jm and x = y. As an illustration, we shall consider the case b1 = b2 = b3 = 2 first. If a is large enough, then for any i1, . . . , im \in{1, 2, 3} we have fi1 ◦\cdot \cdot \cdot◦fim(a) \leq 2.1ma. However, we obtain 3m values in this way, so they cannot be all distinct if m is sufficiently large, a contradiction. In the general case, let real numbers di > bi, i = 1, 2 . . . , n, be chosen such that d1 + \cdot \cdot \cdot + dn > 1: for a large enough, fi(x) < dia for each x \geqa.

Also, let ki > 0 be arbitrary rational numbers with sum 1; denote by N0 the least common multiple of their denominators. Let N be a fixed multiple of N0, so that each kjN is an integer. Consider all combinations fi1 ◦\cdot \cdot \cdot ◦fiN of N functions, among which each fi appears exactly kiN times. There are FN = N! (k1N)!\cdot\cdot\cdot(knN)! such combinations, so they give FN distinct values when applied to a. On the other hand, fi1 ◦\cdot \cdot \cdot ◦fiN(a) \leq(dk1 1 \cdot \cdot \cdot dkn n )Na. Therefore (dk1 1 \cdot \cdot \cdot dkn n )Na \geqFN for all N, N0 | N. (1) It remains to find a lower estimate for FN. In fact, it is straightforward to verify that FN+N0/FN tends to QN0, where Q = 1/  kk1 1 \cdot \cdot \cdot kkn n

. Conse- quently, for every q < Q there exists p > 0 such that FN > pqN. Then (1) implies that

dk1 1 \cdot \cdot \cdot dkn n q N

p a for every multiple N of N0, and hence dk1 1 \cdot \cdot \cdot dkn n /q \geq1. This must hold for every q < Q, and so we have dk1 1 \cdot \cdot \cdot dkn n \geqQ, i.e., (k1d1)k1 \cdot \cdot \cdot (kndn)kn \geq1. However, if we choose k1, . . . , kn such that k1d1 = \cdot \cdot \cdot = kndn = u, then we must have u \geq1. Therefore d1 + \cdot \cdot \cdot + dn \leqk1 + \cdot \cdot \cdot + kn = 1, a contradiction.