Problem

Source: Italy MO 2023 P2

Tags: combinatorics



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.