MathDB

Let

n

be a positive integer. On a blackboard, Bobo writes a list of

n

non-negative integers. He then performs a sequence of moves, each of which is as follows:
-for each

i = 1, . . . , n

, he computes the number

a_i

of integers currently on the board that are at most

i

,
-he erases all integers on the board,
-he writes on the board the numbers

a_1, a_2,\ldots , a_n

.
For instance, if

n = 5

and the numbers initially on the board are

0, 7, 2, 6, 2

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

1, 3, 3, 3, 3

, after the second they will be

1, 1, 5, 5, 5

, and so on.
(a) Show that, whatever

n

and whatever the initial configuration, the numbers on the board will eventually not change any more.
(b) As a function of

n

, determine the minimum integer

k

such that, whatever the initial configuration, moves from the

k

-th onwards will not change the numbers written on the board.

Problem Statement