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 "1994 IMO Problems/Problem 3"

(→‎b) one-from-one values)
Line 1: Line 1:
−
3. For any positive integer k, let f(k) be the number of elements in the set
+
== Problem ==
 +
For any positive integer k, let f(k) be the number of elements in the set
 
{k + 1; k + 2;....; 2k} whose base 2 representation has precisely three 1s.
 
{k + 1; k + 2;....; 2k} whose base 2 representation has precisely three 1s.
 
* (a) Prove that, for each positive integer m, there exists at least one positive integer k such that f(k) = m.
 
* (a) Prove that, for each positive integer m, there exists at least one positive integer k such that f(k) = m.
Line 6: Line 7:
  
 
== Solution ==
 
== Solution ==
−
===a) Surjectivity of f===
+
 
 +
 
 +
=== Solution 1 ===
 +
 
 +
'''a) Surjectivity of f'''
 +
 
 
For space-time saving we say that a positive integer is a T-number or simply is T if it has exactly three 1s in his base two representation.
 
For space-time saving we say that a positive integer is a T-number or simply is T if it has exactly three 1s in his base two representation.
  
Line 38: Line 44:
 
then takes any positive integer value since <math>f(4)=1</math> and <math>f(2^n)</math> becomes arbitrarily large.
 
then takes any positive integer value since <math>f(4)=1</math> and <math>f(2^n)</math> becomes arbitrarily large.
  
−
=== b) one-from-one values ===
+
'''b) one-from-one values'''
  
 
By the fact that <math>f(2^n +2^r + 2^s)=f(2^n) + r +1 </math> where <math>r=1,2,...,n-1</math> and <math>r > s \ge 0</math>  
 
By the fact that <math>f(2^n +2^r + 2^s)=f(2^n) + r +1 </math> where <math>r=1,2,...,n-1</math> and <math>r > s \ge 0</math>  
Line 51: Line 57:
 
It is sufficient to prove that <math>f(k+1) \ge f(k)</math> but this follows by the fact that if k+1 is T then 2k+2 is T too.  
 
It is sufficient to prove that <math>f(k+1) \ge f(k)</math> but this follows by the fact that if k+1 is T then 2k+2 is T too.  
 
By the monotonicity of f <math>f( 2^n + 2)=f(2^n)+1=\tbinom n2 +1= n(n-1)/2 + 1</math> with <math>n \ge 2</math> are the only one-from-one values of f.
 
By the monotonicity of f <math>f( 2^n + 2)=f(2^n)+1=\tbinom n2 +1= n(n-1)/2 + 1</math> with <math>n \ge 2</math> are the only one-from-one values of f.
 +
 +
=== Solution 2 ===
 +
 +
'''a) Surjectivity of f'''
 +
 +
For space-time saving we say that a positive integer is a T-number or simply is T if it has exactly three 1s in his base two representation and define the sets <math>S(k)=\{k+1;k+2;...;2k\}</math>.
 +
So <math>f(k)</math> is the number of T-numbers in <math>S(k)</math>.
 +
 +
A positive even integer 2n is T iff n is T.(Fundamental theorem of T numbers)(FTT)
 +
 +
The function f is non-decreasing.
 +
It is sufficient to prove that <math>f(k+1) \ge f(k)</math>. This follows by (FTT) if k+1 is T then 2k+2 is T too; so passing from <math>S(k)</math> to <math>S(k+1)</math> we can loose a T-number <math>k+1</math> but we regain it with <math>2k+2</math> in <math>S(k+1)</math> so <math>f(k+1)</math> cannot be less than <math>f(k)</math>. We also have <math>f(k+1) \le f(k) + 1</math>. This would be false if <math>k+1</math> were not T and both <math>2k+1</math> and <math>2k+2</math> were T. But if <math>2k+2</math> were T then <math>k+1</math> would be T too by the (FTT).
 +
Then we have <math> f(k) \le f(k+1) \le f(k) + 1</math> that is <math>f(k+1)=f(k)</math> or <math>f(k+1)=f(k)+1</math>.
 +
But <math>f(4)=1</math> and <math>f(2^n)= \tbinom n2</math> so f takes all of the positive integer values because starting from 1 with step of 1 reaches arbitrarily large integer values.
 +
 +
'''a) one-from-one values of f'''
 +
 +
The one-from-one values <math>f(k)</math> are such that <math>f(k)=f(k-1)+1</math> and <math>f(k+1)=f(k)+1</math> since f is monotone non-decreasing and has step 1.
 +
 +
By the condition <math>f(k+1)=f(k)+1</math> since <math>k+1</math> is T iff <math>2k+2</math> is T we have that <math>2k+1</math> must be T.
 +
 +
