IMO 1998 SL 23

Origin: BLR

Problem

Let n be an integer greater than 2. A positive integer is said to be attainable if it is 1 or can be obtained from 1 by a sequence of operations with the following properties: (i) The first operation is either addition or multiplication. (ii) Thereafter, additions and multiplications are used alternately. (iii) In each addition one can choose independently whether to add 2 or n. (iv) In each multiplication, one can choose independently whether to mul- tiply by 2 or by n. A positive integer that cannot be so obtained is said to be unattainable. (a) Prove that if n \geq9, there are infinitely many unattainable positive integers. (b) Prove that if n = 3, all positive integers except 7 are attainable.

Solution

(a) If n is even, then every odd integer is unattainable. Assume that n \geq9 is odd. Let a be obtained by addition from some b, and b from c by multiplication. Then a is 2c + 2, 2c + n, nc + 2, or nc + n, and is in every case congruent to 2c + 2 modulo n −2. In particular, if a \equiv−2 (mod n −2), then also b \equiv−4 and c \equiv−2 (mod n −2). Now consider any a = kn(n−2)−2, where k is odd. If it is attainable, but not divisible by 2 or n, it must have been obtained by addition. Thus all predecessors of a are congruent to either −2 or −4 (mod n −2), and none of them equals 1, a contradiction. (b) Call an attainable number addy if the last operation is addition, and multy if the last operation is multiplication. We prove the following claims by simultaneous induction on k: (1) n = 6k is both addy and multy; (2) n = 6k + 1 is addy for k \geq2; (3) n = 6k + 2 is addy for k \geq1; (4) n = 6k + 3 is addy; (5) n = 6k + 4 is multy for k \geq1; (6) n = 6k + 5 is addy. The cases k \leq1 are easily verified. For k \geq2, suppose all six state- ments hold up to k −1.

Since 6k −3 is addy, 6k is multy. Next, 6k−2 is multy, so both 6k = (6k−2)+2 and 6k+1 = (6k−2)+3 are addy. Since 6k is multy, both 6k + 2 and 6k + 3 are addy. Number 6k + 4 = 2 \cdot (3k + 2) is multy, because 3k + 2 is addy (being either 6l + 2 or 6l + 5). Finally, we have 6k + 5 = 3 \cdot (2k + 1) + 2. Since 2k + 1 is 6l + 1, 6l + 3, or 6l + 5, it is addy except for 7. Hence 6k + 5 is addy except possibly for 23. But 23 = ((1 \cdot 2 + 2) \cdot 2 + 2) \cdot 2 + 3 is also addy. This completes the induction. Now 1 is given and 2 = 1 \cdot 2, 4 = 1 + 3. It is easily checked that 7 is not attainable, and hence it is the only unattainable number.