Maths Olympiad Prep

Library / /108 of 1394

Number theory Difficulty 4.7 AIME Find the answer United States

Problem:
A number is upwards if its digits in base 10 are nondecreasing when read from left to right. Compute the number of positive integers less than 10610^{6} that are both upwards and multiples of 11.

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

Solution

Solution:
For a number d5d4d3d2d1d0d_{5}d_{4}d_{3}d_{2}d_{1}d_{0} (allowing leading 0s) to be upwards and a multiple of 11, we must have
d5d4d3d2d1d0,d_{5} \leq d_{4} \leq d_{3} \leq d_{2} \leq d_{1} \leq d_{0},
d0d1+d2d3+d4d50(mod11).d_{0} - d_{1} + d_{2} - d_{3} + d_{4} - d_{5} \equiv 0 \pmod{11}.
Note that d0d1d_{0} - d_{1}, d2d3d_{2} - d_{3}, and d4d5d_{4} - d_{5} are all nonnegative. Thus,
0(d0d1)+(d2d3)+(d4d5)0 \leq (d_{0} - d_{1}) + (d_{2} - d_{3}) + (d_{4} - d_{5})
(d0d1)+(d1d2)+(d2d3)+(d3d4)+(d4d5)\leq (d_{0} - d_{1}) + (d_{1} - d_{2}) + (d_{2} - d_{3}) + (d_{3} - d_{4}) + (d_{4} - d_{5})
=d0d5= d_{0} - d_{5}
9.\leq 9.
Therefore,
(d0d1)+(d2d3)+(d4d5)=0,(d_{0} - d_{1}) + (d_{2} - d_{3}) + (d_{4} - d_{5}) = 0,
which can only occur when d0=d1d_{0} = d_{1}, d2=d3d_{2} = d_{3}, and d4=d5d_{4} = d_{5}, i.e. the number is of the form aabbccaabbcc. We can easily verify that all numbers of the form aabbccaabbcc for digits abca \leq b \leq c satisfy our conditions, so we simply have to count them.
There are (123)=220\binom{12}{3} = 220 such triples of digits (a,b,c)(a,b,c). However, one of these triples is (0,0,0)(0,0,0), which corresponds to the number 0. Thus our answer is 2201=219220 - 1 = 219.

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.