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

Unread post by ridowan007 » Tue Dec 14, 2010 8:07 pm

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.

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

Re: a problem from IUMO 09

Unread post by rakeen » Wed Dec 15, 2010 1:53 pm

"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

Unread post by ridowan007 » Wed Dec 15, 2010 3:51 pm

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

Unread post by tanzad » Sat Jul 09, 2011 4:23 am

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

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

Re: a problem from IUMO 09

Unread post by nayel » Thu Aug 11, 2011 11:51 pm

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

Unread post by tanzad » Fri Aug 12, 2011 12:37 am

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

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

Re: a problem from IUMO 09

Unread post by nayel » Fri Aug 12, 2011 12:12 pm

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

Unread post by Corei13 » Sat Aug 20, 2011 11:42 pm

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

Unread post by Corei13 » Tue Sep 13, 2011 4:52 pm

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

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

Re: a problem from IUMO 09

Unread post by Masum » Fri Feb 24, 2012 10:33 pm

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

Post Reply