Maths Olympiad Prep

Library / /25 of 82

Number theory Difficulty 4.8 AIME Find the answer United States

Problem:
Find the number of integers xx such that the following three conditions all hold:
- xx is a multiple of 55
- 121<x<1331121 < x < 1331
- When xx is written as an integer in base 1111 with no leading 00s (i.e. no 00s at the very left), its rightmost digit is strictly greater than its leftmost digit.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:
We will work in base 1111, so let x=def11x = \overline{def}_{11} such that d>0d > 0. Then, based on the first two conditions, we aim to find multiples of 55 between 10011100_{11} and 1000111000_{11}. We note that
def11=112d+11e+fd+e+f(mod5) \overline{def}_{11} = 11^2 \cdot d + 11 \cdot e + f \equiv d + e + f \pmod{5}
Hence, xx is a multiple of 55 if and only if the sum of its digits is a multiple of 55. Thus, we wish to find triples (d,e,f)(d, e, f) with elements in 0,1,2,,9,100, 1, 2, \ldots, 9, 10 such that d+e+f0(mod5)d + e + f \equiv 0 \pmod{5} and 0<d<f0 < d < f.

Note that if we choose dd and ff such that d<fd < f, there is exactly one value of ee modulo 55 that would make d+e+f0(mod5)d + e + f \equiv 0 \pmod{5}. Once this value of ee is fixed, then there are two possibilities for ee unless e0(mod5)e \equiv 0 \pmod{5}, in which case there are three possibilities. Thus, our answer is twice the number of ways to choose dd and ff such that 0<d<f0 < d < f plus the number of ways to choose dd and ff such that d+f0(mod5)d + f \equiv 0 \pmod{5} and 0<d<f0 < d < f (to account for the extra choice for the value of ee).

Note that the number of ways to choose 0<d<f0 < d < f is just (102)\binom{10}{2} since any choice of two digits yields exactly one way to order them. The number of ways to choose d+f0(mod5)d + f \equiv 0 \pmod{5} and 0<d<f0 < d < f can be found by listing: (d,f)=(1,4),(1,9),(2,3),(2,8),(3,7),(4,6),(5,10),(6,9),(7,8)(d, f) = (1,4), (1,9), (2,3), (2,8), (3,7), (4,6), (5,10), (6,9), (7,8), for 99 such pairings.

Hence, the total is 2(102)+9=992 \binom{10}{2} + 9 = 99 possibilities for xx.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.