Yo-yo-problem (BOMC-2)

Discussion on Bangladesh National Math Camp
sourav das
Posts: 461
Joined: Wed Dec 15, 2010 10:05 am
Location: Dhaka
Contact:

Yo-yo-problem (BOMC-2)

Unread post by sourav das » Tue Mar 27, 2012 9:57 am

Prove that, we can choose $2^k$ different numbers from $0,1,2$.......$3^k-1$, so that three numbers are in arithmetic progression will not occur.
You spin my head right round right round,
When you go down, when you go down down......
(-$from$ "$THE$ $UGLY$ $TRUTH$" )

Hasib
Posts: 238
Joined: Fri Dec 10, 2010 11:29 am
Location: খুলনা, বাংলাদেশ
Contact:

Re: Yo-yo-problem (BOMC-2)

Unread post by Hasib » Tue Mar 27, 2012 11:08 am

sourav das wrote:Prove that, we can choose $2^k$ different numbers from $0,1,2$.......$3^k-1$, so that three numbers are in arithmetic progression will not occur.
"three numbers are in arithmetic progression" -মানে??? একটু বাংলায় বলেন........
A man is not finished when he's defeated, he's finished when he quits.

sourav das
Posts: 461
Joined: Wed Dec 15, 2010 10:05 am
Location: Dhaka
Contact:

Re: Yo-yo-problem (BOMC-2)

Unread post by sourav das » Tue Mar 27, 2012 11:53 am

মানে হল, তোমার নেওয়া ঐ $2^k$ সংখ্যক সংখ্যার মাঝে যদি তিনটা সংখ্যা $a,b,c$ নেয়া হয় তাহলে $a,b,c$ দ্বারা কোন সমান্তর ধারা তৈরি করা সম্ভব হবে না। মানে $a+b=2c$ এই রকম কখনই হবে না।
You spin my head right round right round,
When you go down, when you go down down......
(-$from$ "$THE$ $UGLY$ $TRUTH$" )

User avatar
*Mahi*
Posts: 1175
Joined: Wed Dec 29, 2010 12:46 pm
Location: 23.786228,90.354974
Contact:

Re: Yo-yo-problem (BOMC-2)

Unread post by *Mahi* » Tue Mar 27, 2012 1:01 pm

The proof is easy by induction, though I have not found an $NT$-based proof yet. I'll post it as soon as I get one.
Proof:
It can be proved for the base cases easily, so skipping that part.
Now let there exist some $2^k$ integers in $0,3^k-1$ which has no three integers with arithmetic progression.Let the sequence be $a_1,a_2,...,a_{2^k}$, also let them be in increasing order.
Now let us consider the sequence $\{2.3^k+a_i\}$. It is easy to see that it also has the property of not containing three integers of arithmetic progression. Also all of them are less than or equal to $3^{k+1}-1$ and strictly greater than $2 \cdot 3^k -1$.
Now \[\frac{a_i+(2 \cdot3^k+a_j)}{2} = 3^k+\frac {a_i+a_j}2 > 3^k-1 > a_x\] for any $i,j,x$
And also \[\frac{a_i+(2 \cdot3^k+a_j)}{2} \leq \frac {2 \cdot 3^k+3^k-1+3^k-1}2 = 2 \cdot 3^k -1 < 2 \cdot 3^k +a_x\] for any $i,j,x$.
So the sequence \[a_1,a_2, \cdots a_{2^k}, (2 \cdot 3^k+a_1),(2 \cdot 3^k+a_2), \cdots (2 \cdot 3^k+a_{2^k})\] has exactly $2 \cdot 2^k =2^{k+1}$ elements and has no three elements forming an arithmetic sequence.
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

Post Reply