5
$\begingroup$

Let $f$ be a bijection from the set of nonnegative integers to itself. Show that there exist infinitely many triples of nonnegative integers $(a,b,c)$ with $f(a) + f(c) = 2f(b)$ and $a < b < c$.

Hello everybody. I hope you are all doing well. The question you see above is a question I could not solve. :( Any help would be appreciated. Here's what I though of:

A.P. stands for Arithmetic Progression

We just want to show that there exist infinitely many integers such that $f(a), f(b), f(c)$ are in A.P. $a < b< c$. Since $f$ is a bijection, it makes our work easier.

Suppose otherwise. There exist no $a, b, c$ with the conditions required. That is, there exists no $f(a), f(b), f(c), a < b < c$ such that they are in A.P.

Hence, $f(0), f(1), f(k)$ where is $k$ is a non-negative integer, can never be in A.P. Let $f(0) = l$ and $f(1) = m$. Also let $d = m - l$. Note that since $f$ is a bijection, $f(k) \neq l, m$ and $l \neq m$. Also assume $f(k) = p \neq m \neq l$ $$f(0) = l$$$$f(1) = m$$We consider $f(1) > f(0)$. OK now since $f(0), f(1), f(k)$ can not be in AP, we have $p - m \neq m-l$. That is there exists no $k$ in non negative integers when $m, l, p$ are in AP, which is absurd iterating $k$ from $2$.

Let me give you an example to make it clearer.

Let $f(0) = 5$ and $f(1) = 20$. The difference is $15$. Clearly, $35$ would satisfy our conditions. Since $f$ is bijection, there should be some number $k$ such that $f(k) = 35$. That is $f(0), f(1), f(k)$ are in AP. Of course $k$ is greater that $0, 1$ because it is not $0,1$ and an integer.

It only works for $f(1) > f(0)$ but I thought that the whole set of nonnegative integers must have a pairing, not just $0$ and $1$. In addition, while something like $f(0) = 10$ and $f(1) = 5$ might not work, there are is an infinite number of other pairs that will work.

Please help. I would be glad to have my "solution" being corrected. Please also inform if this question is a duplicate as it seems as a very common question but I could not find this anywhere on the internet.

Thank You.

EDIT: As pointed out by Martin R (thank you), this has an answer for one such triplet. It is here: Solve this problem on functions

$\endgroup$
  • 3
    $\begingroup$ The existence of one such triple is demonstrated here: math.stackexchange.com/questions/1749558/…. $\endgroup$ – Martin R Sep 6 at 12:21
  • $\begingroup$ Thank you Martin. That definitely helps. BTW how did you search this problem up? (because the title is really weird "Solve this problem on functions") Thanks $\endgroup$ – Vasu090 Sep 6 at 12:23
  • 1
    $\begingroup$ With Approach0. See also math.meta.stackexchange.com/q/24978/42969. $\endgroup$ – Martin R Sep 6 at 12:25
  • $\begingroup$ Thank you so much. I did not know about it. :) $\endgroup$ – Vasu090 Sep 6 at 12:27
  • $\begingroup$ I think it is Approach0 (with zero), not Approacho. $\endgroup$ – GEdgar Sep 6 at 12:38
1
$\begingroup$

The map $g:=f^{-1}$ is a bijection of ${\mathbb N}_{\geq0}$ as well. For a pair $(y,h)$ such that $$g(y-h)<g(y)<g(y+h)\tag{1}$$ put $a:=g(y-h)$, $b:=g(y)$, $c:=g(y+h)$. Then $a<b<c$ and $$f(a)+f(c)=(y-h)+(y+h)=2y=2 f(b)\ .$$ Claim. There are infinitely many pairs $(y,h)$ satisfying $(1)$.

Proof. Define the function $$s(y):=\max\bigl\{k\bigm| [0..k]\subset g\bigl([0..y]\bigr)\bigr\}\qquad\bigl(y\geq f(0)\bigr)\ .$$ The function $y\mapsto s(y)$ is weakly increasing to $\infty$, but may make jumps $>1$. There are infinitely many $y$ with $s(y-1)<s(y)$. Consider such a $y$, and put $s(y-1)=:k-1$. Then $s(y)\geq k$. Since $k\notin g\bigl([0..(y-1)]\bigr)$ and $[0..k]\subset g\bigl([0..y]\bigr)$ it follows that $g(y)=k$. Furthermore $g(y+h)>k=g(y)$ for all $h>0$. On the other hand, there are many $h>0$ for which $g(y-h)<k=g(y)$. It follows that the $y$ we are considering can be supplemented with an $h>0$ such that $(1)$ holds.

$\endgroup$

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.