Maths Olympiad Prep

Library / /92 of 121

Algebra Difficulty 6.7 National Olympiad Prove it India

Problem:

Let f:ZZf: \mathbb{Z} \rightarrow \mathbb{Z} be a function satisfying f(0)0f(0) \neq 0, f(1)=0f(1)=0 and

(i) f(xy)+f(x)f(y)=f(x)+f(y)f(xy)+f(x)f(y)=f(x)+f(y);

(ii) (f(xy)f(0))f(x)f(y)=0(f(x-y)-f(0)) f(x) f(y)=0,

for all x,yZx, y \in \mathbb{Z}, simultaneously.

a. Find the set of all possible values of the function ff.

b. If f(10)0f(10) \neq 0 and f(2)=0f(2)=0, find the set of all integers nn such that f(n)0f(n) \neq 0.

Solution

Solution:

Setting y=0y=0 in the condition (ii), we get
(f(x)f(0))f(x)=0 (f(x)-f(0)) f(x)=0
for all xx (since f(0)0f(0) \neq 0). Thus either f(x)=0f(x)=0 or f(x)=f(0)f(x)=f(0), for all xZx \in \mathbb{Z}. Now taking x=y=0x=y=0 in (i), we see that f(0)+f(0)2=2f(0)f(0)+f(0)^2=2 f(0). This shows that f(0)=0f(0)=0 or f(0)=1f(0)=1. Since f(0)0f(0) \neq 0, we must have f(0)=1f(0)=1. We conclude that
either f(x)=0 or f(x)=1 for each xZ \text{either } f(x)=0 \text{ or } f(x)=1 \text{ for each } x \in \mathbb{Z}
This shows that the set of all possible values of f(x)f(x) is {0,1}\{0,1\}. This completes (a).

Let S={nZf(n)0}S=\{n \in \mathbb{Z} \mid f(n) \neq 0\}. Hence we must have S={nZf(n)=1}S=\{n \in \mathbb{Z} \mid f(n)=1\} by (a). Since f(1)=0f(1)=0, 11 is not in SS. And f(0)=1f(0)=1 implies that 0S0 \in S. Take any xZx \in \mathbb{Z} and ySy \in S. Using (ii), we get
f(xy)+f(x)=f(x)+1 f(xy)+f(x)=f(x)+1
This shows that xySxy \in S. If xZx \in \mathbb{Z} and yZy \in \mathbb{Z} are such that xySxy \in S, then (ii) gives
1+f(x)f(y)=f(x)+f(y) 1+f(x)f(y)=f(x)+f(y)
Thus (f(x)1)(f(y)1)=0(f(x)-1)(f(y)-1)=0. It follows that f(x)=1f(x)=1 or f(y)=1f(y)=1; i.e., either xSx \in S or ySy \in S. We also observe from (ii) that xSx \in S and ySy \in S implies that f(xy)=1f(x-y)=1 so that xySx-y \in S. Thus SS has the properties:

(A) xZx \in \mathbb{Z} and ySy \in S implies xySxy \in S;

(B) x,yZx, y \in \mathbb{Z} and xySxy \in S implies xSx \in S or ySy \in S;

(C) x,ySx, y \in S implies xySx-y \in S.

Now we know that f(10)0f(10) \neq 0 and f(2)=0f(2)=0. Hence f(10)=1f(10)=1 and 10S10 \in S; and 2S2 \notin S. Writing 10=2×510=2 \times 5 and using (B), we conclude that 5S5 \in S and f(5)=1f(5)=1. Hence f(5k)=1f(5k)=1 for all kZk \in \mathbb{Z} by (A).

Suppose f(5k+l)=1f(5k+l)=1 for some ll, 1l41 \leq l \leq 4. Then 5k+lS5k+l \in S. Choose uZu \in \mathbb{Z} such that lu1(mod5)lu \equiv 1 \pmod{5}. We have (5k+l)uS(5k+l)u \in S by (A). Moreover, lu=1+5mlu=1+5m for some mZm \in \mathbb{Z} and
(5k+l)u=5ku+lu=5ku+5m+1=5(ku+m)+1 (5k+l)u=5ku+lu=5ku+5m+1=5(ku+m)+1
This shows that 5(ku+m)+1S5(ku+m)+1 \in S. However, we know that 5(ku+m)S5(ku+m) \in S. By (C), 1S1 \in S which is a contradiction. We conclude that 5k+lS5k+l \notin S for any ll, 1l41 \leq l \leq 4. Thus
S={5kkZ} S=\{5k \mid k \in \mathbb{Z}\}

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 reproduced verbatim; metadata (topic, difficulty) added by this project.