Maths Olympiad Prep

Library / /106 of 520

Combinatorics Difficulty 5.2 AIME, harder Find the answer

6. A 100×100100 \times 100 board is filled with numbers. In the bottom-left cell, there is a 0. From any other cell VV, we consider a path from the bottom-left cell to cell VV, where you can only move right or up, not diagonally. If you add up all the numbers you encounter along the way and then add 1 for each step you have taken, you get the number that is in cell VV.

!
In the partial board shown above, the number 15 is obtained from (0+1+3+7)+4=15(0+1+3+7)+4=15.

What is the last digit of the number in the top-right cell of the 100×100100 \times 100 board?
A) 1
B) 3
C) 5
D) 7
E) 9

Multiple choice: answer with the letter of the option you want.

Solution

A6. \quad B) 3 We consider a route from the bottom-left square to the top-right square. This route consists of 99+99=19899+99=198 steps. The numbers on the squares along this route we call a0,a1,a2,,a198a_{0}, a_{1}, a_{2}, \ldots, a_{198}.

We know that a0=0,a1=1a_{0}=0, a_{1}=1 and a2=3a_{2}=3. To calculate the next number, a3a_{3}, we need to add the numbers a0,a1a_{0}, a_{1} and a2a_{2}, and add 1 for each step we take. We find that a3=(a0+1)+(a1+1)+(a2+1)=7a_{3}=\left(a_{0}+1\right)+\left(a_{1}+1\right)+\left(a_{2}+1\right)=7. To then calculate the next number, which is a4a_{4}, we need to take the same sum and add a3+1a_{3}+1. Thus, we see that a4=a3+(a3+1)=15a_{4}=a_{3}+\left(a_{3}+1\right)=15. In general, we see that

ak+1=(a1+1)++(ak1+1)+(ak+1)=ak+(ak+1)=2ak+1 a_{k+1}=\left(a_{1}+1\right)+\ldots+\left(a_{k-1}+1\right)+\left(a_{k}+1\right)=a_{k}+\left(a_{k}+1\right)=2 a_{k}+1

If we only look at the last digits, we will notice that they repeat; after the first 0, we get: 1,3,7,5,1,3,7,51,3,7,5,1,3,7,5, and so on. It is easy to explain why this regularity occurs. The last digit of ak+1a_{k+1} depends only on the last digit of aka_{k}. For this reason, this regularity continues up to and including a198a_{198}. Therefore, the numbers a2,a6,a10,a14,,a198a_{2}, a_{6}, a_{10}, a_{14}, \ldots, a_{198} all end in 3.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.