I am trying to understand how many functions $\mathbb{Z^+}\to \mathbb{Z^+}$ which satistfy the three following constraints exist:

  • For every $n \in \mathbb{Z^+}$ $$f(f(n))\leq\frac{n+f(n)}{2}$$

  • For every $n \in \mathbb{Z^+}$ $$f(n)\leq f(n+1)$$

  • For every $(n,m)\in \mathbb{Z}^{+}\times\mathbb{Z}^+ $ such that $n \neq m$


One of these functions is indeed $f(n)=1$ for every $n \in \mathbb{Z}^+$, but any other constant function does not satisfy the third constraint, which is probably the strongest.

My first intuition about other functions was something on the lines of $f(n)=\text{the n-th prime number}$, but this functions (or any of its multiples) does not satisfy the first constraint, already for $n=2$.

Are there any other functions that satisfy these constraints? How can they be found?

  • $\begingroup$ What is $MCD$ in the third constraint? $\endgroup$ – Redundant Aunt Aug 27 '15 at 16:34
  • $\begingroup$ @user109899 edited! I meant GCD. $\endgroup$ – Lonidard Aug 27 '15 at 16:36
  • $\begingroup$ In the third constraint, if you don't specify $n \not = m$, then indeed $f(n)=1$ is the only solution $\endgroup$ – user261263 Aug 27 '15 at 17:41
  • $\begingroup$ @EugenCovaci Yes, you are right. I'll fix it! $\endgroup$ – Lonidard Aug 27 '15 at 17:43

The constant function $f(n)=1$ is indeed the only solution, even if we weaken the first condition to: $f(f(n)) \le C(n+f(n))$ for some fixed $C>0$ (no matter how large).

As a proof-of-concept, we prove: there is no such solution with $f(1)>1$. Note that if $f(1)>1$ then $f(n+1)>f(n)$ (strictly) for all $n$, because of the gcd condition. In particular, $f(n)>n$; so it suffices to show there is no solution even if we replace $f(f(n)) \le C(n+f(n))$ by $f(f(n)) \le 2Cf(n)$. To do so, it suffices to show that $\lim_{k\to\infty} \frac{f(k)}k = \infty$.

Each of the values $f(1),\dots,f(k)$ is divisible by at least one prime, and these primes are distinct by the gcd condition; therefore $f(k)$ is at least as large as the $k$th prime. In particular, $f(k) > k\ln k$ by Rosser's theorem, and so indeed $\lim_{k\to\infty} \frac{f(k)}k = \infty$.

This shows that there is no such solution with $f(1)>1$. To consider any solution with $f(1)=1$: If $f(n)$ is not constant, then choose $K$ such that $f(K+1)>1$, and redo the above proof with the values $f(K+1), \dots, f(K+k)$ instead of $f(1),\dots,f(k)$.


Suppose $\exists n$ so that $f(n) \gt n$. Then, from the second condition we get: $$ f(f(n)) \ge f(n) \tag 1 $$ and, using (1) and the first condition: $$ f(n) \le f(f(n))\leq\frac{n+f(n)}{2} \tag 2 $$ from (2) we get: $$ f(n) \le \frac{n+f(n)}{2} \tag 3 $$ which contradicts our assumption $f(n) \gt n$.

We just proved that $f(n) \le n, \forall n$.

Now let's suppose there is $m$ so that $f(m)>1$. We have $$ n \ge f(n) \ge f(m) \gt 1, \forall n \gt m \tag 5$$ and because of the third condition: $$ n \ge f(n) \gt f(m) \gt 1, \forall n \gt m \tag 6$$ We can also extend (6): $$ n \ge f(n)\gt f(n -1)\gt f(n -2)\gt .. \gt f(m + 1) \gt f(m) \tag 7 $$ Let's define $A = \lbrace f(m+1),f(m+2), .. ,f(n) \rbrace$ and $B=\lbrace f(m) + 1, .. ,n \rbrace$

Then A has $n-m$ elements, B has $n-f(m)$ elements and $A \subset B$.

Let's take $n$ so that $n > (m+1)f(m) \tag 8$

Because of the third condition, all multiples of $f(m)$ are not in $A$, therefore we can define $C=B\setminus\lbrace kf(m)| 2 \le k \le m + 1 \rbrace$ and still having: $$A \subset C \tag 9$$ But $C$ has $n - f(m) - m$ elements while A has $n-m$ elements, so the inclusion (9) is not possible, therefore the assumption there is $m$ so that $f(m)>1$ is false.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.