What is the explanation of the solution of problem 3 from IMO 1988?
Oh, that’s a fun one.
I believe this problem can be solved quite easily given enough time (not all IMO problems can.) It’s much harder to do under time pressure, which is why it’s a P3; you’d need amazing insight or a lot of luck to figure it out quickly. But figuring it out slowly is actually not that difficult.
We have a function f, defined for every positive integer n like this:
\displaystyle f(1)=1, f(3)=3
\displaystyle f(2n)=f(n)
\displaystyle f(4n+1)=2f(2n+1)-f(n)
\displaystyle f(4n+3)=3f(2n+1)-2f(n)
The first thing to observe is that this really does define a function for all positive integers n, with no ambiguity or unknown values.
We are asked to find how many fixed points f has through 1988, meaning how many numbers n between 1 and 1988 satisfy f(n)=n. As always, this 1988 is clearly just a red herring. We need to generally understand the fixed points, which likely means we need to understand what this function does in general.
Staring at the recursive definition doesn’t necessarily make anything stand out, so we simply do the most natural thing: calculate some values of f. I always prefer to write a\to b instead of f(a)=b: it’s clearer, and the name f is useless when there’s only one function around.
So, we quickly compute:
1 \to 1
2 \to 1
3 \to 3
4 \to 1
5 \to 5
6 \to 3
7 \to 7
8 \to 1
9 \to 9
10 \to 5
Danger lurks at this point: having made 10 experiments you may think you’ve sampled enough, and you may conclude that f(n)=n holds for all odd n. If you stop now and try to prove this, though, you will quickly run into trouble. Let’s keep going.
11 \to 13 (oh!)
12 \to 3
13 \to 11
14 \to 7
15 \to 15
16 \to 1
17 \to 17
18 \to 9
19 \to 25
20 \to 5
At this second milestone of 20 numbers computed, another danger lurks: the most reasonable theory at this point is that f(n)=n occurs exactly around powers of 2, that is when n=2^k \pm 1. Right? This perfectly explains why 11, 13 and 19 are out while all other small oddies are in.
Do not succumb to temptation. Persevere. Do one more. Just one more.
21 \to 21
Aha! There goes that theory out the window.
So, what’s going on here?
The fixed points we have so far are 1,3,5,7,9,15,17 and 21. It’s not too clear what these numbers are. The even numbers clearly can’t be fixed points, but the way they map is relevant to how the odd numbers behave. What’s the order in this chaos?
The inspired observation you need is to stop looking at these numbers in base 10. Looking at the rules defining f, and how calculating it involves doubling and quadrupling, it may seem natural to look at all of these values in binary.
1\to 1
10\to 1
11\to 11
100 \to 1
Actually, let’s just look at the more interesting ones.
1011 \to 1101 (that’s 11\to 13)
1101 \to 1011 (that’s 13\to 11)
10011 \to 11001 (that’s 19 \to 25)
Do you see it now?
Yes! The function simply reverses the binary digits of its input. That’s why 19 goes to 25, and we can easily confirm that 25 indeed goes back to 19. That’s also why 21, which is 10101 in binary, is a fixed point.
Noticing this simple description of the function f is the only really hard part of this problem. Gathering the data for this observation is purely mechanical, and proving it – which we shall now proceed to do – is pretty straightforward, too. Realizing it takes experience and observation, but we get many clues.
To prove that f really reverses in binary, we can just do this: declare g to be the function that actually reverses the binary digits, and show that g satisfies the same conditions that f does. Since these conditions determine f uniquely, it must be that f=g.
So if g is, by definition, the bit-reversal function, then obviously g(1)=1 and g(3)=3. It’s also clear that g(2n)=g(n): the binary representation of 2n is the same as that of n, with a single 0 attached to the end. Reversing 2n places that 0 at the beginning, which represents the same number as the reversal of n.
Now for the last two relations. Take any natural number n represented in binary. Attach 01at the end; this is now 4n+1. Reverse; you get g(4n+1)=2^k+g(n), where the term 2^k comes from moving the rightmost 1 to the very left, and we don’t bother to calculate k: we won’t need to.
Indeed, g(2n+1)=2^{k-1}+g(n), where the added power of 2 is clearly one less than k. So,
2g(2n+1)=2^k+2g(n)=g(4n+1)+g(n)
which is exactly the defining relation of f(4n+1).
Finally, 4n+3 is represented by the binary representation of n with 11 appended in the end, so
g(4n+3)=2^k+2^{k-1}+g(n)
while
3g(2n+1)=3(2^{k-1}+g(n))=(2+1)2^{k-1}+3g(n)
or
3g(2n+1)=2^k+2^{k-1}+3g(n)=g(4n+3)+2g(n)
which confirms the last relation.
This concludes the verification that g(n), the “binary reversal” function, satisfies the same recursive relations as f, so the two functions are one and the same.
The only thing left to do is count how many palindromic numbers exist between 1 and 1988. The number of such nonzero numbers with d binary digits is:
- 2^{e-1} if d=2e is even (you must start with 1, and then freely choose e-1 digits)
- 2^e if d=2e+1 is odd (start with 1, choose e-1 digits, and choose the middle digit).
This gives 1+1+2+2+4+4+8+8+16+16 palindromes of up to 10 bits. With 11 bits we should have had 32 palindromes, but two of them start with five 1’s and are therefore larger than 1988 (notice that 1988 is very close to 2^{11}=2048). So we only get 30 palindromic numbers of 11 bits which do not exceed 1988, and so the final answer is 92.