Difference between revisions of "1994 IMO Problems/Problem 3"
(→b) one-from-one values) |
|||
Line 1: | Line 1: | ||
− | + | == 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''' | |
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 23:25, 31 October 2009
Contents
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)
whence
Now consider with
and the corrisponding set
whose subset
contains
T-numbers since
contains
T-numbers by definition but
has none. So
but the last set has the only T-number
. We conclude that:
Now consider with
and
.
We explicitly calculate f(k) for such numbers.
So we have to calculate how many T-numbers are in the set
.
The T-numbers less than in
are
whence
.
The T-numbers greater than in
are
whence
.
Therefore contains
T-numbers and we have:
where
ans
.
Summarizing
where
and
.
That's to say that f takes all the values from to
for every
and
then takes any positive integer value since
and
becomes arbitrarily large.
b) one-from-one values
By the fact that where
and
it follows that each of the values
where
come from at least two different k because there are at least two different choices for
. These values are
.
Thus the only possible one-from-one values are that come from
and
that come from
.
If we have
because k+1 is not T and
and
are not T so f maps
and
to
.
If then
.
The function f is non-decreasing.
It is sufficient to prove that
but this follows by the fact that if k+1 is T then 2k+2 is T too.
By the monotonicity of f
with
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 .
So
is the number of T-numbers in
.
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 . This follows by (FTT) if k+1 is T then 2k+2 is T too; so passing from
to
we can loose a T-number
but we regain it with
in
so
cannot be less than
. We also have
. This would be false if
were not T and both
and
were T. But if
were T then
would be T too by the (FTT).
Then we have
that is
or
.
But
and
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 are such that
and
since f is monotone non-decreasing and has step 1.
By the condition since
is T iff
is T we have that
must be T.
By the condition since
is T iff
is T we have that
must be T.
Then and
must have the form
with
since they are odd and
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
and
or
and
which are evidently not T). Let
and
with
. Then
that is
and
.
We conclude that
is one-from-one for
with
.
Since
we have that
with
are the only one-from-one values of f.