MathDB

Let

n

be a positive integer. Beto writes a list of

n

non-negative integers on the board. Then he performs a succession of moves (two steps) of the following type: First for each

i=1,2,...,n

, he counts how many numbers on the board are less than or equal to

i

. Let

a_i

be the number obtained for each

i=1,2,...,n

. Next, he erases all the numbers from the board and writes the numbers

a_1,a_2,...,a_n

. For example, if

n=5

and the initial numbers on the board are

0,7,2,6,2

, after the first move, the numbers on the board will bec

1,3,3,3,3

;after the second move they will be

1,1,5,5,5

, and so on.

a)

Show that, for every

n

and every initial configuration, there will come a time after which the numbers will no longer be modified when using this move.

b)

Find (as a function of

n

) the minimum value of

k

such that, for any initial configuration, the moves made from move number

k

will not change the numbers on the board.

Problem Statement