Maths Olympiad Prep

Track / Stage 5 / 233 of 400 #1313 of 2444

Problem 1313

AIME late
Algebra Difficulty 5.4 Prove it Irish Mathematical Olympiad · Ireland

We say an integer nn is naoish if n90n \ge 90 and the second-to-last digit of nn (in decimal notation) is equal to 99. For example, 1079810798, 19991999 and 9090 are naoish, whereas 99009900, 20092009 and 99 are not. Nino expresses 20202020 as a sum:
2020=n1+n2++nk 2020 = n_{1} + n_{2} + \dots + n_{k}
where each of the njn_j is naoish.
What is the smallest positive number kk for which Nino can do this?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solutions — 2

Solution 1

Equivalently, nn is naoish iff n=100pqn = 100p - q where p1p \ge 1 is an integer and 1q101 \le q \le 10. Decomposing each njn_j in this way, we have:
2020=100(p1+p2++pk)q1q2qk. 2020 = 100(p_1 + p_2 + \dots + p_k) - q_1 - q_2 - \dots - q_k.
In particular, 1002020+q1+q2++qk100 \mid 2020 + q_1 + q_2 + \dots + q_k. The next multiple of 100100 above 20202020 is 23002300, so 2020+q1+q2++qk23002020 + q_1 + q_2 + \dots + q_k \ge 2300. As each qj10q_j \le 10, this implies
k2300202010=8. k \ge \frac{2300 - 2020}{10} = 8.
It is easy to find a solution that works with k=8k=8. One example is 13901390 (once) and 9090 (seven times).

Solution 2

Let niai(mod10)n_i \equiv a_i \pmod{10} with 0ai<100 \le a_i < 10. The second-to-last digit of n1++nkn_1 + \dots + n_k is the last digit of 9k+c9k + c, where cc is the total carry of the addition. As a1+a2++ak9k<10ka_1 + a_2 + \dots + a_k \le 9k < 10k the total carry cc satisfies 0ck10 \le c \le k-1. This means that we can write
9k+c=10k(kc)=10ki 9k + c = 10k - (k - c) = 10k - i
for some 1ik1 \le i \le k. To get a sum of 20202020, we need to have 10ki2(mod10)10k - i \equiv 2 \pmod{10}, i.e. i8(mod10)i \equiv 8 \pmod{10} and, in particular, i8i \ge 8. From iki \le k we obtain k8k \ge 8.
It is easy to find a solution that works with k=8k = 8. One example is 13901390 (once) and 9090 (seven times).

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