IT-CESENATICO 2023 Problem 2

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.