Maths Olympiad Prep

Library / Taiwan IMO Selection Camp /335 of 359

Taiwan IMO Selection Camp

Algebra Difficulty 7.1 National Olympiad, round 2 Prove it Taiwan

Find all surjective functions f:Z→Zf: Z \to Z such that for all integers x,y,zx, y, z
f(xyz+xf(y)+yf(z)+zf(x))=f(x)f(y)f(z) holds. f(xyz + xf(y) + yf(z) + zf(x)) = f(x)f(y)f(z) \text{ holds.}
Note: Here ZZ denotes the set of all integers.

Solution

First of all, we have f(0)=f(0)3f(0) = f(0)^3 by setting x=y=z=0x = y = z = 0 in the condition.
Therefore, f(0)=−1,0f(0) = -1, 0 or 11. Now, if f(0)=0f(0) = 0, we'll get
f(xf(y))=0,∀x,y∈Z f(xf(y)) = 0, \forall x, y \in Z
by setting z=0z = 0. However, this would imply f(x)=0,∀x∈Zf(x) = 0, \forall x \in Z, which is impossible. So it remains to consider the case that f(0)=−1f(0) = -1 or f(0)=1f(0) = 1.

If there is non-zero integer aa such that f(a)=1f(a) = 1. Then one can set y=a,z=0y = a, z = 0 to get
f(x+a)=f(x),∀x∈Z f(x + a) = f(x), \forall x \in Z
which is again impossible because periodic functions defined on integers aren't surjective.

f(b3−3b)=f(b)3=−1 f(b^3 - 3b) = f(b)^3 = -1

Next, take x=b3−3b,y=b,z=0x = b^3 - 3b, y = b, z = 0, we have (Notice bb is non-zero)
f(4b−b3)=1⇔4b−b3=0⇔b=2,−2 f(4b - b^3) = 1 \Leftrightarrow 4b - b^3 = 0 \Leftrightarrow b = 2, -2
Case 1.1: f(−2)=−1f(-2) = -1.
In this case we know
f(x)+f(−2−x)=0,∀x∈Z(1) f(x) + f(-2 - x) = 0, \forall x \in \mathbb{Z} \qquad (1)
Choose a∈Za \in \mathbb{Z} satisfying f(a)=2f(a) = 2. Set y=a,z=0y = a, z = 0:
f(2x+a)=2f(x),∀x∈Z(2) f(2x + a) = 2f(x), \forall x \in \mathbb{Z} \qquad (2)
In particular, f(a−4)=2(−2)=−2f(a-4) = 2(-2) = -2. Use Eq. (1), we get f(2−a)=2f(2-a) = 2. This means
f(2x+(2−a))=2f(x)=f(2x+a). f(2x + (2 - a)) = 2f(x) = f(2x + a).
Suppose that 2−a≠a2-a \neq a. Then ff could only take finite values on 2Z+a2\mathbb{Z}+a. But Eq. (2) then gives that ff could only take finite values on integers, which contradicts to the surjectivity of ff.
Thus, aa must be 1 and Eq. (2) becomes
f(2x+1)=2f(x),∀x∈Z(3) f(2x + 1) = 2f(x), \forall x \in \mathbb{Z} \qquad (3)
To show f(x)=x+1,∀x∈Nf(x) = x + 1, \forall x \in \mathbb{N} (N\mathbb{N} is the set of positive integers), we'll apply mathematical induction. Note that
f(r−1)=r and f(s−1)=s then f(rs−1)=rs f(r - 1) = r \text{ and } f(s - 1) = s \text{ then } f(rs - 1) = rs
by setting x=r,y=s,z=0x = r, y = s, z = 0. Consequently, it remains to check that f(p−1)=pf(p - 1) = p when pp is a prime. We have established the based case. Suppose it's true that f(m−1)=mf(m - 1) = m for all positive integer m<pm < p.

Choose cc such that f(c)=pf(c) = p. If c≠−1(modp)c \neq -1 \pmod{p}, take d∈Zd \in Z so that
0≤pd+c<p−10 \le pd + c < p - 1. Set x=d,y=c,z=0x = d, y = c, z = 0, we get
pd+c+1=f(pd+c)=pf(d). pd + c + 1 = f(pd + c) = pf(d).
This gives pd+c+1pd + c + 1 is divisible by pp, which is absurd! Moreover, if c+1c + 1 is a multiple of 2p2p, then cc is odd. But, it's impossible by Eq. (3).
As the result, c≡p−1(mod2p)c \equiv p - 1 \pmod{2p}. Now,
f(2px+2c+1)=2f(px+c)=2pf(x)=pf(2x+1)=f(2px+p+c) f(2px + 2c + 1) = 2f(px + c) = 2pf(x) = pf(2x + 1) = f(2px + p + c)
If 2c+1≠p+c2c + 1 \neq p + c, ff can take finite values on 2pZ+(2p−1)2p\mathbb{Z} + (2p - 1). But 2pf(x)=f(2px+p+c)2pf(x) = f(2px + p + c) implies ff can take finite values, a contradiction. We conclude that 2c+1=p+c2c + 1 = p + c. In other words, c=p−1c = p - 1, as desired.
Hence, by mathematical induction, we get f(x)=x+1,∀x∈Nf(x) = x + 1, \forall x \in \mathbb{N}.
Finally,
f(x)=x+1,∀x∈Z f(x) = x + 1, \forall x \in \mathbb{Z}
according to equation (1).

Still, choose aa to be the number such that f(a)=2f(a) = 2. This time, we have
f(a+4)=2f(2)=−2→f(−2−a)=2. f(a + 4) = 2f(2) = -2 \rightarrow f(-2 - a) = 2.
The same argument gives us −2−a=a-2 - a = a, i.e. a=−1a = -1. Again, the base case is checked. Suppose f(1−m)=mf(1 - m) = m is true for all positive integer m<pm < p where pp is a prime. Choose c∈Zc \in \mathbb{Z} satisfying f(c)=pf(c) = p.

Then if c≠1(modp)c \neq 1 \pmod{p}, take d∈Zd \in Z such that 1−p<pd+c≤01 - p < pd + c \leq 0. Set x=d,y=c,z=0x = d, y = c, z = 0:
1−(pd+c)=f(pd+c)=pf(d). 1 - (pd + c) = f(pd + c) = pf(d).
This is also impossible. So c≡1(modp)c \equiv 1 \pmod{p}. Since cc is even, it follows that c≡p+1(mod2p)c \equiv p + 1 \pmod{2p}.
f(2px+2c−1)=2f(px+c)=2pf(x)=pf(2x−1)=f(2px−p+c). f(2px + 2c - 1) = 2f(px + c) = 2pf(x) = pf(2x - 1) = f(2px - p + c).
If c≠1−pc \neq 1 - p, then ff takes finite values on 2pZ+12pZ + 1 and also on ZZ, a contradiction. Therefore, c=1−pc = 1 - p. By mathematical induction,
f(1−x)=x,∀x∈N. f(1 - x) = x, \forall x \in N.
Use f(x)+f(2−x)=0f(x) + f(2 - x) = 0, we can say
f(1−x)=x,∀x∈Z→f(x)=1−x,∀x∈Z. f(1 - x) = x, \forall x \in Z \rightarrow f(x) = 1 - x, \forall x \in Z.

Choose e∈Ze \in Z such that f(e)=1f(e) = 1 and set y=e,z=0y = e, z = 0 to get
f(x−e)=−f(x)=0→f(x−2e)=−f(x−e)=f(x). f(x - e) = -f(x) = 0 \rightarrow f(x - 2e) = -f(x - e) = f(x).
Because ee is non-zero, ff is periodic, which is impossible.
It's easy to verify that f(x)=1+x,∀x∈Zf(x) = 1 + x, \forall x \in Z and f(x)=1−x,∀x∈Zf(x) = 1 - x, \forall x \in Z satisfy the original conditions. In conclusion, they are our answers.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.