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

Revision as of 22:32, 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+2)=\tbinom n2 +1= n(n-1)/2 + 1$ with $n \ge 2$ are the only one-from-one values of f.

@@ Line 82: / Line 82: @@
 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.
+Since <math>f(2^n+1)=f(2^n)=\tbinom n2</math> we have that <math>f(2^n+2)=\tbinom n2 +1= n(n-1)/2 + 1</math> with <math>n \ge 2</math> are the only one-from-one values of f.

Page

Toolbox

Search