It seems we should be able to finish from this, but I was not able to do so after a lot of trying. Looking at completed solutions gives reasons to suspect it is actually very difficult to complete from here (as in, you may as well do something else). Very disappointing.

I've found a solution, but it's really messy. I had to prove about 8 conjectures by collective strong induction. Is there a better intended solution?

That's what the official solution pretty much is, and I have yet to see anything better. Not sure what this problem was doing on the shortlist.

MellowMelon wrote: Not sure what this problem was doing on the shortlist. It's probably there because it probably was one of the seven best original algebra problems in the long list. As for a solution, the best that I can find is using induction to find $ f(2^n - a)$ for all $ n$ and $ a = 1,2,3$ (you get a different -simple- expression whether $ n$ is even or odd), then find a bound for $ |f(m)|$, unless I am mistaken you get

and then write for any $ 2^n\leq r < 2^{n + 1}$

An ugly approach(very sorry if repeated): Use induction to show: Case 1:if $ -1\le x \le 2^{2m}-1$ then the maximal value is $ f(2^{2m}-1)$ the minimal value is $ f(2^{2m}-2)$ Case 2:if $ -1\le x \le 2^{2m+1}$ then the maximal value is $ f(2^{2m+1}-2)$ the minimal value is $ f(2^{2m+1}-1)$ Then it is easy to show $ f(x)\le 0$ when $ x$ is not a multiple of $ 3$ and $ f(3p)\ge 0,p\ge 0$ Very sorry for not being completed,the induction is not difficult but rather complicated

MellowMelon wrote:

It seems we should be able to finish from this, but I was not able to do so after a lot of trying. Looking at completed solutions gives reasons to suspect it is actually very difficult to complete from here (as in, you may as well do something else). Very disappointing. I have a solution based on that, not sure if it works. The last inequality is probably off a little but I think it can be easily fixed using what I proved.

Claim: \begin{align*} f(2^{2k+1} - 3) = 0 ~,~ f(2^{2k+1} - 2) &= 3^k ~,~ f(2^{2k+1} - 1) = -3^k \\ f(2^{2k+2} - 3) = -3^k ~,~ f(2^{2k+2} - 2) &= -3^k ~,~ f(2^{2k+2} - 1) = 2 \cdot 3^k \end{align*} Proof: Observe that \begin{align*} f(2^{2k+1} - 3) &= f(2^{2k} -2) - f(2^{2k} - 3) \\ f(2^{2k+1} - 2) &= f(2^{2k} - 1) - f(2^{2k} - 2) \\ f(2^{2k+1} - 1) &= f(2^{2k} - 3) - f(2^{2k} - 1) \\ f(2^{2k+2} - 3) &= f(2^{2k + 1} - 1) - f(2^{2k+1} - 3) \\ f(2^{2k+2} - 2) &= f(2^{2k+1} - 3) - f(2^{2k+1} - 2) \\ f(2^{2k+2} - 1) &= f(2^{2k+1} - 2) - f(2^{2k + 1} - 1) \end{align*}So our claim follows by induction. $\square$ Now for any $1 \le i \le 3$ and $k \in \mathbb Z_{\ge 0}$, let set \begin{align*} S(i,k) := \{f(n) : 3 \mid n-i \text{ and } \lfloor \log_2 n \rfloor = k \} \\ T(i,k) := \{f(n) : 3 \mid n-i \text{ and } 0 \le \lfloor \log_2 n \rfloor \le k \} \end{align*}By notation $a \le \bullet \le b$, we will mean all elements of set $\bullet$ lie in $[a,b]$. Claim: \begin{align*} -3^k \le S(1,2k+1) \le 0 ~,~ -3^k \le S(2,2k+1) \le 0 ~,~ 0 \le S(3,2k+1) \le 2 \cdot 3^k \\ -3^{k+1} \le S(1,2k+2) \le 0 ~,~ -3^k \le S(2,2k+2) \le 0 ~,~ 0 \le S(3,2k+2) \le 3^{k+1} \end{align*} Proof: Observe that \begin{align*} f(x) = f(\underbrace{2^{2k+2} -1}_{=2 \cdot 3^k}) - f(\underbrace{x - 2^{2k+2}}_{\in T(2,2k+1)}) ~ \forall ~ x \in S(3,2k+2) \\ f(x) = f(\underbrace{2^{2k+1} - 2}_{=3^k}) - f(\underbrace{x - 2^{2k+1}}_{\in T(1,2k)} ) ~ \forall ~ x \in S(3,2k+1) \\ f(x) = f(\underbrace{2^{2k+1} - 3}_{=0}) - f(\underbrace{x - 2^{2k+1}}_{\in T(3,2k)}) ~ \forall ~ x \in S(2,2k+1) \\ f(x) = f(\underbrace{2^{2k+2} - 3}_{= - 3^k}) - f(\underbrace{x-2^{2k+2}}_{\in T(3,2k+1)}) ~ \forall ~ x \in S(1,2k+2) \\ f(x) = f(\underbrace{2^{2k+2} - 2}_{= -3^k}) - f(\underbrace{x - 2^{2k+2}}_{\in T(1,2k+1)}) ~ \forall ~ x \in S(2,2k+2) \\ f(x) = f(\underbrace{2^{2k+1} - 1}_{= -3^k}) - f(\underbrace{x - 2^{2k+1}}_{\in T(2,2k) }) ~ \forall ~ x \in S(1,2k+1) \end{align*}Now our Claim just follows by induction. $\square$ This completes the proof of the problem. $\blacksquare$

