Difference between revisions of "1988 IMO Problems/Problem 3"
Mrmustache (talk | contribs) m |
|||
(One intermediate revision by one other user not shown) | |||
Line 1: | Line 1: | ||
− | A function <math>f</math> | + | ==Problem== |
− | <math> f(1) = 1, f(3) = 3, f ( | + | A function <math> f</math> defined on the positive integers (and taking positive integers values) is given by: |
− | <math> f(4n+1) = | + | |
− | for | + | <math> \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}</math> | ||
+ | |||
+ | for all positive integers <math> n.</math> Determine with proof the number of positive integers <math> \leq 1988</math> for which <math> f(n) = n.</math> | ||
+ | |||
+ | ==Solution 1== | ||
+ | Considering that <math> f(n)=f(2n)</math>, the two last equations give : | ||
+ | <math> f(4n + 1)-f(4n) = 2(f(2n + 1) - f(2n))</math> | ||
+ | <math> f(4n + 3)-f(4n+2)= 2(f(2n + 1) - f(2n))</math> | ||
+ | |||
+ | And so, if <math> n</math> is even and <math> 2^{p+1}>n\geq 2^p>1</math>, we have <math> f(n+1)-f(n)=2^p</math> | ||
+ | |||
+ | So, if we have an even <math> n=\sum_{i=1}^{k} 2^{a_i}</math>, where <math> \{a_i\}</math> is a strictly increasing sequence with <math> a_1>0</math> (<math> n</math> even) : <math> f(n+1)=2^{a_k}+f(n)</math> | ||
+ | Then <math> f(n)=f(\sum_{i=1}^{k} 2^{a_i})</math> <math> =f(\sum_{i=1}^{k} 2^{a_i-a_1})</math> <math> =2^{a_k-a_1}+f(\sum_{i=2}^{k} 2^{a_i-a_1})</math> | ||
+ | And so <math> 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})</math> | ||
+ | |||
+ | And it is easy to conclude that <math> f(\sum_{i=1}^{k} 2^{a_i})=\sum_{i=1}^{k} 2^{a_k-a_i}</math> and that applying <math> f(n)</math> means reversing the order of binary representation of n (and this could be also easily shown with induction). | ||
+ | |||
+ | So <math> f(n)=n</math> occurs if and only if the binary representation of n is symetrical. | ||
+ | |||
+ | It remains to count these "symetric" numbers. We have exactly <math> 2^{\lceil\frac{m-1}{2}\rceil}</math> such numbers in <math> [2^m,2^{m+1})</math>. So : | ||
+ | We have exactly 1 such numbers in <math> [1,2)</math> | ||
+ | We have exactly 1 such numbers in <math> [2,4)</math> | ||
+ | We have exactly 2 such numbers in <math> [4,8)</math> | ||
+ | We have exactly 2 such numbers in <math> [8,16)</math> | ||
+ | We have exactly 4 such numbers in <math> [16,32)</math> | ||
+ | We have exactly 4 such numbers in <math> [32,64)</math> | ||
+ | We have exactly 8 such numbers in <math> [64,128)</math> | ||
+ | We have exactly 8 such numbers in <math> [128,256)</math> | ||
+ | We have exactly 16 such numbers in <math> [256,512)</math> | ||
+ | We have exactly 16 such numbers in <math> [512,1024)</math> | ||
+ | |||
+ | Since <math> 1988=B11111000100</math>, positions 2 to 6 may be any between <math> 00000</math> and <math> 11101</math>, and so : | ||
+ | We have exactly 30 such numbers in <math> [1024,1988]</math> | ||
+ | |||
+ | And so the requested number is <math> 1+1+2+2+4+4+8+8+16+16+30=92</math> | ||
+ | |||
+ | This solution was posted and copyrighted by pco. The original thread for this problem can be found here: [https://aops.com/community/p951024] | ||
+ | |||
+ | ==Solution 2== | ||
+ | The main claim is following. | ||
+ | |||
+ | Claim: <math>f(n)</math> is equal to the result when <math>n</math> is written in binary and its digits are reversed. | ||
+ | Proof. Follows directly by induction. <math>\blacksquare</math> | ||
+ | |||
+ | So the question asks for the number of binary palindromes which are at most <math>1988 = 11111000100_2</math>. | ||
+ | For <math>k = 1, 2, \dots, 10</math> there are <math>2^{\left\lceil k/2 \right\rceil-1}</math> binary palindromes with <math>k</math> bits (note the first bit must be <math>1</math>). For <math>k=11</math>, the number of binary palindromes which are also less than <math>1988</math> is <math>2^5 - 2</math> (only <math>11111011111</math> and <math>11111111111</math> are missing). | ||
+ | Hence the final count is<cmath> 2^0+2^0 + 2^1+2^1 + 2^2+2^2 + 2^3+2^3 + 2^4+2^4 + (2^5-2) = 92. </cmath> | ||
+ | |||
+ | This solution was posted and copyrighted by v_Enhance. The original thread for this problem can be found here: [https://aops.com/community/p17304354] | ||
+ | |||
+ | ==Solution 3== | ||
+ | We claim that <math>f(x)</math> is the reversal of the digits of <math>x</math> in binary. We proceed by induction, because given <math>f(1)=f(2)=1</math> and <math>f(3)=3</math>, we can determine all other values, and this property holds for <math>f(1)</math>, <math>f(2)</math>, and <math>f(3)</math>. | ||
+ | |||
+ | We prove that all operations conserve this property. For <math>f(2n)=f(n)</math>, we are adding a zero at the end, thus obviously preserving this property. For <math>f(4n+1) = 2f(2n+1)-f(n)</math>, we see that letting <math>4n+1=\overline{a_1a_2\ldots a_k01}_2</math> gets that assuming this holds true for <math>f(2n+1)</math> and <math>f(n)</math>, then<cmath>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) </cmath><cmath>= 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</cmath>which keeps the property since <math>\overline{10a_ka_{k-1}\ldots a_2a_1}_2</math> is the reversal of <math>\overline{a_1a_2\ldots a_k01}_2</math> in binary. Similarly, letting <math>4n+1=\overline{a_1a_2\ldots a_k11}_2</math>, then<cmath>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) </cmath><cmath>= 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</cmath>which keeps the property since <math>\overline{11a_ka_{k-1}\ldots a_2a_1}_2</math> is the reversal of <math>\overline{a_1a_2\ldots a_k11}_2</math>. Due to this, we have proved that this property holds for all <math>n</math> which means we need to find the number of binary palindromes below <math>1988</math>. This number is just going to be, for <math>n<11</math>-digit numbers, <math>2^{\lfloor \frac {n-1}2 \rfloor}</math> ways, so summing up for less than <math>11</math> digits gets <math>62</math> ways. For <math>11</math>-digit numbers, we have <math>32</math> ways but need to subtract a few in which are greater than <math>1988</math>; there are two numbers we don't count, namely <math>2015</math> and <math>2047</math>. As a result, our answer is <math>62+30=\boxed{92}</math>. | ||
+ | |||
+ | This solution was posted and copyrighted by kevinmathz. The original thread for this problem can be found here: [https://aops.com/community/p19065340] | ||
+ | |||
+ | == See Also == {{IMO box|year=1988|num-b=2|num-a=4}} | ||
+ | |||
+ | [[Category:Functional Equation Problems]] | ||
+ | [[Category:Olympiad Algebra Problems]] |
Latest revision as of 11:35, 30 January 2021
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
, then
which keeps the property since
is the reversal of
in binary. Similarly, letting
, then
which 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 |