orl wrote: A function $ f$ defined on the positive integers (and taking positive integers values) is given by: $ \begin{matrix} f(1) = 1, f(3) = 3 \\ f(2 \cdot n) = f(n) \\ f(4 \cdot n + 1) = 2 \cdot f(2 \cdot n + 1) - f(n) \\ f(4 \cdot n + 3) = 3 \cdot f(2 \cdot n + 1) - 2 \cdot f(n), \end{matrix}$ for all positive integers $ n.$ Determine with proof the number of positive integers $ \leq 1988$ for which $ f(n) = n.$ Considering that $ f(n)=f(2n)$, the two last equations give : $ f(4n + 1)-f(4n) = 2(f(2n + 1) - f(2n))$ $ f(4n + 3)-f(4n+2)= 2(f(2n + 1) - f(2n))$ And so, if $ n$ is even and $ 2^{p+1}>n\geq 2^p>1$, we have $ f(n+1)-f(n)=2^p$ So, if we have an even $ n=\sum_{i=1}^{k} 2^{a_i}$, where $ \{a_i\}$ is a strictly increasing sequence with $ a_1>0$ ($ n$ even) : $ f(n+1)=2^{a_k}+f(n)$ Then $ f(n)=f(\sum_{i=1}^{k} 2^{a_i})$ $ =f(\sum_{i=1}^{k} 2^{a_i-a_1})$ $ =2^{a_k-a_1}+f(\sum_{i=2}^{k} 2^{a_i-a_1})$ And so $ f((\sum_{i=1}^{k} 2^{a_i})+1)=2^{a_k}+2^{a_k-a_1}+f(\sum_{i=2}^{k} 2^{a_i-a_1})$ And it is easy to conclude that $ f(\sum_{i=1}^{k} 2^{a_i})=\sum_{i=1}^{k} 2^{a_k-a_i}$ and that applying $ f(n)$ means reversing the order of binary representation of n (and this could be also easily shown with induction). So $ f(n)=n$ occurs if and only if the binary representation of n is symetrical. It remains to count these "symetric" numbers. We have exactly $ 2^{\lceil\frac{m-1}{2}\rceil}$ such numbers in $ [2^m,2^{m+1})$. So : We have exactly 1 such numbers in $ [1,2)$ We have exactly 1 such numbers in $ [2,4)$ We have exactly 2 such numbers in $ [4,8)$ We have exactly 2 such numbers in $ [8,16)$ We have exactly 4 such numbers in $ [16,32)$ We have exactly 4 such numbers in $ [32,64)$ We have exactly 8 such numbers in $ [64,128)$ We have exactly 8 such numbers in $ [128,256)$ We have exactly 16 such numbers in $ [256,512)$ We have exactly 16 such numbers in $ [512,1024)$ Since $ 1988=B11111000100$, positions 2 to 6 may be any between $ 00000$ and $ 11101$, and so : We have exactly 30 such numbers in $ [1024,1988]$ And so the requested number is $ 1+1+2+2+4+4+8+8+16+16+30=92$

my solution:

Attachments:
imo.pdf (100kb)

Solution from Twitch Solves ISL: The main claim is following. Claim: $f(n)$ is equal to the result when $n$ is written in binary and its digits are reversed. Proof. Follows directly by induction. $\blacksquare$ So the question asks for the number of binary palindromes which are at most $1988 = 11111000100_2$. For $k = 1, 2, \dots, 10$ there are $2^{\left\lceil k/2 \right\rceil-1}$ binary palindromes with $k$ bits (note the first bit must be $1$). For $k=11$, the number of binary palindromes which are also less than $1988$ is $2^5 - 2$ (only $11111011111$ and $11111111111$ are missing). Hence the final count is \[ 2^0+2^0 + 2^1+2^1 + 2^2+2^2 + 2^3+2^3 + 2^4+2^4 + (2^5-2) = 92. \]

