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
Source: Italy MO 2023 P2
Tags: combinatorics
07.05.2023 19:06
$a)$ Notice that after $2$ moves $n$ will be written on the board and there will be no number bigger than $n$ so we can kinda proceed by induction I'm to lazy to write up. Anyways we should get that max amount of moves is less than or equal $2n$ $b)$ Construction for $2n$ is all zeroes.
07.05.2023 19:09
We claim that the process eventually ends in $1,2,\ldots,n$ in $2n$ moves. Note that if the process reaches this point, it indeed terminates. We induct on $n$: Base Case. $n=1$. In this case, if the number he starts with is at most $1$, it becomes $1$. Otherwise, it becomes a $0$, which on the next move becomes a $1$. Induction Hypothesis. Assume it is true for all $n\leq m$. We show it is true for $n=m+1$. Induction Step. Note that after the first move, all numbers vacuously are at most $n$ (by the definition). Hence, after the second move, the last number is indeed $n$. Note that any further operations leave this unchanged (as the numbers are always at most $n$), and furthermore this doesn't affect any of the other numbers. Thus, we can ignore it after the second move. By the induction hypothesis, after performing $2n-2$ more moves, we get $1,2,\ldots,n-1$. However, we already know $n$ is the last number, which means that we have $1,2,\ldots,n$ in $2n$ moves. Now, to finish, it suffices to show a construction. We claim $n+1,n+1\ldots,n+1$ works. Base Case. $n=1$. In this case, clearly $2\mapsto0\mapsto1$. Induction Hypothesis. Assume it is true for all $n\leq m$. We show it is true for $n=m+1$. Induction Step. After one move, the board goes to all zeroes. After that, it goes to $n,n,\ldots,n$. Thus, by the induction hypothesis and the idea in the previous induction, the last number doesn't change, and the rest takes $2n-2$ moves to bring to $1,2,\ldots,n-1$, which means we require $2n$ moves.