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.
Problem
Source: Turkey TST 2014 Day 3 Problem 9
Tags: geometry, combinatorics, TST, combinatorial geometry, Turkey
mavropnevma
12.03.2014 15:56
Some more explanations needed. As stated, any worm - of any colour - can reach any unit square. Should all squares be occupied at the end of the moves? or it only matters if they have been occupied sometimes in the process? Is a worm obliged to make a move at each step, or not? Without answers, the problem is trivial.
emregirgin35
12.03.2014 16:43
mavropnevma wrote: Some more explanations needed. As stated, any worm - of any colour - can reach any unit square. Should all squares be occupied at the end of the moves? or it only matters if they have been occupied sometimes in the process? Is a worm obliged to make a move at each step, or not? Without answers, the problem is trivial. The original post has edited and at least one occupation during the process is sufficient. The quesiton about an obligation does not matter in this form, I think.
MellowMelon
13.03.2014 22:38
1343 worms are needed. Partition the board into 9 sections by drawing two vertical lines separating groups of 671, 672, 671 columns and by drawing two horizontal lines separating groups of 672, 670, 672 rows. Label the sections $\texttt{ABC}$ $\texttt{DEF}$ $\texttt{GHI}$ 672 green worms can cover all of GHEBC. 671 brown worms can cover all of ADEFI. So the whole board is covered. To show this many are needed: consider the intersections of brown worms with each other. Each worm travels to 4027 squares. There's at most one square each brown worm can use on their first and last move, at most two squares each can use on their second and second-to-last move, etc., which means that if there are $b$ brown worms, then they can cover at most $4028b - b^2$ distinct squares for $b \leq 2014$. Similarly, the $g$ green worms can cover at most $4028g - g^2$ distinct squares. Finally, each brown worm and green worm intersects at least once, so we overcount by $bg$. Therefore, with $b$ brown worms and $g$ green worms, the total number of distinct squares covered is at most \[ 4028b + 4028g - b^2 - bg - g^2. \] Suppose $b+g \leq 1342$. For fixed $b+g$, $b^2+bg+g^2$ is minimized with $b = g$, so we may assume $b \leq 671, g \leq 671$. But \[ 2 \cdot 4028 \cdot 671 - 3 \cdot 671^2 < 2014^2, \] (this is equivalent to $3 \cdot 671 < 2014$ after some factoring) so 1342 is not enough.
SMOJ
14.03.2014 09:39
Wow, absolutely fascinating problem, but how do you prove that each brown intersect green at least once? EDIT: Eh, I did not know what I was thinking
emregirgin35
14.03.2014 14:18
SMOJ wrote: Wow, absolutely fascinating problem, but how do you prove that each brown intersect green at least once? WLOG, assume that all brown worms ended up at the bottom-right corner, and all green worms ended up at the top-right corner. They can go there from any square, and getting there does not make them occupy less square. So, we have two paths from the top-left to the bottom-right and from bottom-left to the top-right. Clearly, they must intersect.
tngkrtkdydwk
30.03.2014 13:45
MellowMelon wrote: Finally, each brown worm and green worm intersects at least once, so we overcount by $bg$. But what if a lot of brown worms and green worms intersect at a single square?
emregirgin35
30.03.2014 17:11
tngkrtkdydwk wrote: MellowMelon wrote: Finally, each brown worm and green worm intersects at least once, so we overcount by $bg$. But what if a lot of brown worms and green worms intersect at a single square? Then we overcount that single square as much as the worms passed on it.
JuanOrtiz
21.04.2014 21:45
I'll solve it for any $n$ (the problem asks you for $n=2014$). The answer is
$\displaystyle\lceil \frac{2n}{3} \displaystyle\rceil$
worms are needed.
From small cases $n=1,2,3,4,5,6$, one can see the answer should be $\textless n$. Also, since each worm's path covers at most $2n-1$ squares, one can see one needs at least $\frac{n^2}{2n-1}$ worms, which is approximately $\frac{n}{2}$. But this doesn't take into account path intersections. So the answer should be $\textgreater \frac{n}{2}$. From this, and from the small cases $n=1,2,3,4,5,6$, one can hypothesize that the answer is approximately $\frac{2n}{3}$
Now let's solve the problem.
For convenience, say the answer is $f(n)$. Now, it is easy to see we can add a worm that goes around the border of the board, and so $f(n) \le f(n-1)+1$. So if we prove $f(3m)=2m$, then we'll have $f(n) \le\lceil \frac{2n}{3} \rceil$ , since
$\lceil \frac{3m+2}{3} \rceil = \lceil \frac{3m+1}{3} \rceil + 1 = \lceil \frac{3m}{3} \rceil +2$.
For $m=1$, the paths are $(1,1) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (3,2) \rightarrow (3,3)$ and $(1,3) \rightarrow (2,3) \rightarrow \rightarrow (2,2) \rightarrow (2,1) \rightarrow (3,1)$ picturewhich forms kind of a Nazi symbol.
For greater $m$, the paths are similar. Divide the board into $9$ $m \times m$ little boards, and imagine the paths for $m=1$ going through the little boards. Replicate them $m$ times. For example, for $m=2$, the paths are
$(1,1) \Rightarrow (1,4) \Rightarrow (5,4) \Rightarrow (5,6)$
$(2,1) \Rightarrow (2,3) \Rightarrow (6,3) \Rightarrow (6,6)$
$(1,6) \Rightarrow (4,6) \Rightarrow (4,2) \Rightarrow (6,2)$
$(1,5) \Rightarrow (3,5) \Rightarrow (3,1) \Rightarrow (6,1)$
(notice the paths should start at the corner squares, but it's fine if they don't, since we can just connect the path to the corner square. The way I wrote it is much more visual, I wish I could draw a picture).
So we indeed have $f(n) \le\lceil \frac{2n}{3} \rceil$.
Imagine the green paths, say there are $V$ green paths. WLOG they go from the bottom left corner to the upper right corner. Now, I will define new and improved green paths, which I will call "greener" paths, as follows. Draw all the green paths. The first greener path will follow the "top" lines. The second greener path will follow the "top" lines that aren't in the first greener path. And so on... It is easy to see there will be $V$ greener paths. Basically, the first path is above the second one, that is above the third one, and so on. Also, these new paths also go from corner to corner.
Now, if the first and second paths intersect, modify the second path to go one square below the first path in this area, so that they do not intersect. Repeat this with the 2º and 3º paths, then with the 3º and 4º paths, etcetera. It is easy to see they will cover the squares that were covered by the original green paths, plus maybe some other squares. Also, two green paths will intersect only in the edge of the board. Finally, erase the "tail" and the "head" of the green paths that intersect with other green paths. When erasing tails, erase the tails of the lowest paths first, and when erasing heads, erase the heads of the paths that are most above first. So we have modified the green paths to not intersect each other, be one "above" the other, and they cover the squares the original green paths covered. Also, each path goes from the bottom edge of the board to the upper edge of the board.
This is important: it is easy to see that we must have erased at least $V(V-1)$ squares when we erased tails and heads. This is because, if from some path we erased $\textless V-1$ squares, then there cannot be another $V-1$ paths that go from edge to edge and that do not intersect this path (because there are at most $V-2$ squares to the left of the tail or to the right of the head).
Do the same to the red paths. In total there are $R$ red paths.
We have
$n^2 \le (2n-1)(R+V)-R(R-1)-V(V-1)-RV$
counting the number of squares that are covered by paths, and subtracting the number of red-green intersections (also subtracting the number of head-tail squares we erased) . Each red path and each green path must intersect (because they go from edge to edge), and each intersection must be different since no two same-color paths intersect.
Now let's do some simple computations, where $X=R+V$ is the number of worms.
I hid the computations because they look ugly$n^2 \le (2n-1)(R+V)-R(R-1)-V(V-1)-RV$
$n^2 \le (2n-1)(R+V)-(R^2+V^2+2RV)+(RV+R+V)$
$n^2 \le (2n)X-X^2+RV \le 2nX-X^2+\frac{X^2}{4}$
$\frac{3}{4}X^2 -2nX+n^2 \le 0$
And by the quadratic law we get
$\frac{2n}{3} \le X \le 2n$.
Therefore
$f(n) = X \ge \frac{2n}{3}$
so we are done!
$1343$
.
toto1234567890
14.07.2014 15:33
I think all of you have to fix it a little bit. If a lot of green and red insects intersect at a single square the intersection square of the qreen and red insectsare very less and it becomes harder
toto1234567890
14.07.2014 15:37
So you have to fix the path of the insects so you can use your idea.
Particle
30.09.2014 15:33
Suppose we have a $n\times n$ chessboard and there are $a$ brown worms and $b$ green worms. Label a square $s_i$ for a worm if it can reach there after $i$ moves from the starting square. Similarly label a square $e_i$ for a worm if it can reach the ending square after $i$ moves from it.
Each worm's path consists of $2n-1$ squares. So all the worms have crossed total $(2n-1)(a+b)$ squares. Note that for brown worms and $i<a$, there are $i$ $s_i$s. But when we counted each individual worms' path, we counted $a$ of them. So we have overcounted $a-i$ squares. Similarly for $e_i$s, $i<a$, we have overcounted more $a-i$ squares. Thus the number of overcounted squares resulted from brown worms' overlapping paths is at least $\sum_{i<a} 2(a-i)=a(a-1)$. And for green worms' overlapping paths, the number of overcounted squares is at least $b(b-1)$. Similarly, each brown and green worms have overlapped their paths at least once. Thus we overcounted at least $ab$ more squares. Hence \[(2n-1)(a+b)\ge n^2+a(a-1)+b(b-1)+ab\]Assuming $a+b=x$, it can be rewritten as $ab\ge (n-x)^2$. Hence $x^2\ge 4ab\ge 4(n-x)^2\implies x\ge \frac 2 3 n$.
So $x\ge \left \lceil \frac {2n} 3\right\rceil$. It is also easy to construct an example for $x=\left \lceil \frac {2n} 3\right\rceil$ (Just like people did in earlier posts.) So the minimal number of worms is $\left \lceil \frac {2n} 3\right\rceil$
toto1234567890
22.11.2014 16:22
You are right @ tnkgkrtkdydwk You guys have to fix. The overcounting of squares may not be at least ab squares. So You have to make it work. Hint: You can make the paths of the worms not to coincide and occupy more than before. It's very necessary. Otherwise you'll get a 0 point for this.
dgrozev
03.06.2021 10:56
All the solutions above have the following flaw. They introduced the sets $B$ and $G$ of the cells covered by brown and green worms correspondingly. Then somehow they postulated that $|B\cap G|\ge b\cdot g,$ where $b$ resp. $g$ is the number of brown, resp. green worms. The reason given was: because each brown route crosses each green one. Of course, it's not enough. Imagine all trajectories have only one common point. What happened was the users had in mind the optimal configuration, where really $|B\cap G|= b\cdot g$ but in this configuration there are no tree routes that intersect at one point. This argument could hardly be fixed. Apparently some new idea needs to come into play. https://dgrozev.wordpress.com/2021/06/02/kangaroos-jumping-on-a-chessboard-italian-training-camp/ One may see also this Italian IMO 2015 test for a similar mistake.
HamstPan38825
29.01.2024 23:24
My original solution had the same flaw as everyone else's, so here's my writeup of a solution along the same lines as @dgrozev's. The answer is $\lceil 2n/3 \rceil$ worms. Construction: We essentially draw a swastika. Let the $i$th green worm move $i-1$ squares up, $k-i$ squares right, $k$ squares up, $n-k$ squares right, then up to the top of the board; do the same symmetrically for the $\ell$ red worms. There obviously exists such a construction with $k+\ell = \lceil 2n/3 \rceil$ (this is particularly easy to see when $3 \mid n$). Bound: Suppose there are $k$ green worms and $\ell$ red worms. The idea is to consider the chessboard instead as a one-dimensional column, and let the horizontal dimension represent time. (Of course, this is not completely analogous: we will have worms in a superposition at any given time.) The position of any worm at any given time is given by the set of squares that worm occupies in the column that corresponds to that time. In particular, we may assume that the worms begin in distinct positions at $t=0$ (as they must cover all the squares in that column). Now, at every point in time, we may assume that the worms stay in their current position in the column at the beginning of that second and assume positions during that second. In particular, a total of $n-k-\ell$ new positions must be assumed every second. [This definition is quite subtle; notice that if the worm moves in a horizontal line in the chessboard, i.e. it does not change its position in the next round, it does not assume any new position.] However, by assumption, each green worm can only assume $n-k$ new positions, and each red worm can only assume $n-\ell$ positions because worms cannot move in the reverse direction. Furthermore, there are $k\ell$ occurrences where a red and green worm occupy the same position. Hence we have the inequality $$k(n-k) + \ell(n-\ell) \geq n(n-k-\ell) + k\ell$$which yields $k+\ell \geq 2n/3$, as needed.