Track / Stage 3 / 20 of 260 #500 of 2444

Problem 500

AMC 10/12, early questions

Combinatorics Difficulty 3.1 Prove it CEMC Hypatia · Canada · 2017

A list of integers is written in a table, row after row from left to right. Row 1 has the integer 1. Row 2 has the integers $1,2$ and 3. Row $n$ has the consecutive integers beginning at 1 and ending at the $n^{th}$ odd integer. The first four rows are given below.

Row 1: 1
Row 2: 1, 2, 3
Row 3: 1, 2, 3, 4, 5
Row 4: 1, 2, 3, 4, 5, 6, 7

In the table, the $9^{th}$ integer to be written is 5, and it appears at the end of Row 3. In general, after having completed $n$ rows, a total of $n^2$ integers have been written.

What is the 25 $^{th}$ integer written in the table and in which row does the 25 $^{th}$ integer appear?
What is the 100 $^{th}$ integer written in the table?
What is the 2017 $^{th}$ integer written in the table?
In how many of the first 200 rows does the integer 96 appear?

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.

Official solution

We complete Row 5 of the table, as shown.

Row 1: 1
Row 2: 1, 2, 3
Row 3: 1, 2, 3, 4, 5
Row 4: 1, 2, 3, 4, 5, 6, 7
Row 5: 1, 2, 3, 4, 5, 6, 7, 8, 9
$\vdots$

After having completed $n$ rows, $n^2$ integers have been written.

Therefore, after having completed 5 rows, $5^2=25$ integers have been written.

The 25 $^{th}$ integer written in the table is the last integer in Row 5, which is 9.

After having completed 10 rows, $10^2=100$ integers have been written in the table.

Therefore, the 100 $^{th}$ integer written in the table is the last integer in Row 10.

Row $n$ ends at the $n^{th}$ odd integer.

Beginning at 1, the first odd integer is $1=2(1)-1$ , the second odd integer is $3=2(2)-1$ , the third odd integer is $5=2(3)-1$ .

Beginning at 1, the $n^{th}$ odd integer is $2n-1$ (1 less than the $n^{th}$ even integer $2n$ ).

Row 10 ends at the $10^{th}$ odd integer, which is $2(10)-1=19$ .
Therefore, the 100 $^{th}$ integer written in the table is 19.
After completing 44 rows, $44^2=1936$ integers have been written in the table.

After completing 45 rows, $45^2=2025$ integers have been written in the table.

Therefore, the 2017 $^{th}$ integer written in the table is in Row 45.

The final integer written in Row 45 is the 45 $^{th}$ odd integer, which is $2(45)-1=89$ .
The 2025 $^{th}$ integer written in the table is 89, and so the 2017 $^{th}$ integer written in the table is $2025-2017=8$ less than 89, or $89-8=81$ .
Each row, after the first, contains all of the integers that were written in the previous row, followed by the next two consecutive integers.

For example, Row 3 contains all integers that were written in Row 2 (that is, $1,2,3$ ), followed by the next two consecutive integers, 4 and 5.

Therefore, the first time an integer is written in the table, it appears as the last integer in a row, or as the second last integer in a row.

Since each row ends at the $n^{th}$ odd integer, then the last integer in each row is odd, and the second last integer in each row is even.

The first time the integer 96 appears in the table, it is the second last integer written in a row (since 96 is even), and 97 is the last integer written in that same row.

Since Row $n$ ends with the $n^{th}$ odd integer, $2n-1$ , then when $2n-1=97$ , we get $2n=98$ and so $n=49$ .

That is, Row 49 ends with the integer 97 and so the second last integer written in Row 49 is 96.

Since 96 first appears in Row 49 of the table, then 96 appears in every row following Row 49 and does not appear in any row before Row 49.
Therefore, the integer 96 appears in $200-48=152$ of the first 200 rows of the table.

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