Difference between revisions of "1994 IMO Problems/Problem 3"
(→Solution 2) |
Thriftypiano (talk | contribs) (→Solution) |
||
(5 intermediate revisions by 5 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | For any positive integer k, let f(k) be the number of elements in the set | + | For any positive integer <math>k</math>, let <math>f(k)</math> be the number of elements in the set |
− | {k + 1 | + | <math>\{k + 1, k + 2,\dots, 2k\}</math> whose base 2 representation has precisely three <math>1</math>s. |
− | * (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 <math>m</math>, there exists at least one positive integer <math>k</math> such that <math>f(k) = m</math>. |
− | * (b) Determine all positive integers m for which there exists exactly one k with f(k) = m. | + | * (b) Determine all positive integers <math>m</math> for which there exists exactly one <math>k</math> with <math>f(k) = m</math>. |
Line 72: | Line 72: | ||
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. | 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. | ||
− | ''' | + | '''b) 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. | 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. | ||
Line 80: | Line 80: | ||
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. | 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 | + | 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 difference is 2 and both are T (the only two binary numbers which 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+1}-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>. | 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+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. | 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. | ||
+ | |||
+ | ==See Also== | ||
+ | {{IMO box|year=1994|num-b=2|num-a=4}} |
Latest revision as of 18:59, 9 February 2024
Contents
[hide]Problem
For any positive integer , let be the number of elements in the set whose base 2 representation has precisely three s.
- (a) Prove that, for each positive integer , there exists at least one positive integer such that .
- (b) Determine all positive integers for which there exists exactly one with .
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.
b) 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 difference is 2 and both are T (the only two binary numbers which 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.
See Also
1994 IMO (Problems) • Resources | ||
Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
All IMO Problems and Solutions |