Problem

Source: MEMO 2022 T4

Tags: combinatorics



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.