Maths Olympiad Prep

Library / /240 of 520

Combinatorics Difficulty 6.9 National olympiad Find the answer

Consider a function f:ZZf: \mathbb Z \to \mathbb Z such that for every integer n0n \ge 0, there are at most 0.001n20.001n^2 pairs of integers (x,y)(x,y) for which f(x+y)f(x)+f(y)f(x+y) \neq f(x)+f(y) and max{x,y}n\max\{ \lvert x \rvert, \lvert y \rvert \} \le n. Is it possible that for some integer n0n \ge 0, there are more than nn integers aa such that f(a)af(1)f(a) \neq a \cdot f(1) and an\lvert a \rvert \le n?

Proposed by David Yang

Solution

1. Definitions and Setup:
- An integer n n is bad if f(n)nf(1) f(n) \neq n f(1) .
- A pair of integers (x,y) (x, y) is bad if f(x)+f(y)f(x+y) f(x) + f(y) \neq f(x + y) .
- A pair of integers (x,y) (x, y) is awful if at least one of x x or y y is bad and x+y x + y is also bad.

2. Interval Consideration:
- Fix an arbitrary n>0 n > 0 and consider the interval I=[n,n] I = [-n, n] .
- Slightly tweak the definition of awful to require x+yI x + y \in I .

3. Counting Awful Pairs:
- For every bad kI k \in I , any (x,y)I2 (x, y) \in I^2 with x+y=k x + y = k must be either bad or awful.
- Since for any k k there are at least n n such pairs (actually n+1 n + 1 , but we use n n for simplicity), if we have k k bad integers in I I , then there are at least nk0.001n2 nk - 0.001n^2 awful pairs.

4. Bounding the Number of Bad Integers:
- It follows that there's some bad integer B B that's in at least n0.001n2k n - \frac{0.001n^2}{k} awful pairs.
- Since every awful pair generates a different bad integer as its sum, we have:
n0.001n2kk n - \frac{0.001n^2}{k} \leq k
Simplifying this inequality:
k2nk+0.001n20 k^2 - nk + 0.001n^2 \geq 0
Solving the quadratic inequality:
k[0,n(502490)100][n(50+2490)100,) k \in \left[0, \frac{n(50 - \sqrt{2490})}{100}\right] \cup \left[\frac{n(50 + \sqrt{2490})}{100}, \infty\right)

5. **Conclusion for Small n n :**
- For small n n (say, n30 n \leq 30 ), we actually need f(x)+f(y)=f(x+y) f(x) + f(y) = f(x + y) for all x,y[n,n] x, y \in [-n, n] , which implies f f is linear over I I .
- Thus, k k falls in the first interval (since it's zero), and if at some point we transition between k k being in the first interval to the second interval for n30 n \geq 30 , we have to increase k k by more than 2 by discrete continuity, which is impossible.

6. Final Conclusion:
- Therefore, k k stays in the first interval, so there are at most n n bad numbers in [n,n] [-n, n] (actually way less), as desired.

\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.