Maths Olympiad Prep

Library / /45 of 60

, 2017

Combinatorics Difficulty 3.1 AMC 10/12 Prove it Canada

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,21,2 and 3. Row nn has the consecutive integers beginning at 1 and ending at the nthn^{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 9th9^{th} integer to be written is 5, and it appears at the end of Row 3. In general, after having completed nn rows, a total of n2n^2 integers have been written.

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

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 nn rows, n2n^2 integers have been written.

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

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

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

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

Row nn ends at the nthn^{th} odd integer.

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

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

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

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

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

The final integer written in Row 45 is the 45th^{th} odd integer, which is 2(45)1=892(45)-1=89.
The 2025th^{th} integer written in the table is 89, and so the 2017th^{th} integer written in the table is 20252017=82025-2017=8 less than 89, or 898=8189-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,31,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 nthn^{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 nn ends with the nthn^{th} odd integer, 2n12n-1, then when 2n1=972n-1=97, we get 2n=982n=98 and so n=49n=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 20048=152200-48=152 of the first 200 rows of the table.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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