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"

(Created page with '3. 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 eac…')
 
(→‎a) Surjectivity of f)
Line 13: Line 13:
 
* <math>f(2^{n+1}) = f(2^n)+n </math>
 
* <math>f(2^{n+1}) = f(2^n)+n </math>
  
−
Now consider <math>k=2^n + 2</math> and the corrisponding set <math>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\}</math>
+
Now consider <math>k=2^n + 2</math> with <math>n \ge 2</math> and the corrisponding set <math>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\}</math>
−
the subset <math>\{2^n+3,...,2^{n+1}\}</math> contains <math>f(2^n)</math> T-numbers since <math>S(2^n)=\{2^n+1,...,2^{n+1}\}=\{2^n+1,2^n+2\} \cup \{2^n+3,...,2^{n+1}\}</math> contains <math>f(2^n)</math> T-numbers by definition but <math>\{2^n+1,2^n+2\}</math> has none. So <math>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\}</math> but the last set has the only T-number <math>2^{n+1}+3</math>. We conclude that:
+
whose subset <math>\{2^n+3,...,2^{n+1}\}</math> contains <math>f(2^n)</math> T-numbers since <math>S(2^n)=\{2^n+1,...,2^{n+1}\}=\{2^n+1,2^n+2\} \cup \{2^n+3,...,2^{n+1}\}</math> contains <math>f(2^n)</math> T-numbers by definition but <math>\{2^n+1,2^n+2\}</math> has none. So <math>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\}</math> but the last set has the only T-number <math>2^{n+1}+3</math>. We conclude that:
 
*<math>f(2^n + 2)=f(2^n)+1</math>
 
*<math>f(2^n + 2)=f(2^n)+1</math>
  

Revision as of 19:48, 31 October 2009

3. 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

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 the values $f(2^n) + r +1$ where $r=2,...,n-1$ come from 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.

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