Cool NT

For discussing Olympiad Level Number Theory problems
User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:
Cool NT

Unread post by Phlembac Adib Hasan » Sun Feb 01, 2015 11:10 am

A function $f:\mathbb Z \to \mathbb Z$ satisfies \[f(m)+f(n)+f(f(m^2+n^2))=1\quad \forall m,n\in \mathbb Z\] Also $\exists a,b:f(a)-f(b)=3$. Prove that $\exists c,d:f(c)-f(d)=1$

Hint:
$\color{white}{\text{Look carefully, the differences. Also is it a coincidence that there}}$ $
\color{white}{\text{are exactly three terms on the LHS of the equation? }}$ ;)
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

User avatar
Fm Jakaria
Posts:79
Joined:Thu Feb 28, 2013 11:49 pm

Re: Cool NT

Unread post by Fm Jakaria » Tue Feb 03, 2015 8:22 pm

My solution:

Call a nonempty set S of integers ‘good’ if $\forall x,y \in S \Rightarrow 1-(x+y) \in S$.
Lemma: If S is good and $\exists p,q \in S: p-q = 3$, then $S = \mathbb{Z}$.
Proof:
Let arbitrary $x,y,z \in S$. Then $1-(x+y) \in S \Rightarrow 1-((1-(x+y))+z) = (x+y) – z \in S…(1)$. Also $(1-2x) \in S…(2)$
In (1),we let x vary over S, and set $(y,z) = (p,q),(q,p)$ to get: $x \pm 3 \in S$. So if some $x \in S$ has residue r mod 3, then all integers with residue r is in S. Finally, $1-2x \equiv 1+x(mod 3)$. So starting with $x_0 = x$, and for all $i \in N_0, x_{i+1} = 1 – 2x_i$: then $x_0,x_1,x_2$ has distinct residues mod 3. This completes the proof.

We now note that $f(\mathbb {Z})$ is good with $f(a)-f(b) = 3$. So by the lemma, f is surjective. Then of course such c,d exists.
You cannot say if I fail to recite-
the umpteenth digit of PI,
Whether I'll live - or
whether I may, drown in tub and die.

Post Reply