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.
Re: Yo-yo-problem (BOMC-2)
Posted: Tue Mar 27, 2012 11:08 am
by Hasib
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" -মানে??? একটু বাংলায় বলেন........
Re: Yo-yo-problem (BOMC-2)
Posted: Tue Mar 27, 2012 11:53 am
by sourav das
মানে হল, তোমার নেওয়া ঐ $2^k$ সংখ্যক সংখ্যার মাঝে যদি তিনটা সংখ্যা $a,b,c$ নেয়া হয় তাহলে $a,b,c$ দ্বারা কোন সমান্তর ধারা তৈরি করা সম্ভব হবে না। মানে $a+b=2c$ এই রকম কখনই হবে না।
Re: Yo-yo-problem (BOMC-2)
Posted: Tue Mar 27, 2012 1:01 pm
by *Mahi*
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.