## a problem from IUMO 09

For college and university level advanced Mathematics
ridowan007
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.

rakeen
Posts: 384
Joined: Thu Dec 09, 2010 5:21 pm
Location: Dhaka

### Re: a problem from IUMO 09

"Prove that there exist a power of two such that its"

I think you meant $2$
r@k€€/|/

ridowan007
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.

tanzad
Posts: 3
Joined: Sat Jul 09, 2011 4:07 am

### 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

nayel
Posts: 268
Joined: Tue Dec 07, 2010 7:38 pm
Location: Dhaka, Bangladesh or Cambridge, UK

### Re: a problem from IUMO 09

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]
How do you know that the last thousand digits of $n$ are only $1$'s and $2$'s?

By the way, this is a classic problem.
"Everything should be made as simple as possible, but not simpler." - Albert Einstein

tanzad
Posts: 3
Joined: Sat Jul 09, 2011 4:07 am

### 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

nayel
Posts: 268
Joined: Tue Dec 07, 2010 7:38 pm
Location: Dhaka, Bangladesh or Cambridge, UK

### 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

Corei13
Posts: 153
Joined: Tue Dec 07, 2010 9:10 pm
Location: Chittagong

### 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."
ধনঞ্জয় বিশ্বাস

Corei13
Posts: 153
Joined: Tue Dec 07, 2010 9:10 pm
Location: Chittagong

### 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}^{r-1} m^i \right )}{5^n} \cdot \frac{g}{2^n} = \{1|2\} $
It's true that $m^r k + \frac{(m -1)\left(\sum_{i=0}^{r-1} m^i \right )}{5^n} \cdot \frac{g}{2^n} = \{1|2\} $
Let, $m^r k + \frac{(m -1)\left(\sum_{i=0}^{r-1} m^i \right )}{5^n} \cdot \frac{g}{2^n} = h $
So, it's remain to prove, there exist r such that,
$m^r k + \frac{(m -1)\left(\sum_{i=0}^{r-1} m^i \right )}{5^n} \cdot \frac{g}{2^n} = h $ (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 $ and let $\frac{g}{2^n} \cdot \frac{(m -1)}{5^n} = z$
so, 2 is equivalent to $k + zr = h $, as $(z,5)=1$, there exist such $r$
So, the proof is completed!
ধনঞ্জয় বিশ্বাস

Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm
Location: Dhaka,Bangladesh

### 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. One one thing is neutral in the universe, that is $0$.