Let $n$ be a positive integer. We are given a $2n \times 2n$ table. Each cell is coloured with one of $2n^2$ colours such that each colour is used exactly twice. Jana stands in one of the cells. There is a chocolate bar lying in one of the other cells. Jana wishes to reach the cell with the chocolate bar. At each step, she can only move in one of the following two ways. Either she walks to an adjacent cell or she teleports to the other cell with the same colour as her current cell. (Jana can move to an adjacent cell of the same colour by either walking or teleporting.) Determine whether Jana can fulfill her wish, regardless of the initial configuration, if she has to alternate between the two ways of moving and has to start with a teleportation.
Problem
Source: MEMO 2022 T4
Tags: combinatorics
18.09.2022 12:49
Answer: Yes We start with the following claim Claim: Suppose that we have $2n$ consecutive cells, $t\leq 2n$ of which are coloured black. Call a cell good if its neighbors are both black (ore its single neighbor if it's the first or the last cell). If $m$ is the number of good cells then $m\leq t$ Proof: Denote the cells by $a_1,a_2,..,a_{2n}$ from left to the right. Let $i$ be the smallest index such that $a_i$ is not good. If $i$ doesn't exist then all the cells are black so $m=t=2n$, otherwise $a_1,a_2,..,a_{i-1}$ are good and so each of them is coloured black, also for every good cell $a_k,k>i$ its left neighbor is black so $m\leq t $$\blacksquare$ We continue with an other claim Claim: Consider a $2n \times 2n$ table and suppose that $t$ cells are coloured black. Call a cell good if all its neighbors are black. If $m$ is the number of good cells then $m\leq t$. Proof: Let $m_1,m_2$ be the number of good cells on the first and the last row respectively. Wlog assume that $m_1\geq m_2$ Then match every good cell that isn't in the last row with its black neighbor that is exatly below of it. So we have use black cells only from the last $2n-1$ rows to offset every good cell except the $m_2$ ones in the last row. But from the first claim the number of black cells in the first row is $\geq m_1\geq m_2$ and the result follows $\blacksquare$ Note that the proof also shows that if $m=t$ then $m_1=m_2$ . Now back to the our problem. For every cell $a$ call the other cell with the same color its friend. First color white the cell with the chocolate bar as well as its friend. White cells are cells that if Jana reach after a walking then it can wins. Observe that if a cell $a$ is white then every the friends of their neighbors are also white. We are going to show that all the table has to be white. Suppose not, then every non white cell color it black. If $a$ is a black cell then all the neighbors of its friend has to be also black and so we have an injection from the black cell to good cells, but the second claim says that good cells are no more than black and thus $m=t$. From the proof of second claim we see that this can be happen only when every for every black cell not in the first row, the cell above of it is good, and also $m_1=m_2$. There is at least one black cell $x$ , from the above observation we see that all the cells as in the figure 1 have to be also black. This means that at least one cell in the first row is black and so at least one cell in the last row is black, doing the same operation as for the cell $x$ we see that this time all the cells that in a chessboard have the same color as that have to be also black then using the same arguments as in the second claim but swapping the roles of the first and the last row we see easily that all the cells that in a chessboard have the same color as $x$ have to be black. If there exist a cell non from the previous group that is also black then using the same ideas we see that all the table is black which is impossible since we begin coloring two cells white, so all the other cells have to be white. Observe that if $a$ is black then its friend has to be white since $a$ has white neighbors, so in the $2n^2$ black cells every color (of the $2n^2$ colors appears exatly ones and the same for the white cells, but we begin coloring the cell with the chocolate and it's neighbor white so we have a contradiction and the proof is complete.
Attachments:
