Maths Olympiad Prep

Library / /369 of 397

Algebra Difficulty 7.1 National Olympiad, round 2 Prove it Taiwan

Find all surjective functions f:ZZf: 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,yZ f(xf(y)) = 0, \forall x, y \in Z
by setting z=0z = 0. However, this would imply f(x)=0,xZf(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),xZ f(x + a) = f(x), \forall x \in Z
which is again impossible because periodic functions defined on integers aren't surjective.

f(b33b)=f(b)3=1 f(b^3 - 3b) = f(b)^3 = -1

Next, take x=b33b,y=b,z=0x = b^3 - 3b, y = b, z = 0, we have (Notice bb is non-zero)
f(4bb3)=14bb3=0b=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(2x)=0,xZ(1) f(x) + f(-2 - x) = 0, \forall x \in \mathbb{Z} \qquad (1)
Choose aZa \in \mathbb{Z} satisfying f(a)=2f(a) = 2. Set y=a,z=0y = a, z = 0:
f(2x+a)=2f(x),xZ(2) f(2x + a) = 2f(x), \forall x \in \mathbb{Z} \qquad (2)
In particular, f(a4)=2(2)=2f(a-4) = 2(-2) = -2. Use Eq. (1), we get f(2a)=2f(2-a) = 2. This means
f(2x+(2a))=2f(x)=f(2x+a). f(2x + (2 - a)) = 2f(x) = f(2x + a).
Suppose that 2aa2-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),xZ(3) f(2x + 1) = 2f(x), \forall x \in \mathbb{Z} \qquad (3)
To show f(x)=x+1,xNf(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(r1)=r and f(s1)=s then f(rs1)=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(p1)=pf(p - 1) = p when pp is a prime. We have established the based case. Suppose it's true that f(m1)=mf(m - 1) = m for all positive integer m<pm < p.

Choose cc such that f(c)=pf(c) = p. If c1(modp)c \neq -1 \pmod{p}, take dZd \in Z so that
0pd+c<p10 \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, cp1(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+1p+c2c + 1 \neq p + c, ff can take finite values on 2pZ+(2p1)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=p1c = p - 1, as desired.
Hence, by mathematical induction, we get f(x)=x+1,xNf(x) = x + 1, \forall x \in \mathbb{N}.
Finally,
f(x)=x+1,xZ 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)=2f(2a)=2. f(a + 4) = 2f(2) = -2 \rightarrow f(-2 - a) = 2.
The same argument gives us 2a=a-2 - a = a, i.e. a=1a = -1. Again, the base case is checked. Suppose f(1m)=mf(1 - m) = m is true for all positive integer m<pm < p where pp is a prime. Choose cZc \in \mathbb{Z} satisfying f(c)=pf(c) = p.

Then if c1(modp)c \neq 1 \pmod{p}, take dZd \in Z such that 1p<pd+c01 - 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 c1(modp)c \equiv 1 \pmod{p}. Since cc is even, it follows that cp+1(mod2p)c \equiv p + 1 \pmod{2p}.
f(2px+2c1)=2f(px+c)=2pf(x)=pf(2x1)=f(2pxp+c). f(2px + 2c - 1) = 2f(px + c) = 2pf(x) = pf(2x - 1) = f(2px - p + c).
If c1pc \neq 1 - p, then ff takes finite values on 2pZ+12pZ + 1 and also on ZZ, a contradiction. Therefore, c=1pc = 1 - p. By mathematical induction,
f(1x)=x,xN. f(1 - x) = x, \forall x \in N.
Use f(x)+f(2x)=0f(x) + f(2 - x) = 0, we can say
f(1x)=x,xZf(x)=1x,xZ. f(1 - x) = x, \forall x \in Z \rightarrow f(x) = 1 - x, \forall x \in Z.

Choose eZe \in Z such that f(e)=1f(e) = 1 and set y=e,z=0y = e, z = 0 to get
f(xe)=f(x)=0f(x2e)=f(xe)=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,xZf(x) = 1 + x, \forall x \in Z and f(x)=1x,xZf(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,000 problems in a working order, from AMC 10 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.