Problem A. 835. (October 2022)
A. 835. A. 835. Let \(\displaystyle f^{(n)}(x)\) denote the \(\displaystyle n^\text{th}\) iterate of function \(\displaystyle f\), i.e \(\displaystyle f^{(1)}(x)=f(x)\), \(\displaystyle f^{(n+1)}(x)=f\Big(f^{(n)}(x)\Big)\).
Let \(\displaystyle p(n)\) be a given polynomial with integer coefficients, which maps the positive integers into the positive integers. Is it possible that the functional equation \(\displaystyle f^{(n)}(n)=p(n)\) has exactly one solution \(\displaystyle f\) that maps the positive integers into the positive integers?
Submitted by Dávid Matolcsi andKristóf Szabó, Budapest
(7 pont)
Deadline expired on November 10, 2022.
Answer: there is not exactly one solution to any polynomial: for any polynomial, there is either no solution, or there are infinitely many solutions.
If \(\displaystyle p(x)=c\) is a constant polynomial, then there are infinitely many solutions to the functional equation: all \(\displaystyle f(n)=c\) except \(\displaystyle f(2)\), which is a positive integer other than \(\displaystyle c\).
If \(\displaystyle p(x)=x\), then there are also infinitely many solutions: \(\displaystyle f(n)=n\) for every positive integer \(\displaystyle n\) except for arbitrarily chosen even numbers \(\displaystyle a\ne b\), for which \(\displaystyle f(a)=b\) and \(\displaystyle f(b)=a\).
If \(\displaystyle p(x)=x+c\), where \(\displaystyle c\ge 1\), then we show that there is no solution to the functional equation.
Let \(\displaystyle g(k)=f^{(k)}(1)\). This sequence contains the numbers \(\displaystyle 1, 1+c, 1+2c,...\), so each element of the sequence must be different, otherwise the elements of the sequence would be in a loop and there could not be infinitely many different numbers in the sequence.
Since each number is at most once in the sequence \(\displaystyle g(k)\), the sequence takes only finitely many values less than \(\displaystyle c+1\), i.e. there exists \(\displaystyle N\) such that \(\displaystyle g(k)>c+1\) for all \(\displaystyle k>N\).
Take \(\displaystyle c+1\) consecutive elements of the series with \(\displaystyle k>N\). According to pigeonhole principle, there are two of them which give the same remainder divided by \(\displaystyle c\), let them be \(\displaystyle g(k)\) and \(\displaystyle g(m),\) where \(\displaystyle k<m\le k+c\).
If \(\displaystyle g(m)<g(k)\), then \(\displaystyle g(m+g(m))=g(m)+c\), then \(\displaystyle g(m+g(m)+g(g(m)))=g(m)+2c\), and so on. Since \(\displaystyle g(m)\) and \(\displaystyle g(k)\) give the same remainder divided by \(\displaystyle c\), the series picks up \(\displaystyle g(k)\) somewhere after \(\displaystyle m\), which is a contradiction to the fact that the series cannot have the same value twice.
If \(\displaystyle g(m)>g(k)\), then since \(\displaystyle g(k)>c+1\), then \(\displaystyle k+g(k)>m\), and \(\displaystyle k+g(k)+g(g(k))\) and the elements that follow are also greater than \(\displaystyle m\) by necessity. But at these locations the series takes \(\displaystyle g(k)+c, g(k)+2c,...\), and so over time \(\displaystyle g(m)\), again a contradiction, because the series cannot take the same value at two different locations.
So we see that there is no solution for \(\displaystyle p(x)=x+c\).
If \(\displaystyle p(x)\) is not \(\displaystyle x+c\), then we show that if there is a solution to the functional equation, then there are infinitely many solutions.
Suppose that there exists a solution \(\displaystyle f_0\). It is easy to see that the sequence \(\displaystyle f_0^{(k)}(n)\) takes the same element (loops) several times for exactly the same \(\displaystyle n\)s for which the sequence \(\displaystyle p^{(k)}(n)\) loops.
We create a new function \(\displaystyle f\). For each \(\displaystyle n\) for which \(\displaystyle p^{(k)}(n)\) loops, assign \(\displaystyle f\) the same as \(\displaystyle f_0\). There are only finitely many such \(\displaystyle n\), because after a bound \(\displaystyle N\) the polynomial \(\displaystyle p\) is strictly monotonically increasing, and for every \(\displaystyle n\) it assigns a number greater than \(\displaystyle n\), so it cannot loop. The set of this finite set of many numbers is called \(\displaystyle H\). For every \(\displaystyle n\in H\), \(\displaystyle f^{(n)}(n)=p(n)\) is satisfied, since it is satisfied for \(\displaystyle f_0\).
Since the polynomial \(\displaystyle p\) is not \(\displaystyle x+c\), there are infinitely many positive integers that it does not take as values, and there are still infinitely many of these non-taken numbers that are not \(\displaystyle H\), the set of which is called \(\displaystyle A\).
Since the polynomial \(\displaystyle p\) is strictly monotonically increasing after a bound and thus becomes injective, there are only finitely many numbers \(\displaystyle a\in A\) for which there exists \(\displaystyle b\in A\) for which there exists \(\displaystyle k\) and \(\displaystyle m\) such that \(\displaystyle p^{(k)}(a)=p^{(m)}(b)\). This finite set of numbers forms the set \(\displaystyle C\subset A\).
If \(\displaystyle a\in C\), then let \(\displaystyle f(a)=f_0(a), f(f(a))=f_0(f_0(a)),... \) up to \(\displaystyle f^{(s)}(a)\) such that for every \(\displaystyle b\in A\) for which \(\displaystyle p^{(k)}(a)=p^{(m)}(b)\), \(\displaystyle f_0^{s}(a)\) can be obtained as \(\displaystyle f_0^{(r)}(b)\). This all happens in finitely many steps for finitely many numbers in \(\displaystyle C\), so we have given \(\displaystyle f\) for only finitely many numbers. We call \(\displaystyle D\) the set of numbers that have been given a value here.
Then, the remaining values of \(\displaystyle f\) are given according to the following algorithm:
We go through the positive integers one by one. If for the next \(\displaystyle n\) has not yet been assigned a value by \(\displaystyle f\), then we check whether there exists \(\displaystyle m\) such that \(\displaystyle n=f^{(m-1)}(m)\) according to the values of \(\displaystyle f\) recorded so far. If so (Case 1), then by implication \(\displaystyle f(n)=p(m)\).
If there is no such \(\displaystyle m\) (case 2), then let \(\displaystyle f(n)=r\), for which the following properties hold:
(I.) \(\displaystyle r\in A\setminus C,\)
(II.) the value \(\displaystyle r\) is not yet assigned to any number by \(\displaystyle f\),
(III.) \(\displaystyle r>p(N),\) where \(\displaystyle N\) is the limit beyond which the polynomial \(\displaystyle p\) is strictly monotone increasing,
(IV.) For any \(\displaystyle a\) to which we have already assigned a value by \(\displaystyle f\) and for any \(\displaystyle s\) it cannot be satisfied that
\(\displaystyle 1-\frac{1}{100K}<\frac{r}{p^{(s)}(a)}<1+\frac{1}{100K},\)
where \(\displaystyle K\) is the number of numbers to which we have already assigned a value of \(\displaystyle f\).
(V.) there are no numbers \(\displaystyle a\) and \(\displaystyle t\) and \(\displaystyle i\) and \(\displaystyle j\) for which \(\displaystyle f^{(t)}(a)=n\) and
\(\displaystyle a+p(a)+p(p(a))...+p^{(i)}(a)=t+r+p(r)+...+p^{(j)}(r).\)
We show that if case 2 holds, then there are always infinitely many possible \(\displaystyle r\) to choose from. We show this by showing that for a sufficiently large \(\displaystyle R\) there is always a value \(\displaystyle r\) satisfying all conditions between \(\displaystyle R\) and \(\displaystyle 2R\).
Since the polynomial \(\displaystyle p(x)\) is not \(\displaystyle x+c\), for sufficiently large \(\displaystyle R\) at most half of the numbers between \(\displaystyle R\) and \(\displaystyle 2R\) are taken by \(\displaystyle p\), and the set \(\displaystyle C\) has only finitely many elements, so at least almost half of the numbers between \(\displaystyle R\) and \(\displaystyle 2R\) are in \(\displaystyle A\setminus C\).
For every \(\displaystyle a\) to which we have already assigned a value, there are at most two different \(\displaystyle p^{(s)}(a)\) values between \(\displaystyle R\) and \(\displaystyle 2R\), so at most nearly \(\displaystyle \frac{1}{50}\) of the numbers between \(\displaystyle R\) and \(\displaystyle 2R\) do not satisfy condition (IV).
Consider a number \(\displaystyle r\) for which the four conditions are satisfied. Then, for an arbitrary \(\displaystyle a\), to which we have already assigned a value, there exists a number \(\displaystyle s\) such that
\(\displaystyle (1+\frac{1}{100K})p^{(s)}(a)<r<(1-\frac{1}{100K})p^{(s+1)}(a).\)
Using that \(\displaystyle p(x)\) is not \(\displaystyle x+c\), it is satisfied that
\(\displaystyle p^{(h)}(r)-p^{(s+h)}(a)>2^h(r-p^{(s)}(a))>2^h \frac{1}{100K} p^{(s)}(a).\)
Meanwhile
\(\displaystyle a+p(a)+...+p^{(s)}(a)<3p^{(s)}(a),\)
so if \(\displaystyle k>\log_2(300K)\), then
\(\displaystyle t+b+p(b)+...+p^{(k)}(b)>a+p(a)+...+p^{(s+k)}(a)\)
Similarly, it can be seen that if \(\displaystyle k>\log_2(300K)\), then
\(\displaystyle t+b+p(b)+...+p^{(k)}(b)<a+p(a)+...+p^{(s+1+k)}(a).\)
Thus, for any \(\displaystyle a\), only \(\displaystyle i, j<\log_2(300K)\) can make it possible that an \(\displaystyle r\) satisfying condition (IV) satisfies
\(\displaystyle a+p(a)+p(p(a))...+p^{(i)}(a)=t+r+p(r)+...+p^{(j)}(r),\)
and for any given \(\displaystyle (a,i,j)\), there is at most one such \(\displaystyle r\), since the function \(\displaystyle t+r+p(r)+...+p^{(j)}(r)\) is strictly monotone increasing.
Thus, among the \(\displaystyle r\) satisfying the first four conditions, at most \(\displaystyle K\log_2^2(300K)\) is excluded by condition (V). This is a constant value that does not depend on \(\displaystyle R\), so there still remains a number between \(\displaystyle R\) and \(\displaystyle 2R\) that satisfies all the conditions.
Now we show that case 2 holds at least once.
We assume indirectly that case 2 never occurs. Then, for a sufficiently large \(\displaystyle M\), from \(\displaystyle 1\) to \(\displaystyle M\), every number \(\displaystyle n\) is in \(\displaystyle H\) or \(\displaystyle D\), or case 1 holds for it, i.e. \(\displaystyle n=f^{(m-1)}(m)\), where \(\displaystyle m\le \frac{M}{2}\) or \(\displaystyle m \in D\), because for \(\displaystyle m>\frac{M}{2}\), we have assigned values to only at most \(\displaystyle m-2\) numbers between \(\displaystyle m\) and \(\displaystyle n\), so \(\displaystyle n=f^{(m-1)}(m)\) can't be true.
However, at most \(\displaystyle |H|+2|D|+\frac{M}{2}\) can obtained this way, and if \(\displaystyle M\) is large enough, it is less than \(\displaystyle M\), so there must be a number from \(\displaystyle 1\) to \(\displaystyle M\) for which case 2 holds.
Since we have seen that there are infinitely many function values that can be chosen in Case 2, now we showed that if the algorithm described above is indeed correct, then there are infinitely many \(\displaystyle f\) solutions to the functional equation.
Now we only need to prove that if case 1 holds, then \(\displaystyle f(n)\) can always be given a value in an unambiguous way. This can't be done only if there are two distinct \(\displaystyle m\) and \(\displaystyle k\) for which \(\displaystyle n=f^{(m-1)}(m)\) and \(\displaystyle n=f^{(k-1)}(k)\), but \(\displaystyle p(m)\ne p(k)\).
For \(\displaystyle m\), we check whether he was already the image of something according to \(\displaystyle f\), and if so, whether he was born according to the rule of case 1. If so, we step back to the ancestor of \(\displaystyle m_1\), for which \(\displaystyle f^{(m_1)}(m_1)=p(m_1)=m\). If \(\displaystyle m_1\) was also born according to the rule of case 1, we also step back to its ancestor until we reach a number \(\displaystyle a\), which is no longer the image of something \(\displaystyle f\) assigned according to the rule of case 1.
From the way \(\displaystyle a\) is obtained, it follows that
\(\displaystyle n=f^{(a+p(a)+...+p^{(i)}(a)-1)}(a)\)
for a value of \(\displaystyle i=0\), where \(\displaystyle i=0\) corresponds to \(\displaystyle a=m\).
In the same way, we find the ancestor of \(\displaystyle k\) such that \(\displaystyle b\) is no longer the image of something by \(\displaystyle f\) assigned by the rule of case 1, and
\(\displaystyle n=f^{(b+p(b)+...+p^{(j)}(b)-1)}(b).\)
\(\displaystyle a\) and \(\displaystyle b\) are necessarily different, otherwise \(\displaystyle m\) and \(\displaystyle k\) would not be different.
Suppose that neither \(\displaystyle a\) nor \(\displaystyle b\) is an ancestor of the other (i.e., there is no \(\displaystyle t\) such that \(\displaystyle f^{(t)}(a)=b\) or vice versa), but that \(\displaystyle n\) is nevertheless their common descendant, i.e., \(\displaystyle f^{(q)}(a)=f^{(s)}(b)=n\) for some \(\displaystyle s\) and \(\displaystyle q\).
Then let \(\displaystyle n'\) be their first common descendant, and let \(\displaystyle a'\) and \(\displaystyle b'\) be the descendants of \(\displaystyle a\) and \(\displaystyle b\) for which \(\displaystyle f(a')=f(b')=n'\).
If we have given \(\displaystyle f(a')\) and \(\displaystyle f(b')\) a value according to the rule in Case 2, then the one we gave a value to later could not have been given a value that we had already assigned to an earlier one, so then \(\displaystyle f(a')=f(b')\) couldn't have occured.
If we assign a value to one according to the rule in case 1 and to the other according to the rule in case 2, then the value assigned to one is in \(\displaystyle A\) and so is not taken by the polynomial \(\displaystyle p\), while the other is \(\displaystyle p(m)\), so we cannot have \(\displaystyle f(a')=f(b')\).
If both of them take values according to case 2, then \(\displaystyle n'=f(a')=f(b')\) occurs in two ways in the form \(\displaystyle p(s)\), which means that \(\displaystyle n'\in D\) and its ancestors are in \(\displaystyle D\), so \(\displaystyle a\in D\) and \(\displaystyle b\in D\).
Then \(\displaystyle f\) assigns to them the same values as \(\displaystyle f_0\), and also to their descendants, at least up to the first point where \(\displaystyle f_0^{(s)}(a)=f_0^{(r)}(b)\).
Since
\(\displaystyle f^{(a+p(a)+...+p^{(i)}(a)-1)}(a)=n=f^{(b+p(b)+...+p^{(j)}(b)-1)}(b),\)
that is, \(\displaystyle s-r=(a+p(a)+...+p^{(i)}(a))-(b+p(b)+...+p^{(j)}(b))\).
From this it follows that
\(\displaystyle p^{(i+1)}(a)=f_0^{(a+p(a)+...+p^{(i)}(a))}(a)=n=f_0^{(b+p(b)+...+p^{(j)}(b))}(b)=p^{(j+1)}(b).\)
The two values to be assigned to \(\displaystyle f(n)\) are \(\displaystyle p^{(i+1)}(a)\) and \(\displaystyle p^{(j+1)}(b)\), so because they are equal, we can still follow the rule in Case 1 in this case.
Now we only need to consider the case where \(\displaystyle a\) and \(\displaystyle b\) are ancestors of each other, without loss of generality \(\displaystyle f^{(t+1)}(a)=b\).
Let \(\displaystyle f^{(t)}(a)=c\). If \(\displaystyle c\in D\), then \(\displaystyle a\in D\), and then by the previous logic the values of \(\displaystyle p^{(i+1)}(a)\) and \(\displaystyle p^{(j+1)}(b)\) to be assigned to \(\displaystyle f(n)\) are equal.
So \(\displaystyle c\notin D\), so we assigned \(\displaystyle b\) to \(\displaystyle f(c)\) according to the rule of case 1 or 2, and we assumed in the definition of \(\displaystyle b\) that case 1 did not hold.
So, by the rule of Case 2, \(\displaystyle f(c)=b\) is a number in \(\displaystyle A\) for which, by condition (V), it does not hold for any \(\displaystyle i\) and \(\displaystyle j\) that
\(\displaystyle t+b+p(b)+...+p^{(j)}(b)=a+p(a)+...p^{(i)}(a).\)
However, this contradicts our assumption that
\(\displaystyle n=f^{(b+p(b)+...+p^{(j)}(b)-1)}(b)=f^{(t+b+p(b)+...+p^{(j)}(b)-1)}(a)\)
and also
\(\displaystyle n=f^{(a+p(a)+...p^{(i)}(a)-1)}(a)\)
This leads us to a contradiction, i.e. in case 1 it is always unambiguous which value to assign to \(\displaystyle n\).
So the given algorithm assigns a value to each number, and by the rule of case 1, for the resulting \(\displaystyle f\) it is satisfied that \(\displaystyle f^{(m)}(m)=p(m)\) for each positive integer \(\displaystyle m\). We also showed that there are cases where case 2 holds, so we have infinitely many choices in the continuation of the algorithm, that is, there are infinitely many solutions to the functional equation.
Statistics:
3 students sent a solution. 1 point: 2 students. 0 point: 1 student.
Problems in Mathematics of KöMaL, October 2022