Consider a function $f: \mathbb Z \to \mathbb Z$ such that for every integer $n \ge 0$, there are at most $0.001n^2$ pairs of integers $(x,y)$ for which $f(x+y) \neq f(x)+f(y)$ and $\max\{ \lvert x \rvert, \lvert y \rvert \} \le n$. Is it possible that for some integer $n \ge 0$, there are more than $n$ integers $a$ such that $f(a) \neq a \cdot f(1)$ and $\lvert a \rvert \le n$? Proposed by David Yang
Problem
Source: ELMO 2013/6, by David Yang; also Shortlist A7
Tags: function, induction, algebra unsolved, algebra, 2013, 3n-3 theorem, continuity
06.07.2013 13:07
Darn this is a pretty silly problem. This solution was found in collaboration with zero.destroyer, it is only sketched cause we were too lazy to work out the computations explicitly. Call an integer $x$ good if $f(x) = x \cdot f(1)$ and bad otherwise. Call a pair $(x,y)$ divad if $f(x+y) = f(x) + f(y)$ and gnay otherwise. Denote $S_n$ as the set of integers $|x| \le n$ such that $x$ is good. Remark that for all $|x| \le 31$ we have $x$ is good. Let $m$ be an arbitrary integer. Note that by PIE: \begin{eqnarray*} |S_n \cap (m - S_n)| &=& |S_n| + |m - S_n| - |S_n \cup (m - S_n)| \\ &=& 2|S_n| - |S_n \cup (m - S_n)| \end{eqnarray*} Now we bound $|S_n \cup (m - S_n)|$. We use the stupid bound of $|X| \le \max(X) - \min(X) + 1$ to get $|S_n \cup (m - S_n)| \le 2n + |m| + 1$ to yield \[ |S_n \cap (m - S_n)| \ge (2|S_n| - 2n - 1) - |m|\] Now consider an integer $n'$ such that $n' \le 2|S_n| - 2n - 1$ and $B_{n'}$ denote the bad integers $|x| \le n'$. Then clearly we must have: \begin{eqnarray*} \sum_{x \in B_{n'}} (2|S_n| - 2n - 1) - |x| & \le & 0.001n'^2 \\ \implies \sum_{x \in B_{n'}} n' - |x| \le 0.001n'^2 \end{eqnarray*} because our above result shows that within the pairs of good numbers in $S_n$ who sum to an integer $t$, if $t$ is bad it generates a certain number of gnay pairs and summing over this we get a bound on the number of gnay pairs. Now, the LHS is minimizing when $B_{n'} = \{\pm n', \pm (n'-1),...\}$. This gets us a bound of $|B_{n'}| \le \sim 2n' \sqrt{0.001}$. Now by inducting on the base case of $n \le 31$, we can prove by induction that for all $n$, $|S_n| \ge 1.9n$ because $2|S_n| - 2n - 1 > 1.7n$. The details of this are rather uninteresting.
14.04.2019 03:00
04.04.2021 23:01
Solution from Twitch Solves ISL: The answer is no. Let's say an integer is bad if $f(n) \neq n \cdot f(1)$. It is not hard to see that any bad integer must have absolute value at least $30$. Let's say a pair of integers is bad if $f(x+y) \neq f(x)+f(y)$. Claim: Let $n \ge 1$, and suppose there are $\varepsilon n$ bad integers in $[-n,n]$. Then \[ \varepsilon \left( 1 - 2 \varepsilon \right) < 0.001. \]Proof. If $\varepsilon = 0$ there is nothing to prove. Otherwise, pick a bad integer $b$ and consider \[ \ell_b = \left\{ (x,y) \mid x,y \in [-n,n], x+y=b \right\}. \](We call this a ``line'' colloquially, thinking of it in the $xy$-plane.) Note that: There are at least $n$ points on $\ell_b$. For every $(x,y) \in \ell_b$, either the pair itself is bad, or one of $x$ or $y$ is bad. (Otherwise, putting $(x,y)$ in the functional equation would contradict badness of $b$). Therefore, there are at least $n - 2\varepsilon n$ bad pairs on $\ell_b$. Taking the union across all $\varepsilon n$ lines $\ell_b$, we conclude the total number of bad pairs is at least \[ \varepsilon n \cdot (1 - 2 \varepsilon) n. \]This gives the desired result. $\blacksquare$ Note that the solution to the above quadratic is $\varepsilon < 0.001002$ and $\varepsilon > 0.498998$ (decimal approximations for convenience). Viewing $\varepsilon$ as a function $\varepsilon(n)$ now, we not that $\varepsilon(n) = 0$ initially for $n = 1, 2, \dots, 30$. There is no way for $\varepsilon(n)$ to ``jump'' in the sense that $\varepsilon(n) < 0.1$ and $\varepsilon(n+1) > 0.4$, so this ends the proof.
10.08.2022 03:50
First, some definitions: An integer $n$ is bad if $f(n) \neq nf(1)$. A pair of integers $(x,y)$ is bad if $f(x)+f(y) \neq f(x+y)$. A pair of integers $(x,y)$ is awful if at least one of $x,y$ is bad and $x+y$ is also bad. Now, fix an arbitrary $n>0$ and consider the interval $I=[n,-n]$. Slightly tweak the definition of awful to require $x+y \in I$. For every bad $k \in I$, any $(x,y) \in I^2$ with $x+y=k$ either must be bad or awful. Since for any $k$ there are at least $n$ such pairs (actually $n+1$, but because it's a global problem we don't need strict bounds LUL), if we have $k$ bad integers in $I$ then there are at least $$nk-0.001n^2$$awful pairs. It follows that there's some bad integer $B$ that's in at least $n-\frac{0,001n^2}{k}$ awful pairs. But since every awful pair generates a different bad integer as its sum, it follows that $$n-\frac{0.001n^2}{k} \leq k \implies k^2-nk+0.001n^2 \geq 0 \implies k \in \left[0,\frac{n(50-\sqrt{2490})}{100}\right] \cup \left[\frac{n(50+\sqrt{2490})}{100}\right)$$Because for small $n$ (say, $n \leq 30$), we actually need $f(x)+f(y)=f(x+y)$ for all $x,y \in [-n,n]$, which easily implies $f$ is linear over $I$, so $k$ falls in the first interval (since it's zero), and if at some point we transition between $k$ being in the first interval to the second interval for $n \geq 30$, we have to increase $k$ by more than $2$ by discrete continuity, which is impossible (I haven't actually checked the calculations but they should work out with plenty of room). Thus, $k$ stays in the first interval, so there are at most $n$ bad numbers in $[-n,n]$ (actually way less), as desired. $\blacksquare$ Remark: I did not solve this problem on my own, but here is my attempt at trying to reason through how I could've: The function defined where $f(x)=x$ for "small $x$" and $f(x)=2x$ for "large $x$" has at more than $n$ bad integers in $[-n,n]$ for large $n$, and satisfies the $0.001n^2$ condition for both large and small $n$, only breaking it in the middle. This suggests that any approach where we pick any $n$ by itself, suppose that there are more than $n$ bad integers in $[-n,n]$, and try to force a contradiction, should fail, since by picking large $n$ and the described $f$ we don't get any contradiction. On the other hand, it seems very difficult to relate different $[-n,n]$ to each other well in a "deep" way, which suggests that we should keep looking at individual $[-n,n]$ but take a step back and see what more general results we can find.
19.09.2023 21:22
The answer is no. Assume otherwise. Call an integer $n$ bad if $f(n) \neq nf(1)$, and good otherwise. Call an ordered pair of integers $(x, y)$ sobad if $f(x+y) \neq f(x)+f(y)$, and cracked otherwise. Let $\theta(n)$ be the number of bad integers with absolute value at most $n$. Now suppose $\theta(n)>0$ for some $n$. I contend that $\theta(n)(n-2\theta(n))$ is less than the number of sobad pairs $(x, y) \in [-n, n]^2$. For bad $k \in [-n, n]$, consider the pairs $(x, y) \in [-n, n]^2$ with $x+y=k$; we say that this $k$ is the height of $(x, y)$. Realize that each pair is either sobad or has exactly one bad component, so there are at least $n-2\theta(n)$ sobad pairs of height $k$. Globally summing over all bad $k$ returns a total of $\theta(n)(n-2\theta(n))$ sobad pairs, as claimed. What follows is a discrete continuity argument. Since the number of sobad pairs in $[-n, n]^2$ is $O(n^2)$, we look at $\theta(n)/n$ as we can bound it with quantities independent of $n$. In particular, \[ \left\lfloor 1000 \cdot \frac{\theta(n)}{n} \right\rfloor \in [0, 1] \cup [498, 1000]. \]Note that \[\frac{\theta(n+1)}{n+1} - \frac{\theta(n)}{n} \le \frac{n\theta(n+1)-(n+1)\theta(n)}{n(n+1)} \le \frac{2}{n+1}. \]Abusing the fact that the number of sobad pairs in $[-n, n]^2$ is $0$ when $n=0, 1, \dots, 31$, it is clear for maximal $N$ with $\theta(N)=0$, \[ \left \lfloor 1000 \cdot \left(\frac{\theta(N+1)}{N+1} - \frac{\theta(N)}{N} \right) \right\rfloor \le 1000 \cdot \frac{2}{31+1}+1 = 63.5, \]a contradiction. Remark: The global idea of partitioning a set that a sum is being taken over into subsets which have nice sums and then globally summing over those subsets is a very powerful idea, and is also featured in ISL 2020 A7.
25.10.2023 06:50
Let $x$ be green if $f(x)=xf(1)$ and red otherwise. Let $(x,y)$ be good if $f(x+y)=f(x)+f(y)$ and bad otherwise. Notice that if $x$ and $y$ are green and $x+y$ is red, then $(x,y)$ is bad. Surprisingly, we can disregard the functional structure and use only this fact to prove that there are at most $0.01n$ red numbers with absolute value at most $n$, which implies the problem. We do so by induction on $n$, with the base cases of $n \le 31$ easy. Suppose that our claim is true for $n-1$, and we want to prove it for $n \ge 32$. For any $-n \le k \le n$, there are at least $n+1$ ordered pairs of integers $(a,b)$ with $-n \le a,b \le n$ such that $a+b=k$. Out of these, the inductive hypothesis guarantees that there are at most $0.01(n-1)+2 \le 0.1n$ ordered pairs containing red elements, so there are at least $0.9n$ ordered pairs with both elements green. Thus, each red element in $[-n,n]$ corresponds to at least $0.9n$ bad pairs, so there are at most $\tfrac{0.001n^2}{0.9n} \le 0.01n$ red elements, completing the inductive step. $\square$
19.09.2024 07:38
The answer is no. Let $g(x)=f(x)-xf(1)$ so that $g$ satisfies the same conditions. Call an integer $k$ defiant if $g(k)\neq 0$, and call a pair $(u,v)$ special if $g(u+v)\neq g(u)+g(v)$. The main idea of this problem is to consider all pairs summing to a defiant number. Claim: If $k$ is defiant, then for any $u,v$ with $u+v=k$, we have that either at least one of $u$ and $v$ are defiant or $(u,v)$ is special. This clearly follows as if $u$ and $v$ are not defiant then $g(u)=g(v)=0\neq g(k)$. Let $d_n$ denote the number of defiant integers with magnitude at most $n$. Now, consider $u,v$ with $u+v=k$ for a defiant number $k$ with magnitude at most $n$. There are at least $n$ such pairs $u,v$. However, we know that at most $d_n$ of these have $u$ defiant, and similarly with $v$, so at most $2d_n$ of these pairs have a defiant component. Thus, for each defiant number, there are at least $n-2d_n$ special pairs that sum to it (all remaining pairs where neither of $u,v$ are defiant). Hence, there are at least $d_n(n-2d_n)$ special pairs, so $$d_n(n-2d_n)\leq 0.001n^2.$$ In particular, this means that $d_n$ cannot be between $0.01n$ and $0.49n$. Furthermore, for $n\leq 31$, there are no unique pairs, so $g(n)=0$ for all $|n|\leq 30$ and thus $d_n=0$ for $n\leq 30$. However, since $d_{n+1}\in \{d_n,d_n+1,d_n+2\}$, there is clearly no way to avoid the interval from $0.01n$ to $0.49n$ as it has width greater than $2$. Hence, $d_n$ can never exceed $n$ (or even $0.01n$ for that matter), as desired. remark-- i think an important thing to realize about this problem is that there are functions $f$ that satisfies the problem conditions for sufficiently large $n$ (like $f(x)=x$ except $f(1)=0$), which means that the "initial" conditions are somehow also important. moreover, it is also possible to satisfy the condition for as long as we want, start breaking it, and restore it for sufficiently large $n$ again (e.g. $f(x)=0$ for $|x|\leq 1434$ and $f(x)=x$ for $|x|>1434$). what all of this means is that, not only do we have to look at "initial" and "sufficently large" states, but somehow also incorporate the transition between the two. through the above examples, it's intuitive that attempting to make such a transition will cause the condition to temporarily break. This manifests in the IVT-type argument in the solution.