Another great function. We claim that $f(x)$ is the reversal of the digits of $x$ in binary. We proceed by induction, because given $f(1)=f(2)=1$ and $f(3)=3$, we can determine all other values, and this property holds for $f(1)$, $f(2)$, and $f(3)$. We prove that all operations conserve this property. For $f(2n)=f(n)$, we are adding a zero at the end, thus obviously preserving this property. For $f(4n+1) = 2f(2n+1)-f(n)$, we see that letting $4n+1=\overline{a_1a_2\ldots a_k01}_2$ gets that assuming this holds true for $f(2n+1)$ and $f(n)$, then $$f(4n+1) = 2f(2n+1)-f(n)=2f(\overline{a_1a_2\ldots a_k1}_2)-f(\overline{a_1a_2\ldots a_k}_2) $$$$= 2 \cdot\overline{1a_ka_{k-1}\ldots a_2a_1}_2 - \overline{a_ka_{k-1}\ldots a_2a_1}_2 = \overline{10a_ka_{k-1}\ldots a_2a_1}_2$$which keeps the property since $\overline{10a_ka_{k-1}\ldots a_2a_1}_2$ is the reversal of $\overline{a_1a_2\ldots a_k01}_2$ in binary. Similarly, letting $4n+1=\overline{a_1a_2\ldots a_k11}_2$, then $$f(4n+3) = 3f(2n+1)-2f(n)=3f(\overline{a_1a_2\ldots a_k1}_2)-2f(\overline{a_1a_2\ldots a_k}_2) $$$$= 3 \cdot\overline{1a_ka_{k-1}\ldots a_2a_1}_2 - 2 \cdot \overline{a_ka_{k-1}\ldots a_2a_1}_2 = \overline{11a_ka_{k-1}\ldots a_2a_1}_2$$which keeps the property since $\overline{11a_ka_{k-1}\ldots a_2a_1}_2$ is the reversal of $\overline{a_1a_2\ldots a_k11}_2$. Due to this, we have proved that this property holds for all $n$ which means we need to find the number of binary palindromes below $1988$. This number is just going to be, for $n<11$-digit numbers, $2^{\lfloor \frac {n-1}2 \rfloor}$ ways, so summing up for less than $11$ digits gets $62$ ways. For $11$-digit numbers, we have $32$ ways but need to subtract a few in which are greater than $1988$; there are two numbers we don't count, namely $2015$ and $2047$. As a result, our answer is $62+30=\boxed{92}$.

We claim that the answer is the number of binary palindromes $\leq 1988$. Define $g(n)$ to be the result when $n$ is written in binary, and then evaluated in reverse order. We use induction to show that $f(n)=g(n)$. The base cases are $g(1)=1=f(1),g(3)=3=f(3)$. Now, we claim some properties on $g(n)$. Note that $g(2n)=g(n)$ and $g(2n+1)=2^{\lfloor \log_2 n \rfloor +1}+g(n)$. These are clearly true by the definition of $g(n)$. We also have that $g(4n+1)$ ends up putting a $\overline{10}$ out in front, so \[g(4n+1) = 2\cdot 2^{\lfloor \log_2 n \rfloor +1}+g(n) =2g(2n+1) - g(n)\]and $g(4n+3)$ puts a $\overline{11}$ out front, so \[g(4n+3) = 2\cdot 2^{\lfloor \log_2 n \rfloor +1}+2^{\lfloor \log_2 n \rfloor +1}+g(n) =3g(2n+1) - 2g(n)\]Thus, we have that all definitions of $f(n)$ are satisfied by $g(n)$, and since these conditions uniquely define $f(n)$, we have that $f(n)=g(n)$ for all $n$ and we're done. Now, to finish, simply note that $g(n)=f(n)=n$ only for those $n$ which are binary palindromes. $\square$. Apparently, we're supposed to actually compute a numeric answer. Note that \[1988_{10} = 497 \cdot 00_2 = 248 \cdot 100_2 = 31 \cdot 000100_2 = 11111000100_2\]Now, the number of 11 digit palindromes is $(2^4-1)\cdot 2 = 30$ . For smaller palindromes, there will be: \[1+1+2+2+4+4+8+8+16+16= 62\]Thus, the total is $62+30=92$ and we're done. $\blacksquare$.

Not as hard as it's difficulty partner IMO 1988 p6. But it's pretty cool, nevertheless.

Easy to prove by induction that $f(n)$ reverses the order of the binary representation of $n.$ So we have to calculate the number of palindromes $\geq 1988.$ There are $2^{\lceil \frac{x-1}{2} \rceil}$ binary palindromes $\in [2^x,2^{x+1}).$ Noting that $1988=11111000100_2$ has $11$ digits, only $11111011111_2$ and $11111111111_2$ are $11$ digit binary palindromes greater than $1988,$ so the sum is $\boxed{1 + 1 + 2 + 2 + 4 + 4 + 8 + 8 + 16 + 16+ 62 -2=92}.$

Beautiful. We claim that the answer is $92$. Note that there is only one possible function that exists. Let $g$ be the function that reverses the binary string of a number, excluding trailing zeroes. We claim that $f = g$. Because there is only one possible function, it suffices to prove that all the properties of $f$ match the properties of $g$. The first three conditions are trivial. Denote as $g(n) =a$ for some $n$, which has length $k$ in binary. Then, $2n+1 = \overline{n1}$, which means, $g(2n+1) = \overline{1n} = 2^{k+1}+a$. Also, $4n+1 = \overline{n01}$, which means, $g(4n+1) = \overline{10n} = 2^{k+2}+a$. Finally, $4n+3 = \overline{n11}$, which means, $g(4n+3) = \overline{11n} = 2^{k+2}+2^{k+1}+a$. Thus, \[g(4n+1) = 2^{k+2}+a = 2\cdot(2^{k+1}+a)-a = 2g(2n+1)-g(n)\]and \[g(4n+3) = 2^{k+2}+2^{k+1}+a = (2+1)\cdot(2^{k+1}+a)-2a = 3g(2n+1)-2g(n)\]which proves that $f = g$. The only possible way for $f(x) =x$, is if the number is palindromic when written in binary form. Note, $1988 = 11111011100_{2}$, which has length $11$. Note that there are only $2$ palindrome of length $11$ that are $> 1988$, namely $11111011111_{2}$ and $11111111111_{2}$. It suffices to find all palindromes of length $1 \rightarrow 11$. For odd, we have $2^5+2^4+2^3+2^2+2^1+2^0 = 63$, and for even, we have $2^4+2^3+2^2+2^1+2^0 = 31$, which gives us $63+31-2 = \boxed{92}$.

