a problem from IUMO 09

 Posts: 11
 Joined: Tue Dec 14, 2010 1:09 pm
a problem from IUMO 09
Last year's inter university math olympiad a found a problem which I still can't solve. If any one could give a prove?
Prove that there exist a power of two such that its last(right side) 1000 digit is only containing 1 or 2.
Prove that there exist a power of two such that its last(right side) 1000 digit is only containing 1 or 2.
Re: a problem from IUMO 09
"Prove that there exist a power of two such that its"
I think you meant $2$
I think you meant $2$
r@k€€//

 Posts: 11
 Joined: Tue Dec 14, 2010 1:09 pm
Re: a problem from IUMO 09
Yes. I mean there exist any 2^X such that its right 1000 digit is only contain 1 or 2.
Re: a problem from IUMO 09
let,
2^x=...(thousand 1 or 2)=n.
=> log2 (2^x)=log2 (n).
=> x=m, where m=log2 (n).
Now, since m is a real number, there exists such x. [Proved]
Alhamdulillah!
Tanvir Zawad
2^x=...(thousand 1 or 2)=n.
=> log2 (2^x)=log2 (n).
=> x=m, where m=log2 (n).
Now, since m is a real number, there exists such x. [Proved]
Alhamdulillah!
Tanvir Zawad
Re: a problem from IUMO 09
How do you know that the last thousand digits of $n$ are only $1$'s and $2$'s?tanzad wrote:let,
2^x=...(thousand 1 or 2)=n.
=> log2 (2^x)=log2 (n).
=> x=m, where m=log2 (n).
Now, since m is a real number, there exists such x. [Proved]
By the way, this is a classic problem.
"Everything should be made as simple as possible, but not simpler."  Albert Einstein
Re: a problem from IUMO 09
I defined n to be a number whose last 1000 digits are only 1 or 2.
Note that, asking whether there exists any 2^X such that its right 1000 digits are only 1 or 2 is equivalent to asking whether log2 (n) exists.
log2 (n) exists, and hence there exists such 2^X.
Tanvir Zawad
Note that, asking whether there exists any 2^X such that its right 1000 digits are only 1 or 2 is equivalent to asking whether log2 (n) exists.
log2 (n) exists, and hence there exists such 2^X.
Tanvir Zawad
Re: a problem from IUMO 09
But here a power of $2$ means $2^n$, where $n$ is a positive integer, not a real number.
"Everything should be made as simple as possible, but not simpler."  Albert Einstein
Re: a problem from IUMO 09
I proved a partial result "there exist a power of two such that its last(right side) 1000 digit is only containing 1, 2, 6 or 7."
ধনঞ্জয় বিশ্বাস
Re: a problem from IUMO 09
We'll denote $a \equiv b$ mod $(m)$ by $a=b [m]$. Let $s_n = \phi ( 5^n )$
Now, we'll prove by induction on $n$ that, "there exist a power of two such that its last(right side) $n$ digit is only containing 1, 2"
It's true for $n=1$, as $2^1 = 2$
Let's it true for $n$.
then there exist $c$ and $g$ such that $2^c = g [10^n]$ where $g$ is a $n$digit number whose digits are only 1 and 2.
It's easy to verify that $2^{a+s_n} = 2^a [10^n ]$
Now let, $2^c = 10^n k + g$
We'll prove that, there exist $r$ such that $2^{c + r s_n} = g + \{10^n \text{ or } 2\cdot 10^n \} [10^{n+1}]$ (1)
let, $ 2^{s_n}= m$
Then (1) is equivalent to, $2^c \dot (2^{s_n})^r = (10^n k + g)m^r = g + \{10^n  2\cdot 10^n \} [10^{n+1}]$
or, $10^n \left(m^r k  \{1  2 \} \right) + \left ( m^r 1 \right) g = 0 [10^{n+1}]$
or, $m^r k + \frac{(m 1)\left(\sum_{i=0}^{r1} m^i \right )}{5^n} \cdot \frac{g}{2^n} = \{12\} [10]$
It's true that $m^r k + \frac{(m 1)\left(\sum_{i=0}^{r1} m^i \right )}{5^n} \cdot \frac{g}{2^n} = \{12\} [2]$
Let, $m^r k + \frac{(m 1)\left(\sum_{i=0}^{r1} m^i \right )}{5^n} \cdot \frac{g}{2^n} = h [2]$
So, it's remain to prove, there exist r such that,
$m^r k + \frac{(m 1)\left(\sum_{i=0}^{r1} m^i \right )}{5^n} \cdot \frac{g}{2^n} = h [5]$ (2)
It's obvious that, $c \geq n$, and so, from $g=2^c  10^n k$, we get $\frac{g}{2^n}$ is a integer not divisible by 5, and as $m^r = (2^r)^{s_n} = 1 [5^n]$,$\frac{(m 1)}{5^n}$ is also a integer which is not divisible by 5 as it is straightforward that, 2 is a primitive root modulo $5^{n+1}$
Now, we see $m = 1 [5]$ and let $\frac{g}{2^n} \cdot \frac{(m 1)}{5^n} = z $
so, 2 is equivalent to $k + zr = h [5]$, as $(z,5)=1$, there exist such $r$
So, the proof is completed!
Now, we'll prove by induction on $n$ that, "there exist a power of two such that its last(right side) $n$ digit is only containing 1, 2"
It's true for $n=1$, as $2^1 = 2$
Let's it true for $n$.
then there exist $c$ and $g$ such that $2^c = g [10^n]$ where $g$ is a $n$digit number whose digits are only 1 and 2.
It's easy to verify that $2^{a+s_n} = 2^a [10^n ]$
Now let, $2^c = 10^n k + g$
We'll prove that, there exist $r$ such that $2^{c + r s_n} = g + \{10^n \text{ or } 2\cdot 10^n \} [10^{n+1}]$ (1)
let, $ 2^{s_n}= m$
Then (1) is equivalent to, $2^c \dot (2^{s_n})^r = (10^n k + g)m^r = g + \{10^n  2\cdot 10^n \} [10^{n+1}]$
or, $10^n \left(m^r k  \{1  2 \} \right) + \left ( m^r 1 \right) g = 0 [10^{n+1}]$
or, $m^r k + \frac{(m 1)\left(\sum_{i=0}^{r1} m^i \right )}{5^n} \cdot \frac{g}{2^n} = \{12\} [10]$
It's true that $m^r k + \frac{(m 1)\left(\sum_{i=0}^{r1} m^i \right )}{5^n} \cdot \frac{g}{2^n} = \{12\} [2]$
Let, $m^r k + \frac{(m 1)\left(\sum_{i=0}^{r1} m^i \right )}{5^n} \cdot \frac{g}{2^n} = h [2]$
So, it's remain to prove, there exist r such that,
$m^r k + \frac{(m 1)\left(\sum_{i=0}^{r1} m^i \right )}{5^n} \cdot \frac{g}{2^n} = h [5]$ (2)
It's obvious that, $c \geq n$, and so, from $g=2^c  10^n k$, we get $\frac{g}{2^n}$ is a integer not divisible by 5, and as $m^r = (2^r)^{s_n} = 1 [5^n]$,$\frac{(m 1)}{5^n}$ is also a integer which is not divisible by 5 as it is straightforward that, 2 is a primitive root modulo $5^{n+1}$
Now, we see $m = 1 [5]$ and let $\frac{g}{2^n} \cdot \frac{(m 1)}{5^n} = z $
so, 2 is equivalent to $k + zr = h [5]$, as $(z,5)=1$, there exist such $r$
So, the proof is completed!
ধনঞ্জয় বিশ্বাস
Re: a problem from IUMO 09
Why did you use an alternative notation? May be you did this for typing help. But this looks ugly to me
Well. I didn't look at your solution but I proved the same as you did.
Also prove that there are infinite multiples of $2$ having the digits with $1$ and $2$ only.
In fact, we can prove that there are powers of $2$ with only digits $1$ and $2$.(Actually Ridwan vai gave me this problem in the university personally. While solving his problem, I found this problem generally.) Try it now!
However, before this post the number of my posts was the reverse of the number of your posts.
Well. I didn't look at your solution but I proved the same as you did.
Also prove that there are infinite multiples of $2$ having the digits with $1$ and $2$ only.
In fact, we can prove that there are powers of $2$ with only digits $1$ and $2$.(Actually Ridwan vai gave me this problem in the university personally. While solving his problem, I found this problem generally.) Try it now!
However, before this post the number of my posts was the reverse of the number of your posts.
One one thing is neutral in the universe, that is $0$.