Solved with squareman, megarnie, vsamc, pi271828, notsarcastic69, fuzimiao2013. Omitted some trivial computational details which take a long time to type. First, list out $f(n)$ in $-1 \le n \le 8$, and check that they satisfy the given requirement. This takes care of edge cases. Claim: For all $m \ge 2$, it holds that $f(3m) \ge 2$, $f(3m+1) \le -1$, and $f(3m+2) \le -1$. Proof: Proceed by triple induction, assuming that for $6 \le n \le 2^{2k-1} + 2$, $f(n)$ satisfies the above requirements depending on its modulo 3. The reason we use $2k-1$ instead of $k$ is because then, its modulo 3 is fixed. We will prove that it holds up to $2^{2k+1}+2$ as well. Define $g(n) = f(n+3) - f(n)$. We can easily deduce that $$\left(g(2^{2k-1}), g(2^{2k-1} + 3), g(2^{2k-1}+6), \cdots g(2^{2k}-5), g(2^{2k}-2) \right)= \left( -g(0), -g(3), -g(6), \cdots -g(2^{2k-1}-2), +1 \right)$$$$\left(g(2^{2k-1}+1), g(2^{2k-1} + 4), g(2^{2k-1}+7), \cdots g(2^{2k}-4), g(2^{2k}-1) \right)= \left( -g(1), -g(4), -g(7), \cdots -g(2^{2k-1}-4), +1 \right)$$$$\left(g(2^{2k-1}+2), g(2^{2k-1} + 5), g(2^{2k-1}+8), \cdots g(2^{2k}-6), g(2^{2k}-3) \right)= \left( -g(2), -g(5), -g(8), \cdots -g(2^{2k-1}-6), -1 \right).$$ Specifically, the three sequences are 2, 0, 1 modulo 3 respectively. Using the fact that sums of $g$'s telescope, and the values of $f(0), f(1), f(2)$, we can easily verify that the claimed inequalities hold up to $2^{2k}+2$. Then, we apply the process again (although slightly different because modulo 3's change, but the idea is the same). $$\left(g(2^{2k}+1), g(2^{2k} + 4), g(2^{2k}+7), \cdots g(2^{2k+1}-6), g(2^{2k+1}-3) \right)= \left( -g(1), -g(4), -g(7), \cdots -g(2^{2k}-6), -1 \right)$$$$\left(g(2^{2k}+2), g(2^{2k} + 5), g(2^{2k}+8), \cdots g(2^{2k+1}-5), g(2^{2k+1}-2) \right)= \left( -g(2), -g(5), -g(8), \cdots -g(2^{2k}-5), +1 \right)$$$$\left(g(2^{2k}), g(2^{2k} + 3), g(2^{2k}+6), \cdots g(2^{2k+1}-4), g(2^{2k+1}-1) \right)= \left( -g(0), -g(3), -g(6), \cdots -g(2^{2k}-4), +1 \right).$$ Using telescoping, we can once again easily show that the inequalities hold for each of 2, 0, 1 modulo 3, completing the inductive step. Specifically, we have that $ f(3p)\ge 0$ for all all integers $ p\ge 0$.$\blacksquare$ (I might've messed up indexing of the modulos a bit but thats the main idea)

MellowMelon wrote: That's what the official solution pretty much is, and I have yet to see anything better. Not sure what this problem was doing on the shortlist. To add, why is it not NT? A very lame problem.

Brutal problem. Here is a proof written backwards with motivation (to write it forwards, just reverse the paragraphs): $$3p=2^a+2^b+c\text{ }\forall a>b \text{ and } 2^b>c\ge 0\implies f(3p)=f(2^a+2^b+c)=f(2^a-t(2^b+c))-f(2^b-t(c))+f(c).$$So based off of this, we want to find an upper bound for f(divisible by 3 term) (since $2^n+m\equiv 2^n-t(m)\equiv 2^n+m\pmod 3$), an upper bound for f(some term not divisible by 3), and an upper bound for general $c<2^b$. Let's compute the general values of the LHS of original statement, taking m in {1,2,3}. (since it's similar to t(m) and then we can use inductive hypothesis more). We will prove that $f(2^{2k+1}-\{1,2,3\})=\{-3^k,0,3^k\}$ and $f(2^{2k+2}-\{1,2,3\})=\{3^k2,-3^k,-3^k\}$. Check the base cases manually (I don't wanna type them rn). Now assume these statements are true for all values $l<m$. Inductive step: $$f(2^{2k+1})=f(2^{2k}+(2^{2k}-1)=f(2^{2k}-3)-f(2^{2k}-1)=-3^{k-1}-3^{k-1}2=-3^k.$$Similarly we can derive the other ones, which I'll omit here. Then the key takeaways are $$|f(2^n-t(m)|\le \dfrac23 3^{n/2},\text{ }f(2^n-t(m))\ge 3^{(n-1)/2}\text{ }\forall 2^n+m\equiv 0\pmod 3, \text{ and } f(2^n-t(m)\le 0\forall 2^n+m\ne 0\pmod 3.$$These are our upper bounds for divisible and not divisible by 3 inputs for f. $\square$ Next, we prove by induction that $f(m)\le 3^{n/2}\text{ }\forall 2^n>m,n\ge 0$. Base case clear as f(0)=1, and inductive step says if $m<2^n$ we're done, $$m=2^n+q\text{ }\forall 2^n>q\ge 0\implies |f(m)|=|f(2^n-t(q))-f(q)|\le |f(2^n-t(q)+|f(q)|\le \dfrac23 3^{n/2}+3^{n/2}<3^{(n+1)/2},$$as claimed. $\square$ Putting it all together, $f(c)\ge -3^{b/2}$, $f(2^a-t(2^b+c)\ge 3^{(a-1)/2}$, $f(2^b-t(c))\le 0$ $$\implies f(3p)\ge 3^{(a-1)/2}-3^{b/2}\ge 0\text{ }\forall a>b,$$as desired. $\blacksquare$

First, let us find $f(x)$ for all $x$ of the form $2^n-1$, $2^n-2$, and $2^n-3$ for all integers $n\ge 1$. We already have the values for $n=1$, which are $f(1)=-1$, $f(0)=1$, and $f(-1)=0$. Suppose $n$ is even then \begin{align*} f(2^n-1)&=f(2^{n-1}+2^{n-1}-1)=f(2^{n-1}-t(2^{n-1}-1))-f(2^{n-1}-1)=f(2^{n-1}-2)-f(2^{n-1}-1)\\ f(2^n-2)&=f(2^{n-1}+2^{n-1}-2)=f(2^{n-1}-t(2^{n-1}-2))-f(2^{n-1}-2)=f(2^{n-1}-3)-f(2^{n-1}-2)\\ f(2^n-3)&=f(2^{n-1}+2^{n-1}-3)=f(2^{n-1}-t(2^{n-1}-3))-f(2^{n-1}-3)=f(2^{n-1}-1)-f(2^{n-1}-3) \end{align*}If $n$ is odd then \begin{align*} f(2^n-1)&=f(2^{n-1}+2^{n-1}-1)=f(2^{n-1}-t(2^{n-1}-1))-f(2^{n-1}-1)=f(2^{n-1}-3)-f(2^{n-1}-1)\\ f(2^n-2)&=f(2^{n-1}+2^{n-1}-2)=f(2^{n-1}-t(2^{n-1}-2))-f(2^{n-1}-2)=f(2^{n-1}-1)-f(2^{n-1}-2)\\ f(2^n-3)&=f(2^{n-1}+2^{n-1}-3)=f(2^{n-1}-t(2^{n-1}-3))-f(2^{n-1}-3)=f(2^{n-1}-2)-f(2^{n-1}-3) \end{align*}Inductively, it can be seen that \begin{align*} f(2^{2k}-1) &=2\cdot 3^{k-1}\\ f(2^{2k}-2) &=-3^{k-1}\\ f(2^{2k}-3) &=-3^{k-1}\\ f(2^{2k+1}-1) &=-3^{k}\\ f(2^{2k+1}-2) &=3^{k}\\ f(2^{2k+1}-3) &=0\\ \end{align*}Suppose $x$ is divisible by $3$ then let $x=2^a+2^b+c$ for non-negative integers $a$, $b$, $c$ where $2^a>2^b>c$. Note that \[f(x)=f(2^a-t(2^b+c))-f(2^b+c)=f(2^a-t(2^b+c))-f(2^b-t(c))+ f(c)\]Note that $2^a-t(2^b+c)$ is a multiple of three. As a result, since $2^a$ is not a multiple of three, neither is $2^b+c$. Therefore, $2^b-t(c)$ is not a multiple of three. We can see from our table of values above that if $2^b-t(c)$ is not a multiple of three then $f(2^b-t(c))\le 0$. Thus, it suffices to show that $f(2^a-t(2^b+c))\ge |f(c)|$. We can again consult our table of values above to see that $f(2^a-t(2^b+c))\ge 3^{\left\lfloor \frac{k}{2}\right\rfloor}$ since $2^a-t(2^b+c)$ is a multiple of three. Finally we can use induction to bound $f(c)$ and we're done.