IMO 1994 SL N7

Origin: GBR | Category: Number Theory

Problem

A wobbly number is a positive integer whose digits in base 10 are alternately nonzero and zero, the units digit being nonzero. Determine all positive integers that do not divide any wobbly number.

Solution

A multiple of 10 does not divide any wobbly number. Also, if 25 | n, then every multiple of n ends with 25, 50, 75, or 00; hence it is not wobbly. We now show that every other number n divides some wobbly number. (i) Let n be odd and not divisible by 5. For any k \geq1 there exists l such that (10k −1)n divides 10l −1, and thus also divides 10kl −1. Consequently, vk = 10kl−1 10k−1 is divisible by n, and it is wobbly when k = 2 (indeed, v2 = 101 . . . 01). If n is divisible by 5, one can simply take 5v2 instead. (ii) Let n be a power of 2. We prove by induction on m that 22m+1 has a wobbly multiple wm with exactly m nonzero digits. For m = 1, take w1 = 8. Suppose that for some m \geq1 there is a wobbly wm = 22m+1dm. Then the numbers a \cdot 102m + wm are wobbly and divisible by 22m+1 when a \in{2, 4, 6, 8}. Moreover, one of these numbers is divisible by 22m+3. Indeed, it suffices to choose a such that a 2 + dm is divisible by 4. This proves the induction step. (iii) Let n = 2mr, where m \geq1 and r is odd, 5 ∤r. Then v2mwm is wobbly and divisible by both 2m and r (using notation from (i), r | v2m).