remarks

this could be a final 5 aime problem today sketch bc im tired Surprisingly, $f(x)$ has the following characterization: Claim: Express $x$ in base $2$ - then $f(x)$ is the value of the flipped binary string. (For example, $f(22) = f(10110_2) = 01101_2 = 13$). Proof. Induct - the details are easy enough that I won't write them up here (see other solutions for a complete proof). Now our final answer correlates to the number of binary palindromes that are at most $1988$, which has $11$ digits in binary - for $n$ digits in binary with $0 \le n \le 11$ there are $2^{\left\lfloor\frac{n}{2}\right\rfloor}$ palindromes, but we exclude $11111011111$ and $1111111111$ for a total answer of $\boxed{92}$.

We claim that in binary, $f(n)$ is the reverse of $n.$ We prove this by strong induction. The base cases $n=1,2,3$ are trivial. If $n$ is even then it is also trivial. Now suppose $n=4k+1.$ Denote by $[x]$ the binary expansion of $x,$ and denote by $[[x]]$ the reverse of $[x].$ Notice that $\overline{[2k+1]}=\overline{[k]1},$ so we have $f(n)=f(4k+1)=2f(2k+1)-f(k)=\overline{1[[k]]0}-\overline{[[k]]}=\overline{10[[k]]},$ which is $\overline{[k]01}$ backwards, and $\overline{[k]01}$ is $4k+1=n.$ Now suppose $n=4k+3.$ We have $f(n)=f(4k+3)=3f(2k+1)-2f(k)=\overline{1[[k]]0}+\overline{1[[k]]}-\overline{[[k]]0}=\overline{11[[k]]},$ which is $\overline{[k]11}$ backwards, and $\overline{[k]11}$ is $4k+3=n.$ To finish, notice that $f(n)=n$ iff $n$ is a palindrome in binary, and $1988$ is $11111000100$ in binary, so the largest palindrome with an odd number of digits smaller than it is $11110101111,$ which is the $111101_2=61$st, and $1111111111$ is the largest palindrome with an even number of digits smaller than it, and this is the $11111_2=31$st, so there are a total of $31+61=\boxed{92}.$

We can see that the relation obviously defines all integers. Thus, if we find something that works for all integers then it must be the actual function. We claim that $f(x)$ is equal to the binary reflection of $x$. For example since $13 = 1101_2$ then $f(13) = 1011_2 = 11$ (note that we discount leading $0$'s. We can see that this satisfies the first three conditions. Let $f(n) = x$ and $y$ be the amount of digits of $n$ in base $2$. Then we can see that our fourth condition can be represented as \[2^{x+2} + y = 2y-2 \cdot 2^{x+1} -y\]which is obviously true. The fifth condition is \[3 \cdot 2^{x+1} +y = 3\cdot 2^{x+1} + 3y - 2y\] Finishing by casework on the number of digits we can see that the answer is $32+16+16+8+8+4+4+2+2+1+1-2 = 92$

I'm looking back on this problem now, can someone please explain the motivation for using binary in this problem? Thanks!

After bashing out 50 values, we claim that $f(n)$ is the value of the reverse binary string of $n$, which we show using induction. Our second line for even $n$ is clear. For the third line, we have \begin{align*} f(4x+1) &= f\left(2^n + \sum_{k=2}^{n-1} a_k2^k + 1\right) \\ &= 2\left(2^{n-1} + \sum_{k=2}^{n-1} a_k2^{n-k} + 1\right) - \left(\sum_{k=2}^{n-1} a_k2^{n-k} + 1\right) \\ &= 2^n + \sum_{k=2}^{n-1} a_k2^{n-k} + 1. \end{align*} Our third line is proven with \begin{align*} f(4x+3) &= f\left(2^n + \sum_{k=2}^{n-1} a_k2^k + 3\right) \\ &= 3\left(2^{n-1} + \sum_{k=2}^{n-1} a_k2^{n-k} + 1\right) - 2\left(\sum_{k=2}^{n-1} a_k2^{n-k} + 1\right) \\ &= 2^n + 2^{n-1} + \sum_{k=2}^{n-1} a_k2^{n-k} + 1. \quad \blacksquare \end{align*}