wow,what a huge typo...

BaBaK Ghalebi wrote:

You're wrong

a) We have $ f(2n+1)-f(2n)=n$, so $ 2n\in E$ if $ n=0$ and $ 2n\in L$ if $ n>0$. Also, \[ f(4n+1)-f(4n+2) = 2n+2f(2n) - 2f(2n+1) = 2n + 2n +4f(n) - 4n -4f(n) = 0, \] so $ 4n+1\in E$. We can prove by induction that $ 4n+3\in G$: We have $ f(3)=1, f(4)=0$ and \[ f(4n+3)-f(4n+4) = 2n+1 + 2f(2n+1) - 4f(n+1) = 4n+1+4f(n)-4f(n+1). \] If $ n$ is even then $ f(n)-f(n+1) = n/2$, so $ f(4n+3)-f(4n+4)=2n+1>0$. If $ n\equiv 1 \pmod 4$ then $ f(n)=f(n+1)$, so $ f(4n+3)-f(4n+4)=4n+1>0$. If $ n\equiv 3 \pmod 4$ then $ f(n)>f(n+1)$, so $ f(4n+3)-f(4n+4)>0$. We thus have \[ E = \{4n+1: n\geq 0\}\cup \{0\}, \qquad L = \{2n: n\geq 1\} \qquad G = \{4n+3: n \geq 0\} \] b) We can prove by induction that $ a_k = f(2^k - 1) = 1-2^k+2^{k-1}k$: It is true for $ k=0,1$ and for $ k\geq 1$, we have $ a_k = \max\{f(n): 0\leq n\leq 2^k-1, n\equiv 1 \pmod 2\}$ since $ f(2n)<f(2n+1)$ and $ f(2^k)=0$. Thus, \begin{align*} a_{k+1} &= \max\{ f(2n+1): 0\leq n\leq 2^{k}-1\} \\ &= \max\{ n+2f(n): 0\leq n\leq 2^{k} -1 \} \\ &= 2^k-1 + 2a_k \\ &= 2^k - 1 + 2(1-2^k+2^{k-1}k) = 1-2^{k+1} + 2^k(k+1). \end{align*} $ \Box$

mathpk wrote: You're wrong I think you're also wrong. for example $f (1 ) = f ( 2 ) = 0$

Yimin Ge wrote: a) We have $ f(2n+1)-f(2n)=n$, so $ 2n\in E$ if $ n=0$ and $ 2n\in L$ if $ n>0$. Also, \[ f(4n+1)-f(4n+2) = 2n+2f(2n) - 2f(2n+1) = 2n + 2n +4f(n) - 4n -4f(n) = 0, \]so $ 4n+1\in E$. We can prove by induction that $ 4n+3\in G$: We have $ f(3)=1, f(4)=0$ and \[ f(4n+3)-f(4n+4) = 2n+1 + 2f(2n+1) - 4f(n+1) = 4n+1+4f(n)-4f(n+1). \]If $ n$ is even then $ f(n)-f(n+1) = n/2$, so $ f(4n+3)-f(4n+4)=2n+1>0$. If $ n\equiv 1 \pmod 4$ then $ f(n)=f(n+1)$, so $ f(4n+3)-f(4n+4)=4n+1>0$. If $ n\equiv 3 \pmod 4$ then $ f(n)>f(n+1)$, so $ f(4n+3)-f(4n+4)>0$. We thus have \[ E = \{4n+1: n\geq 0\}\cup \{0\}, \qquad L = \{2n: n\geq 1\} \qquad G = \{4n+3: n \geq 0\} \] b) We can prove by induction that $ a_k = f(2^k - 1) = 1-2^k+2^{k-1}k$: It is true for $ k=0,1$ and for $ k\geq 1$, we have $ a_k = \max\{f(n): 0\leq n\leq 2^k-1, n\equiv 1 \pmod 2\}$ since $ f(2n)<f(2n+1)$ and $ f(2^k)=0$. Thus, \begin{align*} a_{k+1} &= \max\{ f(2n+1): 0\leq n\leq 2^{k}-1\} \\ &= \max\{ n+2f(n): 0\leq n\leq 2^{k} -1 \} \\ &= 2^k-1 + 2a_k \\ &= 2^k - 1 + 2(1-2^k+2^{k-1}k) = 1-2^{k+1} + 2^k(k+1). \end{align*}$ \Box$ There is a typo — $$a_n =(n-3)2^{n-1} + 1 \text{ for } n \geq 5$$and the smaller values are $0,0,1,5,17$ respectively.

Very nice APMO problem from my birth year to me, it felt like the main idea here is about understanding the structure of $f$ and using a better interpretation of it (binary appending) to prove the results. although the solution is quite long, i felt like a lot of the steps are quite motivated and it was relatively painless to break down the problem into small claims Also, no posts for 3 years? The way to think of the function $f$ is, think of the input in binary. The value of $0$ and $1$ are both $0$. When a new digit is appended, if the appended bit is $0$, the value doubles, and if it is $1$, the value doubles and then is increased by the original input. We actually solve part (b) first, given this clearly the optimal strategy to maximize the value given a fixed number of bits is to append $1$ at every step, meaning that $f(2^k-1)$ is maximal. The answer for $k=0$ and $k=1$ is clearly $0$, focus on $k\geq 2$ from now on. We claim that $$f(2^k-1)=(k-2)\cdot 2^{k-1}+1$$for $k\geq 2$ This is true for $k=2$, and we will use induction. We have $$f(2^{k+1}-1)=2f(2^k-1)+2^k-1=(k-1)\cdot 2^k+1,$$completing the proof. Thus, the answer is $$(k-2)\cdot 2^{k-1}+1.$$ Now for part (a). It stays the same from 0 to 1. We claim that beyond this, -Going from $1\pmod{4}$ to $2\pmod{4}$ does not change the value, -going from $2\pmod{4}$ to $3\pmod{4}$ increases the value, -going from $3\pmod{4}$ to $0\pmod{4}$ decreases the value, -going from $0\pmod{4}$ to $1\pmod{4}$ increases the value. The second and fourth claims are clear since we are appending a $1$ instead of a $0$ at the end with everything else equal. To prove the first claim, we show that appending $01$ and appending $10$ to something has the same effect. Suppose we start with $f(n)=v$. If we append $0$ then $1$, then we have $f(2n)=2v$ and $f(4n+1)=4v+2n$. If we append $1$ then $0$, then we have $f(2n+1)=2v+n$ and $f(4n+2)=4v+2n$, as desired. Finally, we will show the third claim where going from 3 mod 4 to 0 mod 4 decreases the value. Suppose that the 3 mod 4 number in binary ends with $01\dots 1$ for some number (at least two) of 1s, and call this the "ending". When we go to $n+1$, it rolls over to $10\dots 0$. Note that this ending of $n$ starts with $01$, and the ending of $n+1$ starts with $10$, everything prior to the ending is equal for both $n$ and $n+1$. We have shown that the $01$ and $10$ has the same effect. However, $n$ will continue appending 1s, while $n+1$ can only append zeroes, hence shown as 3 mod 4 means there is at least one more $1$. Thus, the answer is: $L$ consists of $n\equiv 2\pmod{4}$ as well as $n\equiv 0\pmod{4},n\neq 0$. $E$ consists of $n=0$ and $n\equiv 1\pmod{4}$. $G$ consists of $n\equiv 3\pmod{4}$.