Page 1 of 2

a problem from IUMO 09

Posted: Tue Dec 14, 2010 8:07 pm
by ridowan007
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.

Re: a problem from IUMO 09

Posted: Wed Dec 15, 2010 1:53 pm
by rakeen
"Prove that there exist a power of two such that its"

I think you meant $2$

Re: a problem from IUMO 09

Posted: Wed Dec 15, 2010 3:51 pm
by ridowan007
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

Posted: Sat Jul 09, 2011 4:23 am
by tanzad
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

Re: a problem from IUMO 09

Posted: Thu Aug 11, 2011 11:51 pm
by nayel
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.

Re: a problem from IUMO 09

Posted: Fri Aug 12, 2011 12:37 am
by tanzad
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

Re: a problem from IUMO 09

Posted: Fri Aug 12, 2011 12:12 pm
by nayel
But here a power of $2$ means $2^n$, where $n$ is a positive integer, not a real number.

Re: a problem from IUMO 09

Posted: Sat Aug 20, 2011 11:42 pm
by Corei13
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

Posted: Tue Sep 13, 2011 4:52 pm
by Corei13
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\} [10]$
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\} [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 [2]$
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 [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

Posted: Fri Feb 24, 2012 10:33 pm
by Masum
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. :mrgreen: