Turkey TST 2014
 Phlembac Adib Hasan
 Posts: 1016
 Joined: Tue Nov 22, 2011 7:49 pm
 Location: 127.0.0.1
 Contact:
Turkey TST 2014
At the bottomleft corner of a $2014\times 2014$ chessboard, there are some green worms and at the topleft 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
Comment: Really beautiful problem
Welcome to BdMO Online Forum. Check out Forum Guides & Rules
Re: Turkey TST 2014
Hint:
${\color{White} {\text{Minimize the intersections, and you've minimized the number of worms} } }$
${\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
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah  Mahi

 Posts: 62
 Joined: Sun Mar 30, 2014 10:40 pm
Re: Turkey TST 2014
The problem can be approached by first cutting the board in half; let the upperhalf be called $BROWN$ and the lowerhalf be called $GREEN$.
Now, a pair of brown worms each from the topleft 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$.
Now, a pair of brown worms each from the topleft 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$.

 Posts: 62
 Joined: Sun Mar 30, 2014 10:40 pm
Re: Turkey TST 2014
This solution is wrong. I didn't see another possibility of the situation (a very common mistake in Combi problems).Ragib Farhat Hasan wrote: ↑Mon Nov 04, 2019 9:32 pmThe problem can be approached by first cutting the board in half; let the upperhalf be called $BROWN$ and the lowerhalf be called $GREEN$.
Now, a pair of brown worms each from the topleft 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$.

 Posts: 62
 Joined: Sun Mar 30, 2014 10:40 pm
Re: Turkey TST 2014
The first step remains the same: cutting the board in half and denoting the upperhalf as $BROWN$ and the lowerhalf as $GREEN$.
Now, two brown worms ($B_1$ and $B_2$) start from the topleft 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 topleft 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$.
Now, two brown worms ($B_1$ and $B_2$) start from the topleft 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 topleft 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$.

 Posts: 62
 Joined: Sun Mar 30, 2014 10:40 pm
Re: Turkey TST 2014
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 straightforward!
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!!!
From there, the rest was quite straightforward!
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!!!

 Posts: 62
 Joined: Sun Mar 30, 2014 10:40 pm
Re: Turkey TST 2014
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!!!
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
Because there is no active member!Ragib Farhat Hasan wrote: ↑Tue Nov 05, 2019 12:57 amBTW, I wonder...
This problem was posted over 5 years ago.
And no one posted a solution to this problem in half a decade!!! WOW!!!