0

Consider the following problem from 1987 IMO Show that there is no function $f:\mathbb N→\mathbb N$ Such that

$f(f(n))=n+1987$

In the book that I was referring the solution is given as follows:

" We show that infact there is no function that satisfies this condition

$f(f(n))=n+k$ where k is odd

Assume such an $f$ exists. Then $f(n+k)=f(n)+k$ for all n in N and $f(n-k)=f(n)-k$ for all $n\geq k$ Consider $g(n)=f(n)-k$

Verify that $g(f(n))=n$ for all n and $f(g(n))=n$ for all $f(n) \geq k$

Consider the sets $A=${$n|0\leq n<k$ and $f(n)<k$} and $B=${$n|0\leq n<k$ and $f(n)\geq k$}

Show that there is a bijection between A and B and conclude

$|A|=|B|$

This implies $2|A|=k$ and this forces a contradiction "

The only part I am having trouble is finding such a bijection

Can someone please help

Here $\mathbb{N}$ is the set of all natural numbers and 0

Aarush Saharan
  • 562
  • (Tip: Use \mid rather than | when it means "such that" or "divides" rather than half of an absolute value or determinant function. \{n | -1 < n\} gives ${n | -1 < n}$ and \{n \mid -1 < n\} gives ${n \mid -1 < n}$ with better spacing.) – aschepler Sep 28 '23 at 13:01
  • @aschepler thank you In fact I wanted to write n is greater that or equal to 0 but I don't know how to do that – Aarush Saharan Sep 28 '23 at 13:03
  • \geq or \ge gives $\geq$ and \geqslant gives the nicer looking $\geqslant$. Similarly \leq, \le and \leqslant. – user10354138 Sep 28 '23 at 13:05
  • \leq and \geq. See the MathJax tutorial, point 11. – aschepler Sep 28 '23 at 13:05
  • Since $g$ and $f$ were shown to be inverses of each other (on suitable domains containing $A$ and $B$, respectively) in the preceding line, trying to show that the bijection is given by $f\colon A\to B$ with inverse $g\colon B\to A$ looks suggestive ... – Hagen von Eitzen Sep 28 '23 at 14:06
  • @HagenvonEitzen thank you, that worked – Aarush Saharan Sep 29 '23 at 05:01

0 Answers0