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
Source:
Tags: number theory
11.08.2024 14:35
Call a configuration good if it produces itself under the operation described above. We claim that we can achieve the good configuration in at most $2n$ steps. For the construction, consider the sequence, $(1,n+1, \cdots, n+1)$, where there are $n-1$ terms which are $n+1$. Claim: The only good sequence if $(1,2,\cdots, n)$ Proof: We will prove this by induction on the terms. Firstly, we will prove that the first term has to be $1$. Note that if the first term remains unchanged under the operation, then the term cannot be greater than $1$, otherwise the term under the operation will get changed to $0$. Also, the term cannot be $0$, otherwise it gets changed to $1$. This proves the base case. Now assume that the first $k$ terms of the sequence are $1,2,\cdots,k$ respectively. Let the $(k+1)$th term be $t$. If $t>k+1$, then we reach a contradiction by the same argument as above. If $t<k+1$, then again we reach a contradiction by the same logic as above. This ends the proof. Now we will try to examine how many steps it takes to reach the good configuration. Note that by the end of move $2$, the last term in the sequence has to be $n$. This is because in the first move itself, all the terms will change to something $\le n$, because there can be at most $n$ terms in the sequence. Now we claim by induction that by the move number $2k$, we have that the last terms of the sequence looks something like this, $(\cdots, n+1-k,n+2-k, \cdots, n)$. To prove this, it is enough to prove that it takes at most 2 steps to increase 1 more term at the end of the sequence to the form written above. To prove this, suppose we have the sequence something like this, $(a_1, a_2,\cdots, a_{t-1}, t, t+1, \cdots , n)$. Note that in the next step, no matter the values of $a_i$ for any $i<t$, all the first $t-1$ terms will be changed to something $<t$. This is because there are already $n-t+1$ terms which are greater than $t-1$. Thus, after the second step, we are sure that there are exactly $t-1$ terms which are $\le t-1$, and thus, the $t-1$th term in the sequence will become $t-1$. By induction, we are done.