Prove: Row of 1000 Integers Becomes Identical Over Time

[sachinism]

A row contains 1000 integers

The second row is formed by writing under each integer, the number of times it occurs in the first row.The third row is now constructed by writing under each number in the 2nd row, the number of times it occurs in the 2nd row.This is process is continued

Prove that at some point, one row becomes identical to the next.

 

[Petr Mugver]

From the second row on, if an integer n is present in the row, then it is present at least n times, because it is the number of times some other number is present in the previous row. If all the different n's are present exactly n times in a row, then all the following rows will be the same (for example (223334444) -> (223334444) -> (223334444) -> ...). If this is not the case, then there must be some n that is present more than n times. This means that going from one row to the next one there are two possibilities: either the row remains the same, or at least some number of the row has a bigger number below it. Since the maximum n that can be present in a row can't be bigger than 1000, this sequence must terminate, and at some point the row doesn't change anymore.

 

[sachinism]

nice one man