1988 IMO Problems/Problem 3
Problem
A function defined on the positive integers (and taking positive integers values) is given by:
for all positive integers Determine with proof the number of positive integers for which
Solution 1
Considering that , the two last equations give :
And so, if is even and , we have
So, if we have an even , where is a strictly increasing sequence with ( even) : Then And so
And it is easy to conclude that and that applying means reversing the order of binary representation of n (and this could be also easily shown with induction).
So occurs if and only if the binary representation of n is symetrical.
It remains to count these "symetric" numbers. We have exactly such numbers in . So : We have exactly 1 such numbers in We have exactly 1 such numbers in We have exactly 2 such numbers in We have exactly 2 such numbers in We have exactly 4 such numbers in We have exactly 4 such numbers in We have exactly 8 such numbers in We have exactly 8 such numbers in We have exactly 16 such numbers in We have exactly 16 such numbers in
Since , positions 2 to 6 may be any between and , and so : We have exactly 30 such numbers in
And so the requested number is
This solution was posted and copyrighted by pco. The original thread for this problem can be found here: [1]
Solution 2
The main claim is following.
Claim: is equal to the result when is written in binary and its digits are reversed. Proof. Follows directly by induction.
So the question asks for the number of binary palindromes which are at most . For there are binary palindromes with bits (note the first bit must be ). For , the number of binary palindromes which are also less than is (only and are missing). Hence the final count is
This solution was posted and copyrighted by v_Enhance. The original thread for this problem can be found here: [2]
Solution 3
We claim that is the reversal of the digits of in binary. We proceed by induction, because given and , we can determine all other values, and this property holds for , , and .
We prove that all operations conserve this property. For , we are adding a zero at the end, thus obviously preserving this property. For , we see that letting gets that assuming this holds true for and , thenwhich keeps the property since is the reversal of in binary. Similarly, letting , thenwhich keeps the property since is the reversal of . Due to this, we have proved that this property holds for all which means we need to find the number of binary palindromes below . This number is just going to be, for -digit numbers, ways, so summing up for less than digits gets ways. For -digit numbers, we have ways but need to subtract a few in which are greater than ; there are two numbers we don't count, namely and . As a result, our answer is .
This solution was posted and copyrighted by kevinmathz. The original thread for this problem can be found here: [3]
See Also
1988 IMO (Problems) • Resources | ||
Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
All IMO Problems and Solutions |