Turkey TST 2014
- Phlembac Adib Hasan
- Posts:1016
- Joined:Tue Nov 22, 2011 7:49 pm
- Location:127.0.0.1
- Contact:
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
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 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$.
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$.
-
- 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 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$.
-
- 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 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$.
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$.
-
- 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 straight-forward!
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 straight-forward!
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!!!
-
- 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!!!