By the condition <math>f(k)=f(k-1)+1</math> since <math>k</math> is T iff <math>2k</math> is T we have that <math>2k-1</math> must be T.
 +
 +
Then <math>2k-1</math> and <math>2k+1</math> must have the form <math>2^{n+1}+2^{r+1}+1</math> with <math>n>r\ge 0</math> since they are odd and <math>n \ge 2</math> since there is only 1 T-number less than 8 and they must have the same number of bits since their diferrence is 2 and both are T (the only two binary numbers wich differs by 2 and have different number of bits are <math>2^n+1</math> and <math>2^n-1</math> or <math>2^n</math> and <math>2^n-2</math> which are evidently not T). Let <math>2k+1=2^{n+1}+2^{j+1}+1</math> and <math>2k-1=2^{n+1}+2^{i+1}+1</math> with <math>j>i \ge 0</math>. Then <math>2k+ 1-(2k-1)=2^{j+i}-2^{i+1}=2</math> that is <math>j=1</math> and <math>i=0</math>.
 +
We conclude that <math>f(k)</math> is one-from-one for <math>k=2^n+2^j=2^n+2</math> with <math>n \ge 2</math>.
 +
Since <math>f(2^n+1)=f(2^n)=\tbinom n2</math> we have that <math>f(2^n+1)=\tbinom n2 +1= n(n-1)/2 + 1</math> with <math>n \ge 2</math> are the only one-from-one values of f.

Revision as of 22:25, 31 October 2009

Problem

For any positive integer k, let f(k) be the number of elements in the set {k + 1; k + 2;....; 2k} whose base 2 representation has precisely three 1s.

  • (a) Prove that, for each positive integer m, there exists at least one positive integer k such that f(k) = m.
  • (b) Determine all positive integers m for which there exists exactly one k with f(k) = m.


Solution

Solution 1

a) Surjectivity of f

For space-time saving we say that a positive integer is a T-number or simply is T if it has exactly three 1s in his base two representation.

It's easy to see that (one has to place two 1s in the less n significative bit of a (n+1)-bit number)

  • $f(2^n) = \tbinom n2 = \sum_{i=1}^{n-1} i$ whence
  • $f(2^{n+1}) = f(2^n)+n$

Now consider $k=2^n + 2$ with $n \ge 2$ and the corrisponding set $S(2^n+2)=\{2^n+3,...,2^{n+1},2^{n+1}+1,2^{n+1}+2,2^{n+1}+3,2^{n+1}+4\}$ whose subset $\{2^n+3,...,2^{n+1}\}$ contains $f(2^n)$ T-numbers since $S(2^n)=\{2^n+1,...,2^{n+1}\}=\{2^n+1,2^n+2\} \cup \{2^n+3,...,2^{n+1}\}$ contains $f(2^n)$ T-numbers by definition but $\{2^n+1,2^n+2\}$ has none. So $S(2^n+2)=\{2^n+3,...,2^{n+1}\} \cup \{2^{n+1}+1,2^{n+1}+2,2^{n+1}+3,2^{n+1}+4\}$ but the last set has the only T-number $2^{n+1}+3$. We conclude that:

  • $f(2^n + 2)=f(2^n)+1$

Now consider $k=2^n +2^r + 2^s$ with $n>r>s\ge 0$ and $n\ge 2$. We explicitly calculate f(k) for such numbers. So we have to calculate how many T-numbers are in the set $S(k)=\{2^n +2^r + 2^s+1;...;2^{n+1} +2^{r+1} + 2^{s+1}\}$.

The T-numbers less than $2^{n+1}$ in $S(k)$ are $T_1 = \{2^n +2^j + 2^i : (j=r \wedge r>i>s) \vee (n>j>r \wedge j>i>0) \}$ whence $\# (T_1)= r-s-1 + \sum_{h=r+1}^{n-1} h$.

The T-numbers greater than $2^{n+1}$ in $S(k)$ are $T_2 = \{2^{n+1} +2^j + 2^i : (j=r+1 \wedge s+1 \ge i\ge 0) \vee (r\ge j \ge 1 \wedge j>i \ge 0) \}$ whence $\# (T_2)= s+2 + \sum_{h=1}^{r} h$.

Therefore $S(k)$ contains $\# (T_1) + \# (T_2)=r-s-1 + s+2 + \sum_{h=1}^{r}h +\sum_{h=r+1}^{n-1} h = \sum_{h=1}^{n-1} h + r + 1$ T-numbers and we have:

  • $f(2^n +2^r + 2^s)=f(2^n) + r +1$ where $r=1,2,...,n-1$ ans $r > s \ge 0$ .

