Turkey TST 2014

[Phlembac Adib Hasan]

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

[*Mahi*]

Hint:
${\color{White} {\text{Minimize the intersections, and you've minimized the number of worms} } }$

[Ragib Farhat Hasan]

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]

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).

[Ragib Farhat Hasan]

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]

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!!!

[Ragib Farhat Hasan]

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]

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!