Maths Olympiad Prep

Library / /242 of 348

Number theory Difficulty 5.0 AIME, harder Find the answer

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

A number or a short expression. Spacing and $ signs are ignored.

Solution

We will work in base 11, so let x=def11x=\overline{\operatorname{def}}_{11} such that d>0d>0. Then, based on the first two conditions, we aim to find multiples of 5 between 10011100_{11} and 1000111000_{11}. We note that def11112d+11e+fd+e+f(mod5)\overline{d e f}_{11} \equiv 11^{2} \cdot d+11 \cdot e+f \equiv d+e+f \quad(\bmod 5) Hence, xx a multiple of 5 if and only if the sum of its digits is a multiple of 5 . Thus, we wish to find triples (d,e,f)(d, e, f) with elements in 0,1,2,,9,100,1,2, \cdots, 9,10 such that d+e+f0(mod5)d+e+f \equiv 0(\bmod 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 5 that would make d+e+f0(mod5)d+e+f \equiv 0(\bmod 5). Once the this value of ee is fixed, then there are two possibilities for ee unless e0(mod5)e \equiv 0(\bmod 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(\bmod 5) and 0<d<f(0<d<f( to account for the extra choice for the value of e)e). Note that the number of ways to choose 0<d<f0<d<f is just (102)\binom{10}{2} since any 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(\bmod 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 9 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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.