We say an integer $n$ is naoish if $n \geq 90$ and the second-to-last digit of $n$ (in decimal notation) is equal to $9$. For example, $10798$, $1999$ and $90$ are naoish, whereas $9900$, $2009$ and $9$ are not. Nino expresses 2020 as a sum: \[ 2020=n_{1}+n_{2}+\ldots+n_{k} \]where each of the $n_{j}$ is naoish. What is the smallest positive number $k$ for which Nino can do this?
Problem
Source: Thirty Third Irish Mathematical Olympiad 2020 P1/10
Tags: number theory, modular arithmetic, irmo
circlethm
20.07.2020 20:18
I claim the answer is $k = 8$. Solution Any naoish number is of the form $100m + 90 + n$ for integers $m, n$ with $0 \leq n \leq 9$. If our numbers are $$ n_1 = 100{m_1} + 90 + n_1, \quad n_2 = 100{m_2} + 90 + n_2, \quad \cdots \quad n_k = 100m_k + 90 + n_k, $$we get $$ 2020 = 100(m_1 + m_2 + \cdots + m_k) + 90k + (n_1 + n_2 + \cdots + n_k). $$Let $M = m_1 + \cdots + m_k$ and $N = n_1 + n_2 + \cdots + n_k$. Then $2020 = 100M + 90k + N$. We can bound $0 \leq n_i \leq 9$, so $0 \leq N \leq 9k$. Then, modulo 100 we have $$ 2020 \equiv 20 \equiv 90k + N \pmod{100}, $$and we work out the following table: Thus we can only have $90k + N \equiv 20 \pmod{100}$ if $k \geq 8$, so $k = 8$ is minimum. To show that there is a solution for $k = 8$, setting $n_1 = n_2 = \cdots = n_8 = 0$ and $m_1 = m_2 = \cdots = m_7 = 1$ and $m_8 = 6$ works.
thepsserby
21.07.2020 11:40
Notice that every naoish number is congruent to one of $\{-1, -2, -3, \cdots, -10\}$ modulo 100. Additionally, $2020\equiv -80\pmod{100}$. The greedy algorithm for getting to $-80$ using the fewest naoish numbers is clearly picking $-10$ as many times as possible first, and it's easy to see that this is optimal. This takes 8 steps, so we have a lower bound on the value of $k$. This bound can be achieved, for example by taking $n_i=90$ for $1\leq i\leq 7$ and $n_8=1390$, so the smallest value of $k$ is indeed 8.