Turkey TST 2014

For discussing Olympiad Level Combinatorics problems
User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:
Turkey TST 2014

Unread post by Phlembac Adib Hasan » Tue Sep 30, 2014 12:45 pm

At the bottom-left corner of a $2014\times 2014$ chessboard, there are some green worms and at the top-left corner of the same chessboard, there are some brown worms. Green worms can move only to right and up, and brown worms can move only to right and down. After a while, the worms make some moves and all of the unit squares of the chessboard become occupied at least once throughout this process. Find the minimum total number of the worms.

Comment: Really beautiful problem 8-)
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

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

Re: Turkey TST 2014

Unread post by *Mahi* » Wed Oct 01, 2014 7:48 pm

Hint:
${\color{White} {\text{Minimize the intersections, and you've minimized the number of worms} } }$ ;)
Please read Forum Guide and Rules before you post.

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

Nur Muhammad Shafiullah | Mahi

Ragib Farhat Hasan
Posts:62
Joined:Sun Mar 30, 2014 10:40 pm

Re: Turkey TST 2014

Unread post by Ragib Farhat Hasan » Mon Nov 04, 2019 9:32 pm

The problem can be approached by first cutting the board in half; let the upper-half be called $BROWN$ and the lower-half be called $GREEN$.

Now, a pair of brown worms each from the top-left corner move to each of the squares (except the last one) in the diagonal of the LHS $1007\times1007$ square of the $BROWN$ region after a finite set of moves. Only one brown worm occupies the last square of the diagonal.

Now, it can be implied that when each two worms in the mentioned squares each moves to the right and down directions respectively, with none of the worms' paths intersecting, all the unit squares in the entire $BROWN$ region is occupied at least once.

The same procedure can be carried out in the $GREEN$ region, only this time the worms will move right and up.

Therefore, the minimum total number of worms $=> 1006\times2\times2+2=4026$.

Ragib Farhat Hasan
Posts:62
Joined:Sun Mar 30, 2014 10:40 pm

Re: Turkey TST 2014

Unread post by Ragib Farhat Hasan » Mon Nov 04, 2019 11:39 pm

Ragib Farhat Hasan wrote:
Mon Nov 04, 2019 9:32 pm
The problem can be approached by first cutting the board in half; let the upper-half be called $BROWN$ and the lower-half be called $GREEN$.

Now, a pair of brown worms each from the top-left corner move to each of the squares (except the last one) in the diagonal of the LHS $1007\times1007$ square of the $BROWN$ region after a finite set of moves. Only one brown worm occupies the last square of the diagonal.

Now, it can be implied that when each two worms in the mentioned squares each moves to the right and down directions respectively, with none of the worms' paths intersecting, all the unit squares in the entire $BROWN$ region is occupied at least once.

The same procedure can be carried out in the $GREEN$ region, only this time the worms will move right and up.

Therefore, the minimum total number of worms $=> 1006\times2\times2+2=4026$.
This solution is wrong. I didn't see another possibility of the situation (a very common mistake in Combi problems). :D

Ragib Farhat Hasan
Posts:62
Joined:Sun Mar 30, 2014 10:40 pm

Re: Turkey TST 2014

Unread post by Ragib Farhat Hasan » Tue Nov 05, 2019 12:34 am

The first step remains the same: cutting the board in half and denoting the upper-half as $BROWN$ and the lower-half as $GREEN$.

Now, two brown worms ($B_1$ and $B_2$) start from the top-left corner; $B_1$ goes to the right and $B_2$ goes to the down direction.
Upon reaching the end of the board, $B_1$ starts going in the down direction, and...
Upon reaching the end of the $BROWN$ region, $B_2$ starts going in the right direction.
They both keep moving until all the outermost unit squares of the $BROWN$ region is occupied at least once in the process.

Similarly, two brown worms ($B_3$ and $B_4$) starts from the unit square diagonally below the top-left corner and moves around the board on a path parallel to the ones of $B_1$ and $B_2$ until all the second outermost unit squares of the $BROWN$ region is occupied at least once in the process.

Moving on, it can be deduced that the smaller side of each of the rectangular paths that each pair of brown worms cover in their journey gets smaller as such $=> 1007, 1005, 1003,...,7,5,3$. Let the series be denoted as $B$.

Lastly, just $1008$ unit squares lying in a straight horizontal line right through the middle of the $BROWN$ region remains unoccupied at least once, which are covered by a single worm moving to its right.

So, there are $503$ terms in the series $B$. In each case, there were two worms.
Therefore, required minimum total number of brown worms is $(503\times2+1)=1007$.

The entire process can be repeated in the $GREEN$ region, only this time the worms will move right and up.

Hence, the minimum total number of worms required is $(1007\times2)=2014$.

Ragib Farhat Hasan
Posts:62
Joined:Sun Mar 30, 2014 10:40 pm

Re: Turkey TST 2014

Unread post by Ragib Farhat Hasan » Tue Nov 05, 2019 12:52 am

Taking a $n\times n$ chessboard, where $n\equiv 2$ (mod $4$) and experimenting with smaller values of $n$ (like 6 and 10), yields the pattern which is denoted as series $B$ in the solution.

From there, the rest was quite straight-forward! :D

But yeah, it is actually an elegant problem, primarily because it can be proved as a general solution: for a $n\times n$ chessboard , where $n\equiv2$ (mod $4$), the answer is also $n$.

Long live Combinatorics!!! :lol: :lol: :lol:

Ragib Farhat Hasan
Posts:62
Joined:Sun Mar 30, 2014 10:40 pm

Re: Turkey TST 2014

Unread post by Ragib Farhat Hasan » Tue Nov 05, 2019 12:57 am

BTW, I wonder...

This problem was posted over 5 years ago.

And no one posted a solution to this problem in half a decade!!! WOW!!!

samiul_samin
Posts:1007
Joined:Sat Dec 09, 2017 1:32 pm

Re: Turkey TST 2014

Unread post by samiul_samin » Tue Nov 12, 2019 8:25 am

Ragib Farhat Hasan wrote:
Tue Nov 05, 2019 12:57 am
BTW, I wonder...

This problem was posted over 5 years ago.

And no one posted a solution to this problem in half a decade!!! WOW!!!
Because there is no active member!

Post Reply