Question

Solution to: There is a row of 1000 integers. There is a second row below, which is constructed as follows. Under each number a of the first row, there is a positive integer f(a) such that f(a) equals the number of occurrences of a in the first row. In the same way, we get the 3rd row from the 2nd row, and so on. Prove that, finally, one of the rows is identical to the next row.

Answer 1

The first thing to recognize is that if 2 consecutive rows have the same number of terms, the second term has all 1's

Answer 2

If this is true, the row after the row with all ones will contain a single number

Answer 3

then the next row will contain 1

Answer 4

then the row after that will contain 1

Answer 5

so:

Answer 6

Now, because a row can't contain any 0's, every row must be smaller or the same size as the previous one

Answer 7

So, that means that either the row will stay the same size, in which case we have already proven that it eventually goes to 1, or they will get smaller and smaller

Answer 8

\[\in R_1 = 1000\]
\[\in R_2 \le 1000\]
\[\in R_3 \le 999\]
...
\[\in R_{1001} \le 1\]

Answer 9

You can't have 0 elements in a row, so:
\[\in R_{1001} = 1\]

Answer 10

therefore:

Answer 11

QED