Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1988 IMO Problems/Problem 3"

(Created page with "A function <math>f</math> is defined on the positive integers by <math> f(1) = 1, f(3) = 3, f (2n) = f (n)</math> , <math> f(4n+1) = 2f(2n+1)−f(n), f(4n+3) = 3f(2n+1)−2f(n...")
 
 
(2 intermediate revisions by one other user not shown)
Line 1: Line 1:
−
A function <math>f</math> is defined on the positive integers by
+
==Problem==
−
<math> f(1) = 1, f(3) = 3, f (2n) = f (n)</math> ,
+
A function <math> f</math> defined on the positive integers (and taking positive integers values) is given by:
−
<math> f(4n+1) = 2f(2n+1)−f(n), f(4n+3) = 3f(2n+1)−2f(n)</math> ,
+
 
−
for all positive integers <math> n</math> .
+
<math> \begin{matrix} f(1) = 1, f(3) = 3 \\
−
Determine the number of positive integers <math> n</math> , less than or equal to <math> 1988</math> , for which <math> f(n) = n</math>  
+
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 $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.$

Solution 1

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$

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: $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.\]

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 $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}$.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1988_IMO_Problems/Problem_3&oldid=144056"