Maths Olympiad Prep

Library / /324 of 520

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it

Let Z\mathbb Z be the set of integers. We consider functions f:ZZf :\mathbb Z\to\mathbb Z satisfying
f(f(x+y)+y)=f(f(x)+y)f\left(f(x+y)+y\right)=f\left(f(x)+y\right)
for all integers xx and yy. For such a function, we say that an integer vv is f-rare if the set
Xv={xZ:f(x)=v}X_v=\{x\in\mathbb Z:f(x)=v\}
is finite and nonempty.
(a) Prove that there exists such a function ff for which there is an ff-rare integer.
(b) Prove that no such function ff can have more than one ff-rare integer.

Netherlands

Solution

### Part (a): Prove that there exists such a function f f for which there is an f f -rare integer.

1. **Define the function f f :**
We need to construct a function f:ZZ f: \mathbb{Z} \to \mathbb{Z} that satisfies the given functional equation and has at least one f f -rare integer. Let's consider the function:
f(x)={0if x=02ν2(x)+1if x0 f(x) = \begin{cases} 0 & \text{if } x = 0 \\ 2^{\nu_2(x) + 1} & \text{if } x \neq 0 \end{cases}
where ν2(x) \nu_2(x) denotes the highest power of 2 dividing x x .

2. Verify the functional equation:
We need to check if f f satisfies the functional equation:
f(f(x+y)+y)=f(f(x)+y) f(f(x+y) + y) = f(f(x) + y)
- For x=0 x = 0 :
f(f(y)+y)=f(y) f(f(y) + y) = f(y)
This holds because f(y) f(y) is defined such that f(f(y)+y)=f(y) f(f(y) + y) = f(y) .

- For x0 x \neq 0 :
f(f(x+y)+y)=f(2ν2(x+y)+1+y) f(f(x+y) + y) = f(2^{\nu_2(x+y) + 1} + y)
Since f(x)=2ν2(x)+1 f(x) = 2^{\nu_2(x) + 1} , we have:
f(f(x)+y)=f(2ν2(x)+1+y) f(f(x) + y) = f(2^{\nu_2(x) + 1} + y)
Both sides are equal because f f is defined in terms of the highest power of 2 dividing the argument.

3. **Identify an f f -rare integer:**
- Consider v=0 v = 0 . The set X0={xZ:f(x)=0} X_0 = \{ x \in \mathbb{Z} : f(x) = 0 \} is {0} \{0\} , which is finite and nonempty.
- Therefore, 0 0 is an f f -rare integer.

### Part (b): Prove that no such function f f can have more than one f f -rare integer.

1. **Assume there are two f f -rare integers d d and e e with de d \neq e :**
- Let d d and e e be f f -rare integers. This means Xd X_d and Xe X_e are both finite and nonempty.

2. Derive a contradiction:
- Suppose f(k)=d f(k) = d and f(l)=e f(l) = e for some integers k k and l l .
- From the functional equation, we have:
f(f(x+y)+y)=f(f(x)+y) f(f(x+y) + y) = f(f(x) + y)
- Set x=k x = k and y=lk y = l - k :
f(f(k+(lk))+(lk))=f(f(k)+(lk)) f(f(k + (l - k)) + (l - k)) = f(f(k) + (l - k))
f(f(l)+(lk))=f(d+(lk)) f(f(l) + (l - k)) = f(d + (l - k))
f(e+(lk))=f(d+(lk)) f(e + (l - k)) = f(d + (l - k))
- Since de d \neq e , this implies f f must map different values to the same value, which contradicts the definition of f f -rare integers being finite and nonempty.

3. **Conclude that there cannot be more than one f f -rare integer:**
- Therefore, no such function f f can have more than one f f -rare integer.

\blacksquare

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.