Estonian Mathematical Olympiad

Firstly, we prove by induction that if $f$ is a regular function then $f(i)<i$ for each positive argument $i$. For that, assume that the claim holds for all smaller arguments. We have $f(i)\in \{i-1,f(i-1),f(f(i-1)),\dots \}$ by regularity. By the induction hypothesis and the assumption $f(0)=0$, we have $i-1\ge f(i-1)\ge f(f(i-1))\ge \dots$. Hence $f(i)<i$ indeed.

Now we prove by induction on $n$ that the information given to Miku by Juku uniquely determines the regular function. If $n=0$ then only one regular function exists whence the claim holds trivially. Assume in the rest that $n>0$ and that the claim holds for all smaller numbers. As $f(1)<1$ by the lemma proven in the beginning, we must have $f(1)=0$.

Let $k$ be the largest number in $\{0,1,\dots ,n\}$ such that $f(k)=0$. Then $k\ge 1$ since $f(1)=0$. By the lemma proven in the beginning, $0<i\le k$ always implies $f(i)<i$ and hence also $f(i)<k$. On the other hand, $k<i\le n$ implies $f(i)\ge k$. Indeed, assume that $f(j)\ge k$ for each $j=k+1,\dots ,i-1$; let exactly $s$ initial members of the sequence $i-1,f(i-1),f(f(i-1)),\dots$ be larger than or equal to $k$. Then the $s$th member must be $k$ because otherwise the $s$ initial members would all be in $\{k+1,\dots ,i-1\}$, implying that the next member would be larger than or equal to $k$, too. Thus the next member is $f(k)$ which equals 0 and all following members are 0, too. But as $f(i)\ne 0$, we must have $f(i)\ge k$. We can conclude that the number of arguments $i$ such that $f(i)\ge k$ is exactly $n-k$.

Now if $0<l<k$ then similarly to what we did before we can prove that $0<i\le l$ always implies $f(i)<l$. But among the arguments $i$ such that $l<i\le n$, there is $k$ for which $f(k)=0$. Thus the number of arguments $i$ such that $f(i)\ge l$ is less than $n-l$. Consequently, $k$ is the least positive integer for which the number of arguments $i$ such that $f(i)\ge k$ is $n-k$. According to this property, Miku can determine $k$.

Restricting $f$ to $\{0,1,\dots ,k-1\}$, all conditions of regularity hold. Hence, by the induction hypothesis, Miku can determine $f(1),\dots ,f(k-1)$. Note that if we forget about arguments $1,\dots ,k$ and decrease the other argument-value pairs of $f$ by exactly $k$, the conditions of regularity again hold. Hence, by the induction hypothesis, Miku can also determine $f(k+1),\dots ,f(n)$. Consequently, Miku can determine the values of $f$ at all its arguments.

---

Alternative solution.

We start like in Solution 1 by showing that if $f$ is regular then $f(i)<i$ for every positive argument $i$.

Now we prove the following lemma: Whenever $0<k\le i\le n$, either $f(i)\ge k$ or $f(i)\le f(k)$. To this end, fix $k$ and proceed by induction on $i$. The base case $i=k$ is trivial. Assume now that $i>k$ and, for every $i^{\prime }$ such that $k\le i^{\prime }<i$, either $f(i^{\prime })\ge k$ or $f(i^{\prime })\le f(k)$. By regularity, $f(i)$ is a term in the sequence $i-1,f(i-1),f(f(i-1)),\dots$. This sequence decreases until it reaches zero. Let the sequence contain exactly $s$ terms larger than or equal to $k$. As all terms are less than $i$, the induction hypothesis implies that the term number $s+1$ is at least $k$ (which is impossible by the choice of $s$) or at most $f(k)$. Then the following terms are also at most $f(k)$. Thus $f(i)$ must be either at least $k$ or at most $f(k)$.

Miku can determine Juku's regular function as follows. Let Miku put the numbers of repetitions of values in the order of decreasing value (i.e., the number of repetitions of $n$ first, then the number of repetitions of $n-1$, etc.). Every time a number of repetitions of some value $k$ equals a positive number $a$, let Miku define the value of $f$ on the least $a$ arguments greater than $k$ where the value is not defined so far to be $k$. We show that this results in the only possible regular function with the given numbers of repetitions of values. Suppose the contrary. Let $k$ be the largest value of the function for which a divergence appears. We know that all arguments on which the function obtains the value $k$ must be larger than $k$. Hence there exist $i^{\prime }$ and $i$ such that $k<i^{\prime }<i$, $f(i)=k$ and $f(i^{\prime })\ne k$. Since all values greater than $k$ are already assigned by the algorithm and they are correct by the choice of $k$, the only option is $f(i^{\prime })<k$. But then the lemma proven above implies either $f(i)\ge i^{\prime }>k$ or $f(i)\le f(i^{\prime })<k$, contradiction. Consequently, no divergence between the actual function and the one constructed by the algorithm can arise. Hence Miku can always determine Juku's function.

---

Alternative solution.

Like in Solution 1, we show that if $f$ is regular then $f(i)<i$ for every positive argument $i$. Like in Solution 2, we show that $0<k\le i\le n$ always implies either $f(i)\ge k$ or $f(i)\le f(k)$.

