BdMO H.Sec 2010. Problem 10

Discussion on Bangladesh Mathematical Olympiad (BdMO) National
User avatar
Zzzz
Posts: 172
Joined: Tue Dec 07, 2010 6:28 am
Location: 22° 48' 0" N / 89° 33' 0" E

BdMO H.Sec 2010. Problem 10

Unread post by Zzzz » Thu Dec 09, 2010 2:00 pm

আচ্ছা, আমি কখনোই ১০ নম্বর সমস্যাটার সমাধান কোথাও দেখি নাই। নিজেও করতে পারি নাই অবশ্যই। কেউ কি দিতে পারেন?

সমস্যাটা হইলঃ

Let $a_1,a_2,…,a_k,…,a_n$ is a sequence of distinct positive real numbers such that $a_1<a_2<…<a_k$ and $a_k>a_{k+1}>…>a_n$ . A grasshopper is to jump along the real axis, starting at the point $O$ and making $n$ jumps to right of lengths $a_1,a_2,…,a_n$ respectively. Prove that, once he reaches the rightmost point, he can come back to point $O$ by making $n$ jumps to left of of lengths $a_1,a_2,…,a_n$ in some order such that he never lands on a point which he already visited while jumping to the right. (The only exceptions are point O and the rightmost point).
Every logical solution to a problem has its own beauty.
(Important: Please make sure that you have read about the Rules, Posting Permissions and Forum Language)

tanvirab
Posts: 446
Joined: Tue Dec 07, 2010 2:08 am
Location: Pasadena, California, U.S.A.

Re: BdMO H.Sec 2010. Problem 10

Unread post by tanvirab » Sun Dec 12, 2010 12:16 pm

The case $n=1$ is trivial. Case $n=2$ is easy. Do induction with base case $n=2$.

Always try induction if the problem is concerning some finite set.

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

Re: BdMO H.Sec 2010. Problem 10

Unread post by sourav das » Tue Jan 29, 2013 4:54 pm

Solution:
Note that $min\{a_i\}\in\{a_1,a_n\}$ and all are distinct. Let the rightmost point be $R$
Case:1
$min\{a_i\}=a_n$
Then first jump $a_{n-1}$
second jump $a_{n-2}$
...
...
$i'th$ jump $a_{n-i}$ (Where $a_0=a_n$)
......
We'll prove that this process works.
After $i'th$ jump (for $i<n$), the distance from point $R$ is $a_{n-1}+a_{n-2}+.....+a_{n-i}$ which must lie between the distances $a_n+a_{n-1}+.....+a_{n-i+1}$ and $a_n+a_{n-1}+....+a_{n-i}$ from $R$. (as $a_n<a_{n-i}$) and at last jump the grasshopper comes to point $O$

Case:2
$min\{a_i\}=a_1$
Then first jump $a_1$
second jump $a_n$
...
...
$i'th$ jump $a_{n-i+1}$
...
We'll prove that this process works.
After $i'th$ jump (for $i<n$), the distance from point $R$ is $a_1+a_{n}+a_{n-2}+.....+a_{n-i+1}$ which must lie between the distances $a_n+a_{n-1}+.....+a_{n-i+1}$ and $a_n+a_{n-1}+....+a_{n-i}$ from $R$. (as $a_1<a_{n-i}$) and at last jump the grasshopper comes to point $O$

Thus in these processes, the grasshopper won't make any double steps in any point except $O$ (Proved)
Please check my solution. Am I missing any point? :?
You spin my head right round right round,
When you go down, when you go down down......
(-$from$ "$THE$ $UGLY$ $TRUTH$" )

Post Reply