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> |
− | + | 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 20: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)
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 the values
where
come from 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.