Let $\mathbb Z$ be the set of integers. We consider functions $f :\mathbb Z\to\mathbb Z$ satisfying \[f\left(f(x+y)+y\right)=f\left(f(x)+y\right)\]for all integers $x$ and $y$. For such a function, we say that an integer $v$ is f-rare if the set \[X_v=\{x\in\mathbb Z:f(x)=v\}\]is finite and nonempty. (a) Prove that there exists such a function $f$ for which there is an $f$-rare integer. (b) Prove that no such function $f$ can have more than one $f$-rare integer. Netherlands
Problem
Source: 2019 ISL A7
Tags: algebra, IMO Shortlist, IMO Shortlist 2019, functional equation, arithmetic sequence
23.09.2020 02:24
I didn't find this that bad for an A7. a) We leave the reader to verify that $$f(n)=\begin{cases} 0,\, &n=0 \\ 2^{\nu_2(n)+1},\, &n\neq0 \end{cases}$$works, with $0$ being $f$-rare. b) Suppose such a function $f$ had two $f$-rare integers $u$ and $v$. Assume that $u<v$, and write $X_u=\{u_1,u_2,\dots, u_m\}$ and $X_v=\{v_1,v_2,\dots, v_n\}$, where $u_1<u_2<\dots < u_n$ and $v_1<v_2<\dots < v_n$ so that, by definition. \[ \begin{cases} f(u_1)=f(u_2)=&\cdots = f(u_m)= u, \\ f(v_1)=f(v_2)=&\cdots = f(v_n)=v.\end{cases}\]Claim: $f(u)=u$ and $f(v)=v$. Proof: Let $x=u$ and $y=u_i-u$ (for a later chosen $i$) in the equation to obtain \begin{align*} f(f(u_i)+u_i-u)&=f(f(u)+u_i-u) \\ \implies u &= f(f(u)+u_i-u) \end{align*}so $f(u)+u_i-u\in U_x$. It follows that $u_1\leq f(u)+u_i-u\leq u_n$ for all $1\leq i\leq n$. Then by taking $i=1$ and $i=n$, we see that $f(u)=u$. Similarly, $f(v)=v$, proving the claim. $\blacksquare$ With this in mind, the following observation kills the problem: Claim: $u+na\in X_v$ for all positive integers $n$, where $a=v-u>0$. Proof: This is an easy induction - the base case is easy to verify, and if the claim was true for $n=k$, putting $x=u$ and $y=ka$ in the equation yields \begin{align*}f(f(u+ka)+ka)&= f(f(u)+ka) \\ \implies f(v+ka)&= f(u+ka) \\ \implies f(u+(k+1)a) &= v \end{align*}so $u+(k+1)a\in X_v$, completing the induction. $\blacksquare$ Since $a>0$, this claim shows that there are infinitely members in $X_v$, a contradiction. Hence there cannot be two $f$-rare integers.
23.09.2020 02:26
The FE is clearly equivalent to \[f(f(x)+d)=f(f(y)+d)\]if $d\mid x-y$. The key claim is as follows. Claim: If $v$ is $f$-rare, then $f(v)=v$. Proof: Let $f^{-1}(v) = \{x_1<\ldots<x_n\}$. Fix any $x$, and let $d=x_i-f(x)$. Then, \[f(f(x+kd)+d)=v,\]so \[f(x+k(x_i-f(x_i)))+x_i-f(x)\in\{x_1,\ldots,x_n\},\]so \[f(x+k(x_i-f(x_i)))\in f(x)+\{x_1-x_i,\ldots,x_n-x_i\}.\]Thus, taking $i=1$ and $i=n$, we see that \[f(x+k(x_1-f(x_1))(x_n-f(x_n)))\in f(x)+[\{x_1-x_1,\ldots,x_n-x_1\}\cap\{x_1-x_n,\ldots,x_n-x_n\}]=\{f(x)\},\]so \[f(x+k(x_1-f(x_1))(x_n-f(x_n))) = f(x).\]Taking $x=x_i$ then shows that there are infinitely many $f(x)=v$ unless $x_1=f(x_1)$ or $x_n=f(x_n)$. Thus, $v\in\{x_1,x_n\}$, so $f(v)=v$. $\blacksquare$ The problem is just computation now. Indeed suppose we had $f(v)=v$ and $f(w)=w$. Then, taking $d=v-w$, we have \[f(2v-w)=f(v)=v\]and similarly $f(2w-v)=w$. Taking $d=(2v-w)-w$, we see \[v=f(2v-w)=f(3v-2w),\]and continuing similarly gives $f((k+1)v-kw)=v$ for all $k$. If $v\ne w$, then this contradicts finiteness of $f^{-1}(v)$, so we're done. For a construction, take $f(x)=2^{v_2(x)+1}$ for nonzero $x$ and $f(0)=0$. Unclear how this is motivated though.
23.09.2020 09:47
Comment: One of the best FE I have ever seen for a while. In my opinion, this is a perfect problem for IMO 3/6, but sadly did not get selected. (a) An example is $f(0)=0$ and $f(x)=2^{\nu_2(x)+1}$ for $x\ne 0$. (b) Suppose there exists two $f$-rare integers $A<B$ and let the preimages of $A, B$ are $\mathcal{A} = \{a_1<a_2<\hdots<a_m\}$ and $\mathcal{B} = \{b_1<b_2<\hdots<b_n\}$. First, we extend the functional function to $$f(f(x+ny) + y) = f(f(x)+y)\qquad (*)$$for any $x,y,n\in\mathbb{Z}$. Now we prove the following key claim. Claim: For any $t\in\mathbb{Z}$ we have \begin{align*} f[t+(a_1-f(t))(b_n-f(t))] &= f(t) \\ f[t+(a_m-f(t))(b_1-f(t))] &= f(t) \end{align*} Proof. We will prove only the first one, since the second one follows analogously. We note that for any $N\in\mathbb{Z}$, $$f[f(t+N(a_1-f(t))) + (a_1-f(t))] = f(a_1) = A $$thus $f[t+N(a_1-f(t))] + a_1 - f(t)\in \mathcal{A}$. In particular, if $N=b_n-f(t)$, we get that $$K\stackrel{\text{def}}{=} f[t+(a_1-f(t))(b_n-f(t))] - f(t) \in (\mathcal{A}-a_1)$$Similarly, we get that $K\in (\mathcal{B}-b_1)$. However, from ordering, we get that $(\mathcal{A}-a_1)$ consists of only nonnegative numbers while $(\mathcal{B}-b_1)$ consists of only nonpositive numbers. Thus $K=0$, hence the claim.$\blacksquare$ Thus from the claim, we vary $t\in\{a_1,a_2,\hdots,a_n\}$, we see that $$\mathcal{A} + (a_1-A)(b_n-A) = \mathcal{A}$$which forces $a_1=A$ or $b_n=A$. Similarly, $a_1=B$ or $b_n=B$. Hence $\{a_1,b_n\} = \{A,B\}$. Analogously, we get $\{a_m,b_1\} = \{A,B\}$. This forces $m=n=1$ and $\{a_1,b_1\} = \{A,B\}$. Thus $\{f(A),f(B)\}=\{A,B\}$. However, from $(x,y)=(A,B-A)$ in the original equation, we get $f(B)=f(2B-A)$, which means $B=2B-A$ or $A=B$, contradiction.
24.09.2020 11:12
IMOSL 2019 A7 wrote: Let $\mathbb{Z}$ be the set of integers. We consider functions $f : \mathbb{Z} \rightarrow \mathbb{Z}$ satisfying $f(f(x+y)+y)=f(f(x)+y)$ for all integers $x$ and $y$. For such a function, we say that an integer $v$ is $f$-rare if the set $X_v = \{ x \in \mathbb{Z} : f(x)=v \}$ is finite and nonempty. (a) Prove that there exists such a function $f$ for which there is an $f$-rare integer. (b) Prove that no such function $f$ can have more than one $f$ -rare integer. Dolution] For part a), I skip the calculation bash for the reader but we give the construction : $f(0)=0$ $f(x) = 2^{\nu _2 \left (\mid 2x \mid\right )}$ for all $x \neq 0$. This construction looks unmotivated but I started with function $f(0)=0$ and $f(x)=2^{\nu _2\dots}$ because $f(x+y)=f(x)$ looks similar if $\nu _2(y) > \nu _2(x)$ and hence I got this construction. Now, for part b), suppose $v_1, v_2$ are two $f$-rare integers. Now observe that there exists a translation of $f$ which preserves $f$-rare property and satisfies the condition. There are many such translation, one is $x \mapsto f(x+n)-n$. See why this preserves our $f$-rare condition. Hence, we do proper translation so that $0$ is also $f$-rare. Now, see that is $P(x, y)$ is the assertion,and if $a_1, a_2 ... a_i$ are elements of $X_{v_1}$, then $P(v_1, a_1-v_1) \implies f(v)-v+a_1 \in X_{v_1}$, but this means that $f(v) \geq v$ as the other way round implies $\exists$ $p < a_1$ such that $f(p)=v_1$, a contradiction. So, we similarly have $f(v) \leq v$ by $P(v_1, a_i-v_)$ and so $f(v_1)=v_1$. We use induction to show that $f(kv_1)=v_1$ for all naturals $k$. See that if it is true for some natural $n$, then $P(0, nv_1) \implies f(nv_1+v_1)=f(nv_1)$ which means that using induction, there exists infinitely many $q$ such that $f(q)=v_1$ which contradicts the fact that $v_1$ is $f$-rare, hence using translation we get that there cannot exist two $f$-rare integers
15.10.2020 17:37
ayan_mathematics_king wrote: This construction looks unmotivated but I started with function $f(0)=0$ and $f(x)=2^{\nu _2\dots}$ because $f(x+y)=f(x)$ looks similar if $\nu _2(y) > \nu _2(x)$ and hence I got this construction. Here's how I motivated $f(x)=\begin{cases} 0\ &(x=0) \\ 2^{\nu_2(x)+1}\ &(x\neq0) \end{cases}$ for part (a): It is natural to solve part (b) first, so it's easy to deduce that if $v$ is a $f$-rare integer, then $f(v)=v$. Now noting that the transformation $f(x) \mapsto f(x+u)-u$ for some integer $u$ also leads to a vaild solution, WLOG we can set $f(0)=0$ and $0$ be the unique $f$-rare integer(or you could just put $f(0)=0$ by instinct). Then from the assertion we have $f(y+nf(y))=f(y)$ for any integer $n, y$. Now we seek to determine $f(1)$. We first try $f(1)=1$, but this fails since $0=f(1-1f(1))=f(1)=1$. Now we try $f(1)=2$. Then $f(2n+1)=f(1+nf(1))=f(1)=2$, so $f$ maps odd integers to $2$. We now proceed to determine $f(2)$. If $f(2)$ is odd, then $f(2+f(2))=2=f(2)$, contradiction. Hence $f(2)$ should be even, but $f(2)=2$ fails since $f(2-f(2))=f(2)=0$. The next natural approach is to take $f(2)=4$, which leads to $f(4n+2)=f(2)=4$. Note that now we have the "$v_2$ hierarchy" of $f$. After noticing the "$v_2$ hierarchy", you'll get the above description of $f$ if you play along with negative numbers as well. As a sidenote, you can get (infinitely many) solutions by slightly modifying the initial values here.
16.10.2020 13:54
MarkBcc168 wrote: Comment: One of the best FE I have ever seen for a while. In my opinion, this is a perfect problem for IMO 3/6, but sadly did not get selected. The problem was not popular with the jury members, as the statement was considered to be unusually long and convoluted for a functional equation. After the selection of the four easy and medium problems, it dropped out of the competition, as there was already another function equation on the paper.
16.10.2020 14:13
lminsl wrote: ayan_mathematics_king wrote: This construction looks unmotivated but I started with function $f(0)=0$ and $f(x)=2^{\nu _2\dots}$ because $f(x+y)=f(x)$ looks similar if $\nu _2(y) > \nu _2(x)$ and hence I got this construction. Here's how I motivated $f(x)=\begin{cases} 0\ &(x=0) \\ 2^{\nu_2(x)+1}\ &(x\neq0) \end{cases}$ for part (a): It is natural to solve part (b) first, so it's easy to deduce that if $v$ is a $f$-rare integer, then $f(v)=v$. Now noting that the transformation $f(x) \mapsto f(x+u)-u$ for some integer $u$ also leads to a vaild solution, WLOG we can set $f(0)=0$ and $0$ be the unique $f$-rare integer(or you could just put $f(0)=0$ by instinct). Then from the assertion we have $f(y+nf(y))=f(y)$ for any integer $n, y$. Now we seek to determine $f(1)$. We first try $f(1)=1$, but this fails since $0=f(1-1f(1))=f(1)=1$. Now we try $f(1)=2$. Then $f(2n+1)=f(1+nf(1))=f(1)=2$, so $f$ maps odd integers to $2$. We now proceed to determine $f(2)$. If $f(2)$ is odd, then $f(2+f(2))=2=f(2)$, contradiction. Hence $f(2)$ should be even, but $f(2)=2$ fails since $f(2-f(2))=f(2)=0$. The next natural approach is to take $f(2)=4$, which leads to $f(4n+2)=f(2)=4$. Note that now we have the "$v_2$ hierarchy" of $f$. After noticing the "$v_2$ hierarchy", you'll get the above description of $f$ if you play along with negative numbers as well. As a sidenote, you can get (infinitely many) solutions by slightly modifying the initial values here. Hello. Now that I remember about this problem, I sincerely thank ayan mathematics king for posting my solution. I get your approach well. I first noticed the transformation one. Because this seemed like a strange yet beautiful FE like IMO 2017 P2, and there we can minimise casework by considering that if $f$ works then $-f$ works too(In IMO 2017 P2) and so we can solve just one case in that problem, and hence I found this transformation. Then I seeked for $\nu _2$ as I knew that all other functions in terms of $rad(x)$, $\phi (x)$ won't work. Simply observable. So I worked on the function of that form. Obviously if $2^{x\nu _2 (n) + y}$ works then we do that operation on two odd numbers, eventually in a step getting $f(\mathrm{odd}) = 2$. So $y=1$. Hence, I now figured out that $x=1$ too, look at bounds of one or two examples of the operarions I'd already listed out. TelMarin wrote: MarkBcc168 wrote: Comment: One of the best FE I have ever seen for a while. In my opinion, this is a perfect problem for IMO 3/6, but sadly did not get selected. The problem was not popular with the jury members, as the statement was considered to be unusually long and convoluted for a functional equation. After the selection of the four easy and medium problems, it dropped out of the competition, as there was already another function equation on the paper. In my honest and humble opinion, $N3$ instead of $A1$ and $A7$ instead of $C5$ would've worked really well. $N3$ isn't as tough as few people claim and just needs one crucial observation, unlike $A1$ which is though nice Olympiad problem, easy for even those not that comfortable with function.
16.10.2020 14:52
DapperPeppermint wrote: In my honest and humble opinion, $N3$ instead of $A1$ and $A7$ instead of $C5$ would've worked really well. The jury is using a weird protocol for problem selection that is hampering its work and that would make your choice practically impossible. Before the fixing of the two hard problems, the jury had selected easy problems A1 and N1 and medium problems G3 and C3. If you want to replace easy A1 by easy N3, you also must remove easy N1 and add some easy algebra problem instead. And then your new easy algebra problem must not be on the same day as your A7. Or you remove one of the medium problems G3 and C3 by medium algebra and introduce easy G or easy C. (And you must be able to implement all this via the voting process at the jury meeting.)
06.11.2020 21:26
This may seem short and simple but it's really not. Worth every second of the full-day grind. As per usual, let $P(x,y)$ be the received assertion upon plugging $x$ and $y$ to the given FE. For part (a), we consider the function $f(0) = 0$, and $f(n) = 2^{v_{2}(n)+1}$. We can verify this in two steps: $\textcolor{blue}{\text{(a), Case 1:}}$ $x = 0$ or $x+y = 0$. By symmetry or setting $x+y = x', x = x'+y'$, we can just consider the case $x = 0$. But, letting $v_2(y) = v$, LHS = $v_2(2^{v+1}+y)$ is equal to $v$, which is equal to RHS = $v_2(0+y)$. $\textcolor{blue}{\text{(a), Case 2:}}$ The rest of the integers. Also letting $v_2(y) =v$, if $v_2(x) \geq v_2(y)$, we can easily obtain $v_2(f(x+y)+y) = v_2(2^{\text{something} \geq v+1} + y) = v$, and similarly $v_2(f(x)+y) = v$. If $v_2(x) < v_2(y)$, we can infer that $f(x+y) = 2^{v_2(x+y)+1}$ is the same number as $f(y) = 2^{v_2(x)+1}$, because $v_2(x+y) = v_2(x)$. For part (b), we use the following $\textit{Lemma}$. $\textbf{Lemma.}$ If $b$ is a $f-rare$ integer, with $f(b) = b$, then there are no two $f-rare$ numbers. $\textbf{Proof.}$ For every number $r \ne b$, we would like to prove it being $ not \, \, f-rare$. Firstly, if $r$ is not in $range(f)$, then obviously the set $X_r$ is empty, implying $r$ not $f-rare$. Let $f(c) = r$. $P(b,c-b)$ implies $f(y) = f(f(b+c-b)+c-b) = f(c+r-b)$. So, we get that $f(c) = r$ implies $f(c+ (r-b)) = r$, too. Provided that $r \ne b$, i.e. $r-b \ne 0$, by induction we can obtain that $\{c+k(r-b)\} \in X_r$, implying $r$ not $f-rare$. $\textbf{[End of Lemma's Proof]}$ We now proof that for every $v$ $f-rare$, $f(v)$ is indeed $v$. Let the minimum value in $X_v$ be $a$ and maximum is $b$ (they exist because $X_v$ is bounded). Let $f(v) \ne v$. $\textcolor{blue}{\text{(b) - Case 1:}}$ $f(v) < v$. $P(v,a-v)$ implies $f(f(v)+a-v) = f(a)$. Then, some number $a+f(v)-v$ also is in $X_v$, contradiction. $\textcolor{blue}{\text{(b) - Case 2:}}$ $f(v) > v$. Same working with $a$ replaced with $b$. We are done.
23.05.2021 09:04
Really amazing and hard problem!, It has a short solution but it is not easy at all! . Solved with Pujnk, Psyduck909 Part (a): The magical function $f(0) = 0$ and $f(x) = p^{v_p(x)+1}$ works where $p$ is any prime (Other solutions in the thread only use $p = 2$) To show this works, we just need to show that $v_p(p^{v_p(x+y)+1}+y) = v_p(p^{v_p(x)+1}+y)$. If $v_p(x) < v_p(y)$, then this is obvious since it means $v_p(x+y) = v_p(x)$. If $v_p(x) \ge v_p(y)$, then we get that the $v_p$ of both sides is $v_p(y)$ and the function works in this case too Part (b): Let $a$ be an $f$-rare integer, and let $A = X_a$ for convenience. Let $P(x,y)$ denote the given assertion. Claim 1: $f(a) = a$ Proof: Suppose $p$ is an element of $A$, then $P(a,p-a)$ gives that $f(f(p)+p-a) = f(f(a)-a+p) \implies f(p+f(a)-a) = a$ and so if we let $c = f(a) - a$, we get that if $p \in A \implies p+c \in A$. If $c \neq 0$, then this means that there are infinite elements in $A$, which is impossible since $a$ is $f-$rare. So, $c = 0 \implies f(a) = a$, as claimed. $\blacksquare$ Claim 2: $a$ is the only fixed point of $f$ Proof: Suppose $f(b) = b$ and $b \neq a$. Then $P(b,p-b)$ gives that $f(f(p)+p-b) = f(f(b)+p-b) \implies f(p+a-b) = a$ and so letting $c = a-b \neq 0$, we get that $p \in A \implies p+c \in A$, which again means that $|A| = \infty$, which is impossible, so $a$ is the only fixed point of $f$ $\blacksquare$ So now, suppose there were two $f$-rare integers $a,b$. Then $f(a) = a$ and $f(b) = b$ by claim 1, which is impossible by claim 2. Therefore, there cannot be two $f$-rare integers
24.05.2021 14:23
dame dame
26.05.2021 22:10
Amazing Problem!!! a) We see that the function defined by $f(0) = 0$ and $f(x) = 2^{\nu_2(x)+1} $ for $x\neq 0$ works and has $0$ as an $f-rare$ integer.
b) Let $f$ be a function satisfying the condition , note that we can repeatedly apply the condition and rewrite it as $$P(x,y,n) : \hspace{0.5cm} f(f(x+ny)+y) = f(f(x)+y) \hspace{0.5cm} \text{ where } x,y,n \in\mathbb{Z}$$ Claim - If an integer $u$ is $f-rare$, then $f(u)=u$. Proof - Let $u$ be $f-rare$, let $P = \Pi_{a\in X_u}(a-u)$. Let $m = Pk +u$ for some integer $k$. Let $a\in X_u \implies a-u $ divides $m-u$ and hence also $m-u-(a-u)=m-a \implies m = (a-u)n+a$ . $P(a,a-u,n) \implies f(f(m)+a-u) = f(f(a)+a-u)=f(u+a-u)=f(a)=u $ Hence we have that $a \in X_u \implies a+f(m)-u \in X_u$ , as $X_u$ is finite this forces $f(m) = u$ and hence $m\in X_u$. But again $m$ was $Pk+a$ and finiteness of $X_u$ gives that $P=0 \implies u \in X_u \implies f(u)=u$ as desired. Now to finish the problem assume that there exists an $f-rare$ integer $v$ other than $u$ and let $s=v-u$. Let $Q(y)$ denote $P(u,y,1)$, that is $Q(y) : f(f(u+y)+y) = f(u+y)$ . $Q(s) \implies f(v+s) = v $ , assume $f(v+ks) = v$, $Q((k+1)s) \implies f(v+(k+1)s) = f(v+ks) = v$ Hence by induction $v+ks \in X_v$ for all positive integers $k$. As $u\neq v$ $s \neq 0$ This contradicts finiteness of $X_v$. Hence proved .
27.05.2021 07:29
I'll admit, this problem is super nice. Let $P(x,y)$ denote the assertion $f\left(f(x+y)+y\right)=f\left(f(x)+y\right)$. a) The function $$f(n)=\begin{cases} 0,\, &n=0 \\ 2^{\nu_2(n)+1},\, &n\neq0 \end{cases}$$works, with $0$ being $f$-rare. Casework is omitted. b) Suppose for the sake of contradiction that there are at least two $f$-rare integers, then pick two of these to be $v > u$. Let $S_u = \{x \mid f(x) = u\}$ and $S_v = \{x \mid f(x) = v\}$, and denote the elements of these sets by $u_1 < \ldots < u_m$ and $v_1 < \ldots < v_n$ respectively. Lemma 1: We have $f(u) = u$ and $f(v) = v$. Proof: $P(u, u_i - u) \implies u = f(f(u)-u+u_i)$ for arbitrary $u_i \in S_u$. Hence $f(u)-u + u_i \in S_u$. Now, if $f(u) < u$ then take $i=1$, so $f(u)-u+u_1 < u_1$ and if $f(u) > u$, then take $i=m$ which implies $f(u) - u + u_m > u_m$. Both of these are strictly outside the range of $S_u$, which is a contradiction. This implies $f(u)=u$ as required. By applying the proof analogously for $v$ we obtain $f(v) =v$. $\square$ We are now on the final stretch of the problem. Final claim: If $f(nv- (n-1)u) = v$ then $f((n+1)v-nu)=v$ for $n \in \mathbb{Z}_{>0}$. We proceed by induction. Clearly, if $n=1$ then this statement is true as $f(v)=v$. Now, assume that this statement is true for $n=k$. $P(u,k(v-u)) \implies f( f(kv-(k-1)u) + k(v-u)) = f( kv - (k-1)u)$. So $f((k+1)v - ku) = v$, thus this statement is true for all positive $n$ as required. $\square$ This is enough to conclude the problem, because by setting $k$ to be some arbitrarily large positive integer such that $v + k(v-u) > v_n$ we have that this is a contradiction to the finiteness of $S_v$. Thus the proof is concluded.
28.10.2021 18:45
naman12 wrote: Let $\mathbb Z$ be the set of integers. We consider functions $f :\mathbb Z\to\mathbb Z$ satisfying \[f\left(f(x+y)+y\right)=f\left(f(x)+y\right)\]for all integers $x$ and $y$. For such a function, we say that an integer $v$ is f-rare if the set \[X_v=\{x\in\mathbb Z:f(x)=v\}\]is finite and nonempty. (a) Prove that there exists such a function $f$ for which there is an $f$-rare integer. (b) Prove that no such function $f$ can have more than one $f$-rare integer. Netherlands Looked simple for an A7 so correct me if I am wrong For part a), the construction is same as the others in the thread, that is $$f(n)=\begin{cases} 0,\, &n=0 \\ 2^{\nu_2(n)+1},\, &n\neq0 \end{cases}$$ Part b) is the real fun As always, let \(P(x,y)\) denote the assertion of the functional equation. Assume that \(u\) and \(v\) (\(u\neq v\)) are \(f\)-rare. Then let \(a_i\), \(1\leq i\leq n\) be the domains which give range \(u\) and let \(b_i\), \(1\leq i\leq v\) be the domains which give range \(v\). Then, \(P(u,a_i-u)\) gives us \[f(f(u)+a_i-u)=f(f(a_i)+a_i-u)=u\]so \(f(u)+a_i-u\) is in one of the \(a_j's\). Wlog if \(a_i\) is increasing, then we have \[a_1\leq f(u)+a_i-u\leq a_n\]for all \(i\) and plugging \(i=1,n\) gives us \(f(u)=u\). Similarly \(f(v)=v\). This step is the master blaster: \(P(u,v-u)\) gives us that \[f(f(v)+v-u)=f(f(u)+v-u)=v\]so \(f(2v-u)=v\). Inductively arguing, we see that \(f(kv-u)=u\) and by the definition of a rare subset, there are distinct \(k,l\) with \(ku-v=lu-v\) implying that \(u=0\). Similarly, \(P(v,u-v)\) would give us that \(v=0\), implying that \(u=v\), a contradiction. This completes the proof of part b).
26.12.2021 16:03
Easy for A7 Our construction for part $(a)$ is $f(0)=0$ and $f(x)=2^{\nu_2(x)+1}\forall x\ne0$. By casework on $\nu_2(x)$ and $\nu_2(y)$, we can find that this construction works, and $0$ is the $f$-rare integer. Now we will prove part $(b)$. AFTSOC there exist $u$ and $v$ with $u<v$ that are both $f$-rare integers. Let $X_u=\{u_1,u_2,u_3,\ldots,u_n\}$ with $u_1<u_2<\ldots<u_n$ and $X_v=\{v_1,v_2,v_3,\ldots,v_n\}$ with $v_1<v_2<\ldots<v_n$. Let $P(x,y)$ denote the assertion of the FE. Claim: $u\in X_u$ and $v\in X_v$ $P(u,u_i-u): u=f(f(u)+u_i-u)$ Thus, $f(u)+u_i-u\in X_u$, so $u_1\le f(u)+u_i-u\le u_n$. Taking $i=1$ gives $f(u)-u\ge 0$ and taking $i=n$ gives $f(u)-u\le 0$, so $f(u)=u\implies u\in X_u$. Proceed similarly for $v$ to get $v\in X_v$. Now we will show by induction that $u+n(v-u)\in X_v$ for all positive integers $n$. Base case: $n=1$ obvious from our above claim. Inductive step: Suppose $u+k(v-u)\in X_v$ for all $k\le n$. \[P(u,n(v-u)): f(f(u+n(v-u))+n(v-u))=f(f(u)+n(v-u))\implies f(v+n(v-u))=f(u+n(v-u))\implies f(v+n(v-u))=f(u+(n+1)(v-u))=v\]which completes the induction. Thus, $X_v$ is infinite, a contradiction.
19.04.2022 12:33
I found this one a bit hard, unlike others
02.06.2022 13:43
Construction: $f(0)=0$ and $f(a)=2^{\nu_2(a)+1}$ for nonzero $a,$ it can be verified that it works. Let $P(x,y)$ denote the given assertion. Claim 1: If $v$ is rare then, $f(v)=v.$ Proof. Let $M$ and $m$ be the maximum and minimum elements of $X_v$ respectively. Let $M-v=N$ and $m-v=n.$ The claim follows from $P(v,N)$ and $P(v,n).$ $\blacksquare$ Claim 2: Only $v$ is rare. Proof. Let $w$ be another rare. We prove by induction that $f(cv-cw+v)=v$ for all $c.$ For $c=1$ use $P(u,v-u).$ Assume it's true for $c=\gamma,$ then by $P(u,\gamma v-\gamma w)$ we get that it's true for $\gamma +1.$ It forces $v=w$ for $X_v$ finite. $\blacksquare$
15.06.2022 04:14
06.01.2023 23:20
(a) By a straightforward check function $$f(x)=\begin{cases} 0,\, &x=0 \\ 2^{v_2(2x)},\, &x\in \mathbb Z \backslash \left \{ 0\right \} \end{cases}$$satisfies the equation and has $f-$rare integer $0.$ (b) Claim 1. If $f(x)$ satisfies the equation, then $g(x)=f(x+n)-n$ for $n\in \mathbb Z$ satisfies too. Proof. We have $g(g(x+y)+y)=f(f((x+n)+y)+y)-n=f(f(x+n)+y)-n=g(g(x)+y)$ $\Box$ Claim 2. Any $f-$rare integer $t$ satisfies $f(t)=t.$ Proof. Define $m=\min X_t,M=\max X_t.$ Substituting $x=t,y=m-t$ and $x=t,y=M-t$ we obtain $$f(f(t)+m-t)=f(f(m)+m-t)\implies (f(t)+m-t)\in X_t\implies f(t)\geq t$$$$f(t)+M-t\in X_t\implies f(t)\leq t\implies f(t)=t \quad \Box$$ Due to the first claim we can WLOG assume that $0$ is $f-$rare. Hence it suffices to prove the following Claim 3. Any $f-$rare integer $s$ satisfies $f(ks)=s$ for an arbitrary $k\in \mathbb Z^+.$ Proof. Induct on $k,$ using the claim $2$ as the base case $k=1$. Next $$f((k+1)s)=f(f(0+ks)+ks)=f(f(0)+ks)=f(ks)=s\quad \Box$$
23.04.2023 17:19
Struggling to find a function was a great fun! I hope something like those problems will appear on IMO 2023... $$P(x,y):\hspace{0.5cm} f(f(x+y)+y)=f(f(x)+y)$$(a) Let $f(x)=\begin{cases} 0 & \text{ if } x=0 \\ 2^{\nu_2(x)}+1 & \text{ otherwise } \end{cases}$ For checking this function we check the following cases: Case1: $x+y=0$ This is equivalant to $f(y)=f(f(-y)+y)$. if $y=0$ then we are done. now assume that $y=2^{\nu_2 (y)}h$ for $h=\text{odd}$: $$\text{RHS}=f(2^{\nu_2(y)+1}+y)=f(2^{\nu_2(y)+1}+2^{\nu_2(y)}.h)=2^{\nu_2(y)+1}=\text{LHS}$$ Case2: $x=0$ Equivalent to $f(y)=f(f(y)+y)$ which can be checked by the same as above. Case3: otherwise \begin{align*} \nu_2(x)\geq \nu_2(y) &\Rightarrow \nu_2(x+y)+1>v_2(y) \Rightarrow \text{LHS}=2^{\nu_2(y)+1}=\text{RHS} \\ \nu_2(x)<\nu_2(y) &\Rightarrow \text{LHS}=f(2^{\nu_2(x)+1}+2^{\nu_2(y)}.h)=\text{RHS} \end{align*} (b) Assume FTSoC that such a function $f$ exists: Claim1: we can assume that $0=f$-$\text{rare}$ Proof: define $g:\mathbb{Z}\rightarrow\mathbb{Z}$ such that $g(x)=f(x+a)-a$ \begin{align*} P(x,y-a):\hspace{0.5cm} & f(f(x+y-a)+y-a)=f(f(x)+y-a)\\ \Longleftrightarrow & g(g(x+y)+y)=g(g(x)+y) \end{align*}and we are done. Claim2: $f(0)=0$ Proof: by claim1, assume $\max(X_0)=M$ and $\min(X_0)=m$, then: \begin{align*} P(0,M):\hspace{0.5cm} &0=f(f(0)+M) \Rightarrow f(0)\leq 0\\ P(0,m):\hspace{0.5cm} &0=f(f(0)+m) \Rightarrow f(0)\geq 0 \end{align*}hence $f(0)=0$. Claim3: $f(y)=f(kf(y)+y)\hspace{0.2cm} \forall k\in\mathbb{Z}_{\geq 0}\dots \bigstar $ Proof: $$P(0,y)\hspace{0.5cm} f(y)=f(f(y)+y)\dots \spadesuit$$We proceed by induction, assume the claim is true for $k\in \mathbb{Z}_{\geq 0}$: \begin{align*} f(y)&= f(kf(y)+y)\overset{\spadesuit}{=} f(f(kf(y)+y)+kf(y)+y)\\ &=f(f(y)+kf(y)+y)=f((k+1)f(y)+y) \end{align*}and we are done.$\square$ (base case $k=0$ is trivial) Now from $\bigstar$ we have either $f(y)=0$ or $f(y)\neq 0$, the later one gives us: $$kf(y)+y \in X_{f(y)}\hspace{0.2cm} \forall k\in \mathbb{Z}_{\geq 0}$$hence there is only one $f$-$\text{rare}$ integer which is zero, a contradiction. $\blacksquare$
28.09.2023 02:52
(a) Just note by some guess that $f(x)=p^{v_p(x)+1}$ for all integers $x \ne 0$ and $f(0)=0$ for $p$ prime works, having $0$ as its $f$-rare integer. (b) Suppose FTSOC $a,b$ are both different $f$-rare integers, set $X_a=\{a_1, a_2, ..., a_i\}$ and $X_b=\{b_1, b_2, ..., b_j \}$ where $a_1 \le a_2 \le ... \le a_i$ and $b_1 \le b_2 \le ... \le b_j$, now call $P(x,y)$ the assertion of the given F.E., we go with some Claims. Claim 1: If $\ell$ is $f$-rare for $X_{\ell}=\{\ell_1, \ell_2, ..., \ell_m \}$ then $f(\ell)=\ell$ Proof: Order $\ell_1 \le \ell_2 \le ... \le \ell_m$, now by $P(\ell, \ell_i-\ell)$ we get that $$\ell=f(\ell_i)=f(f(\ell_i)+\ell_i-\ell)=f(f(\ell)+\ell_i-\ell) \implies \ell_1 \le f(\ell)+\ell_i-\ell \le \ell_m \; \forall 1 \le i \le m \; \implies \ell \ge f(\ell) \ge \ell \implies f(\ell)=\ell$$Claim 2: $a+n(b-a) \in X_b$ for all posititve integers $n$. Proof: we go by induction over $n$, the base case $n=1$ holds by Claim 1 so now by $P(a, n(b-a))$ and the inductive hypotesis assuming it holds for $n$. $$f(a+(n+1)(b-a))=f(b+n(b-a))=f(f(a+n(b-a))+n(b-a))=f(f(a)+n(b-a))=f(a+n(b-a))=b \implies a+n(b-a) \in X_b \; \forall n \in \mathbb Z_{>0}$$Finishing: Note that $X_b$ is infinite thus we get a contradiction, hence $f$ has at most one $f$-rare integer solving part b, and thus solving the whole problem .
23.12.2023 13:48
this is a really interesting problem, and deserving of an A7 spot, despite its seemingly easy solution. I think the solution is very difficult to come up with, and to me the problem did not feel as easy as some of my fellow posters above claim (although this could be due to lack of skills in solving FEs) tl;dr short solution does not mean easy problem
24.12.2023 20:18
Assume $v$ to be $f$-rare. Let $a$ and $b$ be the smallest and largest elements of the finite non-empty set $X_v$. Claim : $f(x) = f(x + k\cdot (f(x)-a)(f(x)-b))$ for all $x, k \in \mathbb{Z} \dots [\diamondsuit]$. Proof : Repeating the given equation for $x\rightarrow x\pm y$, we get $P(x,y) : f(f(x+ny)+y)=f(f(x)+y)$ for any $n \in \mathbb{Z}$. $P(x,a-f(x)) : f( f(x+n(a-f(x))) + a - f(x)) = f(a) =v \implies f(x+n(a-f(x))) + a - f(x) \in X_v$. Since $a$ is the smallest element of $X_v$, we must have that $f(x+n(a-f(x))) \geqslant f(x)$ for any $x,n \in \mathbb{Z}$. $P(x,b-f(x)) : f( f(x+m(b-f(x))) + b - f(x)) = f(b) =v \implies f(x+m(b-f(x))) + b - f(x) \in X_v$. Since $b$ is the largest element of $X_v$, we must have that $f(x+m(b-f(x))) \leqslant f(x)$ for any $x,m \in \mathbb{Z}$. The last two bounds bounds together that $$f(x+n(a-f(x))) \geqslant f(x) \geqslant f(x+m(b-f(x))) \text{ for any } x,n,m \in \mathbb{Z}$$Now take $n=k\cdot(b-f(x))$ and $m=k\cdot(a-f(x))$. Equality must hold everywhere in the above equation, and we have proven the claim! $\blacksquare$ Now assume FTOSC we have distinct $v,u$ both $f$-rare. Let $a,b$ be the smallest and largest elements of $X_v$; while $c,d$ to be that of $X_u$. Plugging $x=a$ in $[\diamondsuit]$ : $v=f(a +k\cdot (v-a)(v-b)) \implies a + k \cdot (v-a)(v-b) \in X_v$. Since $X_v$ is a finite set, we must have that $(v-a)(v-b)=0$. Similarly plugging $x=c$ implies $(u-a)(u-b)=0$. Hence from the last two equations, as $u\neq v$, we must have $\{u,v\}=\{a,b\}$. By symmetry, we get $\{u,v\}=\{c,d\}$, implying $\{a,b\}=\{c,d\}$. But clearly $X_u \cap X_v = \phi$, hence we get a contradiction! This proves that there is atmost one $f$-rare integer. For construction to part A, $f(0)=0$ and $f(x) = 2^{\nu_2(x) +1}$ works. Checking this is just some casework. Hence we are done
07.01.2024 16:21
27.04.2024 19:05
I had so much fun with this one, I think this problem fits perfectly in IMO 3/6, but unfortunately, didn't get selected. For part (a), just take $f(0) = 0$ and $f(n) = 2^{\nu_2(n) + 1}$, otherwise. One can check that above function satisfies the problem condition. (b) For the sake of contradiction, assume that $a, b$ are $f$-rare integers. Note that our condition implies that $f(f(x + yk) + y) = f(f(x) + y)$ for all $x, y, k \in \mathbb{Z}$. Call this assertion $P(x, y, k)$. Claim: We have $f(a) = a$ and $f(b) = b$. Proof. Let $M = \max(X_a), m = \min(X_a)$. $P(x, M-f(x), k)$ gives $a = f(M) = f(f(x) + M - f(x)) = f(f(x + (M - f(x))k) + M - f(x)) \implies f(x + (M - f(x))k) + M - f(x) \le M$, or equivalently, $f(x + (M - f(x))k) \le f(x)$ for all $x, k \in \mathbb{Z}$. Similarly, we get that $f(x) \le f(x + (m - f(x))k)$ for all $x, k \in \mathbb{Z}$. Now, note that $f(x + (M - f(x))(m - f(x))k) \le f(x)$ and $f(x) \le f(x + (M - f(x))(m - f(x))k)$, so $f(x) = f(x + (M - f(x))(m - f(x))k)$ for all $x, k \in \mathbb{Z}$. Thus taking $x = M$ into that, we get $a = f(M) = f(M + (M - a)(m - a)k)$, which means that $(M - a)(m - a)k \le 0$ for all $k$, implying $(m - a)(M - a) = 0$. Since $a = f(M) = f(m)$, we get that $f(a) = a$. Similarly, we get $f(b) = b$. $\blacksquare$ WLOG, assume $a > b$. We'll prove by induction that $f(na - (n-1)b) = a$. Induction base $n = 1$ is clear. Assume it's true on $n$ and let's prove on $n+1$. $P(b, n(a - b), 1)$ yields $a = f(na - (n-1)b) = f(b + n(a - b)) = f(f(b) + n(a - b)) = f(f(b + n(a - b)) + n(a - b)) = f(a + n(a - b)) = f((n+1)a - nb)$, completing the induction step. Thus, we get $f(na - (n-1)b) = a$ for all $n \ge 1$, contradicting the fact that $a$ is $f$-rare. Hence, we're done. $\blacksquare$
03.08.2024 18:51
Part a: The function \[f(x) = \begin{cases} 0 & x = 0\\ 2^{\nu_2(x)+1} & n \neq 0 \end{cases}\]satisfies the given properties and $0$ is $f$-rare. Part b: Let $P(x, y)$ denote the assertion that $f\left(f(x+y)+y\right)=f\left(f(x)+y\right)$. Repeatedly applying $P$ implies that \[f\left(f(x+ky)+y\right)=f\left(f(x)+y\right)\]for any integer $k$. Let $P_k(x, y)$ denote this assertion. Claim: If $u$ and $v$ are rare, then $f(u) = v$. Proof: Let $A = f^{-1}(v) = \{a_1, a_2, \dots, a_n\}$ where $a_1 \le a_2 \le \dots \le a_n$. Taking $P_k(u, a_1-f(u))$, we have \[v = f(a_1) = f(f(u+k(a_1-f(u))) + a_1 - f(u)).\]So, $f(u+k(a_1-f(u))) + a_1 - f(u) \in A$. So, \[f(u+k(a_1-f(u))) + a_1 - f(u) \ge a_1\]\[f(u+k(a_1-f(u))) \ge f(u).\]Similarly, $f(u+k(a_n-f(u))) \le f(u)$. So, \[f(u+k(a_1-f(u))(a_n-f(u))) = f(u).\]Therefore, $u+k(a_1-f(u))(a_n-f(u))$ covers finitely many values as $k$ varies. So, $(a_1-f(u))(a_n-f(u)) = 0$, so $f(u) \in \{a_1, a_n\}$. Therefore, $f(f(u)) = v$. So, if there is a rare number $v$, then $f(f(v))$ is equal to every rare number. So, there can only be one rare number.