Problem

Source:

Tags: number theory



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.