IMO '94 P3

Discussion on International Mathematical Olympiad (IMO)
User avatar
Abdullah Al Tanzim
Posts:24
Joined:Tue Apr 11, 2017 12:03 am
Location:Dhaka, Bangladesh.
IMO '94 P3

Unread post by Abdullah Al Tanzim » Sun Oct 20, 2019 8:58 pm

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 integer $m$ for which there exists exactly one $k$ with $f(k)=m$.
Everybody is a genius.... But if you judge a fish by its ability to climb a tree, it will spend its whole life believing that it is stupid - Albert Einstein

User avatar
Abdullah Al Tanzim
Posts:24
Joined:Tue Apr 11, 2017 12:03 am
Location:Dhaka, Bangladesh.

Re: IMO '94 P3

Unread post by Abdullah Al Tanzim » Sun Oct 20, 2019 11:04 pm

Solution:
(a) Let $A= a_1,a_2,a_3,.... $ be the sequence of positive integers whose base $2$ representation has precisely three $1s$ and for all $k\in N$, $a_{k+1}>a_k$.

Claim 1: $0\leq f(k+1)-f(k)\leq 1$
Proof: Note that $2k+2 \in A$ iff $k+1 \in A$. Now, $f(k+1)-f(k)<0$ implies $k+1$ is in $A$ and $2k+1,2k+2$ isn't in $A$ but that's not possible.
Also, $f(k+1)-f(k)=2$ implies $2k+1,2k+2$ is in $A$ and $k+1$ isn't in $A$ which is not possible.
So, $0 \leq f(k+1)-f(k) \leq 1$.

Claim 2: $f$ never becomes a constant function.
Proof: Between two terms $(11100..0)_2$($n$ number of $0$) and $(11100...0)_2$($n+1$ number of $0$) $\in A$, we can say there are $^{n+3}C_2$ numbers that belongs to $A$.

As $(111..0)_2$($n$ number of $0$)$= 7.2^n$ and $(1110...0)_2$($n+1$ number of $0$)$= 7.2^{n+1}$,
we can say $f(7.2^n)= ^{n+3}C_2$ for all positive integer $n$.
So, $f$ can never become constant.

Therefore, for any positive integer $m$, there exists at least one positive integer $k$ such that $f(k)=m$.


(b) We claim that all the positive integers with the desired property are $\frac{n(n+1)}2+1$, $n\in N$
Let $B= b_1,b_2,.....$ be a sequence of positive integers such that $f(b_i)=f(k)$ implies $b_i=k$ and $b_{i+1}>b_i$ for all $i$

Claim 1: $b_n=2^{n+1}+2$
Proof: We can say that for all positive integer $n$ , $f(b_n)-f(b_n-1)=1$ and $f(b_n+1)-f(b_n)=1$.
So, the sequence $A$ must be of the following form:

$.......,b_n+1,...,2b_n-1,2n_n+1,2b_n+2,....$ or, $........,2b_n-1,2b_n+1,......$
It implies $2b_n-1,2b_n+1\in A$ and $2b_n$ isn't in $A$.

Thus we are interested in successive terms of the sequence $A$ whose difference is $2$.In this case, the terms must be of the form:
$........,(10....011)_2$($n$ number of $0$),$(10....101)_2,......$
So, $2b_n-1=1+2+2^{n+2} \Rightarrow b_n=2^{n+1}+2$.

Claim 2: $f(b_n)=\frac{n(n+1)} 2+1$
Proof: As $b_n+1,2b_n-1 \in A$ and $2b_n$ isn't in $A$ , $f(b_n)$ is the number of elements of the set ${b_n+1,b_n+2,....,2b_n-1}$ that belongs to $A$.

Also, $b_n+1= (10...011)_2$($n-1$ number of $0$) and $2b_n-1=(10...0011)_2$ ($n$ number of $0$)
So, Between $b_n+1$ and $2b_n-1$ there are $^{n+1}C_2+1$ positive integers whose base 2 representation has three $1s$.
Thus $f(b_n)= ^{n+1}C_2+1$.

So, all the positive integers $m$ for which there exists exactly one $k$ such that $f(k)=m$ are $\frac{n(n+1)}2+1$ , $n\in N$.
:D :D
Everybody is a genius.... But if you judge a fish by its ability to climb a tree, it will spend its whole life believing that it is stupid - Albert Einstein

Post Reply