Summarizing

  • $f(2^{n+1}) = f(2^n)+n$
  • $f(2^n + 2)=f(2^n)+1$
  • $f(2^n +2^r + 2^s)=f(2^n) + r +1$ where $r=1,2,...,n-1$ and $r > s \ge 0$ .

That's to say that f takes all the values from $f(2^n)$ to $f(2^{n+1})$ for every $n \ge 2$ and then takes any positive integer value since $f(4)=1$ and $f(2^n)$ becomes arbitrarily large.

b) one-from-one values

By the fact that $f(2^n +2^r + 2^s)=f(2^n) + r +1$ where $r=1,2,...,n-1$ and $r > s \ge 0$ it follows that each of the values $f(2^n) + r +1$ where $r=2,...,n-1$ come from at least two different k because there are at least two different choices for $s$. These values are $f(2^n)+3,f(2^n)+4,...,f(2^n)+n=f(2^{n+1})$.

Thus the only possible one-from-one values are $f(2^n)+1$ that come from $k=2^n + 2$ and $f(2^n)+2$ that come from $k=2^n + 3$.

If $k=2^n + 3$ we have $f(k)=f(k+1)$ because k+1 is not T and $2k+1=2^{n+1} + 7$ and $2k+2=2^{n+1} + 8$ are not T so f maps $2^n + 3$ and $2^n + 4$ to $f(2^n)+2$.

If $k=2^n + 2$ then $f(k+1)=f(2^n)+2>f(k)=f(2^n)+1>f(k-1)=f(2^n+1)=f(2^n)$. The function f is non-decreasing. It is sufficient to prove that $f(k+1) \ge f(k)$ but this follows by the fact that if k+1 is T then 2k+2 is T too. By the monotonicity of f $f( 2^n + 2)=f(2^n)+1=\tbinom n2 +1= n(n-1)/2 + 1$ with $n \ge 2$ are the only one-from-one values of f.

Solution 2

a) Surjectivity of f

For space-time saving we say that a positive integer is a T-number or simply is T if it has exactly three 1s in his base two representation and define the sets $S(k)=\{k+1;k+2;...;2k\}$. So $f(k)$ is the number of T-numbers in $S(k)$.

A positive even integer 2n is T iff n is T.(Fundamental theorem of T numbers)(FTT)

The function f is non-decreasing. It is sufficient to prove that $f(k+1) \ge f(k)$. This follows by (FTT) if k+1 is T then 2k+2 is T too; so passing from $S(k)$ to $S(k+1)$ we can loose a T-number $k+1$ but we regain it with $2k+2$ in $S(k+1)$ so $f(k+1)$ cannot be less than $f(k)$. We also have $f(k+1) \le f(k) + 1$. This would be false if $k+1$ were not T and both $2k+1$ and $2k+2$ were T. But if $2k+2$ were T then $k+1$ would be T too by the (FTT). Then we have $f(k) \le f(k+1) \le f(k) + 1$ that is $f(k+1)=f(k)$ or $f(k+1)=f(k)+1$. But $f(4)=1$ and $f(2^n)= \tbinom n2$ so f takes all of the positive integer values because starting from 1 with step of 1 reaches arbitrarily large integer values.

a) one-from-one values of f

The one-from-one values $f(k)$ are such that $f(k)=f(k-1)+1$ and $f(k+1)=f(k)+1$ since f is monotone non-decreasing and has step 1.

By the condition $f(k+1)=f(k)+1$ since $k+1$ is T iff $2k+2$ is T we have that $2k+1$ must be T.

By the condition $f(k)=f(k-1)+1$ since $k$ is T iff $2k$ is T we have that $2k-1$ must be T.

Then $2k-1$ and $2k+1$ must have the form $2^{n+1}+2^{r+1}+1$ with $n>r\ge 0$ since they are odd and $n \ge 2$ since there is only 1 T-number less than 8 and they must have the same number of bits since their diferrence is 2 and both are T (the only two binary numbers wich differs by 2 and have different number of bits are $2^n+1$ and $2^n-1$ or $2^n$ and $2^n-2$ which are evidently not T). Let $2k+1=2^{n+1}+2^{j+1}+1$ and $2k-1=2^{n+1}+2^{i+1}+1$ with $j>i \ge 0$. Then $2k+ 1-(2k-1)=2^{j+i}-2^{i+1}=2$ that is $j=1$ and $i=0$. We conclude that $f(k)$ is one-from-one for $k=2^n+2^j=2^n+2$ with $n \ge 2$. Since $f(2^n+1)=f(2^n)=\tbinom n2$ we have that $f(2^n+1)=\tbinom n2 +1= n(n-1)/2 + 1$ with $n \ge 2$ are the only one-from-one values of f.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1994_IMO_Problems/Problem_3&oldid=32897"