Olympiad Maths Prep

Track / Stage 5 / 206 of 400 #806 of 2000

Problem 806

AIME late
Combinatorics Difficulty 5.5 Find the answer

As shown in the figure, a rectangular table has 8 columns. Numbers 1,2,1, 2, \cdots are filled into the table in a certain order (filled from left to right, and when a row is full, move to the next row, still filling from left to right). A student first colors the cell with the number 1 black, then skips 1 cell, and colors the cell with the number 3 black; then skips 2 cells, and colors the cell with the number 6 black; then skips 3 cells, and colors the cell with the number 10 black. This continues until every column contains at least one black cell (no more coloring after that). Therefore, the number in the last black cell he colored is \qquad

Official solution

(Method One)
The 1st blackened cell is 1;
The 2nd blackened cell is 3=1+23=1+2;
The 3rd blackened cell is 6=1+2+36=1+2+3;
The 4th blackened cell is 10=1+2+3+410=1+2+3+4;
\qquad
And so on, the nn-th blackened cell is 1+2++n1+2+\cdots+n.
Thus, we can get the blackened cells in sequence as 11(mod8),1+2=33(mod8)1 \equiv 1(\bmod 8), 1+2=3 \equiv 3(\bmod 8),
1+2+3=66(mod8),1+2+3+4=102(mod8)1+2++5=157(mod8),1+2++6=215(mod8)1+2++7=284(mod8),1+2++8=364(mod8)1+2++9=455(mod8),1+2++10=557(mod8)1+2++11=662(mod8),1+2++12=786(mod8)1+2++13=913(mod8),1+2++14=1051(mod8)1+2++15=1200(mod8) \begin{array}{l} 1+2+3=6 \equiv 6(\bmod 8), 1+2+3+4=10 \equiv 2(\bmod 8) \\ 1+2+\cdots+5=15 \equiv 7(\bmod 8), \quad 1+2+\cdots+6=21 \equiv 5(\bmod 8) \\ 1+2+\cdots+7=28 \equiv 4(\bmod 8), \quad 1+2+\cdots+8=36 \equiv 4(\bmod 8) \\ 1+2+\cdots+9=45 \equiv 5(\bmod 8), \quad 1+2+\cdots+10=55 \equiv 7(\bmod 8) \\ 1+2+\cdots+11=66 \equiv 2(\bmod 8), \quad 1+2+\cdots+12=78 \equiv 6(\bmod 8) \\ 1+2+\cdots+13=91 \equiv 3(\bmod 8), \quad 1+2+\cdots+14=105 \equiv 1(\bmod 8) \\ 1+2+\cdots+15=120 \equiv 0(\bmod 8) \end{array}

Up to this point, the numbers that are mod8\bmod 8 with remainders 070 \sim 7 have all appeared; that is, every column contains at least one black cell;
The number in the last blackened cell is 120.
(Method Two)
The 1st blackened cell is 1;
The 2nd blackened cell is 3=1+23=1+2;
The 3rd blackened cell is 6=1+2+36=1+2+3;
The 4th blackened cell is 10=1+2+3+410=1+2+3+4;
\qquad
And so on, the nn-th blackened cell is 1+2++n1+2+\cdots+n.
The blackened cells mod8\bmod 8 have remainders in sequence as 1,3,6,2,7,5,4,1,3,6,2, 7, 5, 4, \ldots
Up to this point, except for mod8\bmod 8 with remainder 0, all other mod8\bmod 8 with remainders 171 \sim 7 have already appeared;
Therefore, we only need to consider 1+2++n0(mod8)1+2+\cdots+n \equiv 0(\bmod 8);
81+2++n=12n(n+1)16n(n+1) \begin{array}{l} 8 \left\lvert\, 1+2+\cdots+n=\frac{1}{2} n(n+1)\right. \\ 16 \mid n(n+1) \end{array}

Since nn and n+1n+1 are coprime;
Thus, 16n16 \mid n or 16n+116 \mid n+1;
We hope that nn is as small as possible;
Then take n+1=16n+1=16;
n=15 n=15

Thus, the number in the last blackened cell is 1+2++15=(1+15)×15÷2=1201+2+\cdots+15=(1+15) \times 15 \div 2=120.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.