Miku can determine Juku's regular function as follows. Let Miku start by defining $f(0)=0,f(1)=0$. These are clearly the only options. Whenever $f(0),f(1),\dots ,f(i-1)$ have been fixed, let Miku define $f(i)$ to be the largest number among $0,1,\dots ,i-1$ whose presumed number of occurrences is not achieved yet. As $f(i)<i$, such number must exist. We show now that this definition is the only possible. Suppose the contrary. Let the first divergence arise at the definition of $f(i)$. Let the algorithm assign the value $k$ to it; then actually $f(i)<k<i$, because the algorithm finds the largest number less than $i$ that can be used. But since the value $k$ is not yet saturated, there must exist $i^{\prime }$ such that $i^{\prime }>i$ and $f(i^{\prime })=k$. By the lemma proven at the beginning of the solution, either $f(i^{\prime })\ge i>k$ or $f(i^{\prime })\le f(i)<k$, contradiction. Hence Miku can always determine Juku's function.

Now we prove by induction on $n$ that the information given to Miku by Juku uniquely determines the regular function. For $n=0$, there exists only one regular function, whence the claim holds. Assume in the following that $n>0$ and the claim holds for $n-1$. Let $a_0,a_1,\dots ,a_n$ be the numbers of repetitions of values of $f$. By the property proven at the beginning of the solution, $n$ cannot occur among the values of $f$, hence $a_n=0$. Let $l$ be the least positive integer such that $a_l=0$. As $a_{l-1}>0$, we have $f(l)=l-1$ by the above. Define $b_0,b_1,\dots ,b_{n-1}$ by $$b_i=\{\begin{array}{ll}{a}_i,& \text{if }i<l-1,\\ a_i-1,& \text{if }i=l-1,\\ a_{i+1},& \text{if }i\ge l.\end{array}$$ Note that $b_0,b_1,\dots ,b_{n-1}$ are the numbers of repetitions of values of function $g$ defined by $$g(i)=\{\begin{array}{ll}f(i),& \text{if }i<l,\\ f(i+1),& \text{if }f(i+1)<l\le i,\\ f(i+1)-1,& \text{if }l<f(i+1).\end{array}$$ In other words, function $g$ is obtained from $f$ by removing the argument-value pair $(l,l-1)$ (this removes the only occurrence of $l$ in these pairs) and decreasing the numbers $l+1,\dots ,n$ by 1 in all other pairs. It is easy to check that regularity of $f$ implies regularity of $g$. By the induction hypothesis, $g$ is the only regular function with numbers of repetitions of values are $b_0,b_1,\dots ,b_{n-1}$. But $f$ can be defined in terms of $g$: $$f(i)=\{\begin{array}{ll}g(i),& \text{if }i<l,\\ l-1,& \text{if }i=l,\\ g(i-1),& \text{if }g(i-1)<l<i,\\ g(i-1)+1,& \text{if }l\le g(i-1).\end{array}$$ In other words, add the argument-value pair $(l,l-1)$ and increase all numbers $l,\dots ,n-1$ by 1 in other pairs. This completes the solution.

---

Alternative solution.

Like in Solution 1, we show that if $f$ is regular then $f(i)<i$ for every positive argument $i$. Next we show that $f(i)=i-1$ whenever $f$ is regular and $i-1$ occurs among the values of $f$. Indeed, let $k$ be the least positive integer such that $f(k)=i-1$; by the above, $k\ge i$. By regularity, $i-1$ occurs in the sequence $k-1,f(k-1),f(f(k-1)),\dots$. If $i-1=k-1$ then $f(i)=i-1$, otherwise $i-1$ can be represented in the form $f(j)$ where $j\le k-1<k$, which contradicts the choice of $k$.

Now we prove by induction on $n$ that the information given to Miku by Juku uniquely determines the regular function. For $n=0$, there exists only one regular function, whence the claim holds. Assume in the following that $n>0$ and the claim holds for $n-1$. Let $a_0,a_1,\dots ,a_n$ be the numbers of repetitions of values of $f$. By the property proven at the beginning of the solution, $n$ cannot occur among the values of $f$, hence $a_n=0$. Let $l$ be the least positive integer such that $a_l=0$. As $a_{l-1}>0$, we have $f(l)=l-1$ by the above. Define $b_0,b_1,\dots ,b_{n-1}$ by $$b_i=\{\begin{array}{ll}{a}_i,& \text{if }i<l-1,\\ a_i-1,& \text{if }i=l-1,\\ a_{i+1},& \text{if }i\ge l.\end{array}$$ Note that $b_0,b_1,\dots ,b_{n-1}$ are the numbers of repetitions of values of function $g$ defined by $$g(i)=\{\begin{array}{ll}f(i),& \text{if }i<l,\\ f(i+1),& \text{if }f(i+1)<l\le i,\\ f(i+1)-1,& \text{if }l<f(i+1).\end{array}$$ In other words, function $g$ is obtained from $f$ by removing the argument-value pair $(l,l-1)$ (this removes the only occurrence of $l$ in these pairs) and decreasing the numbers $l+1,\dots ,n$ by 1 in all other pairs. It is easy to check that regularity of $f$ implies regularity of $g$. By the induction hypothesis, $g$ is the only regular function with numbers of repetitions of values are $b_0,b_1,\dots ,b_{n-1}$. But $f$ can be defined in terms of $g$: $$f(i)=\{\begin{array}{ll}g(i),& \text{if }i<l,\\ l-1,& \text{if }i=l,\\ g(i-1),& \text{if }g(i-1)<l<i,\\ g(i-1)+1,& \text{if }l\le g(i-1).\end{array}$$ In other words, add the argument-value pair $(l,l-1)$ and increase all numbers $l,\dots ,n-1$ by 1 in other pairs. This completes the solution.