Maths Olympiad Prep

Library / /309 of 310

, 2023

Number theory Difficulty 4.8 AIME Find the answer Canada

For each positive integer nn,
define s(n)s(n) to equal the sum of the
digits of nn. For example, s(2023)=2+0+2+3s(2023) = 2 + 0 + 2 + 3. The number of
integers nn with 100n999100 \leq n \leq 999 and 7s(n)117 \leq s(n) \leq 11 is SS. What is the integer formed by the
rightmost two digits of SS?

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

Solution

We write an integer nn with
100n999100 \leq n \leq 999 as n=100a+10b+cn = 100a + 10b + c for some digits aa, bb
and cc.

That is, nn has hundreds digit aa, tens digit bb, and ones digit cc.

For each such integer nn, we have
s(n)=a+b+cs(n) = a + b + c.

We want to count the number of such integers nn with $7 \leq
a+b+c \leq 11$.

When 100n999100 \leq n \leq 999, we know
that 1a91 \leq a \leq 9 and 0b90 \leq b \leq 9 and 0c90 \leq c \leq 9.

First, we count the number of nn
with a+b+c=7a+b+c=7.

If a=1a=1, then b+c=6b+c=6 and there are 7 possible pairs of
values for bb and cc. These pairs are $(b,c) =
(0,6),(1,5),(2,4),(3,3),(4,2),(5,1),(6,0)$.

If a=2a=2, then b+c=5b+c=5 and there are 6 possible pairs of
values for bb and cc.

Similarly, when a=3,4,5,6,7a=3, 4, 5, 6, 7,
there are 5, 4, 3, 2, 1 pairs of values, respectively, for bb and cc.

In other words, the number of integers nn with a+b+c=7a+b+c=7 is equal to 7+6+5+4+3+2+1=287+6+5+4+3+2+1=28.

Using a similar process, we can determine that the number of such
integers nn with s(n)=8s(n) = 8 is 8+7+6+5+4+3+2+1=368+7+6+5+4+3+2+1=36 and the number of such
integers nn with s(n)=9s(n) = 9 is 9+8+7+6+5+4+3+2+1=459+8+7+6+5+4+3+2+1=45.

We have to be more careful counting the number of integers nn with $s(n) =
10and and s(n) = 11$, because
none of the digits can be greater than 9.

Consider the integers nn with a+b+c=10a+b+c=10.

If a=1a=1, then b+c=9b+c=9 and there are 10 possible pairs of
values for bb and cc. These pairs are (b,c)=(0,9),(1,8),,(8,1),(9,0)(b,c)=(0,9),(1,8),\ldots,(8,1),(9,0).

If a=2a=2, then b+c=8b+c=8 and there are 9 possible pairs of
values for bb and cc.

As aa increases from 1 to 9, we find
that there are 10+9+8+7+6+5+4+3+2=5410+9+8+7+6+5+4+3+2=54 such integers nn.

(Note that when a=9a=9, we have b+c=1b+c=1 and there are 2 pairs of values for
bb and cc.)

Finally, we consider the integers nn
with a+b+c=11a+b+c=11.

If a=1a=1, then b+c=10b+c=10 and there are 9 possible pairs of
values for bb and cc. These pairs are (b,c)=(1,9),(2,8),,(8,2),(9,1)(b,c)=(1,9),(2,8),\ldots,(8,2),(9,1).

If a=2a=2, then b+c=9b+c=9 and there are 10 possible pairs of
values for bb and cc.

If a=3a=3, then b+c=8b+c=8 and there are 9 possible pairs of
values for bb and cc.

Continuing in this way, we find that there are 9+10+9+8+7+6+5+4+3=619+10+9+8+7+6+5+4+3 = 61 such integers
nn.

Having considered all cases, we see that the number of such integers
nn is S=28+36+45+54+61=224S = 28 + 36 + 45 + 54 + 61 = 224 The rightmost two digits of
SS are 24.

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

Source: CEMC, University of Waterloo, licensed CC-BY-NC-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.