At each node of the checkboard $n\times n$ board, a beetle sat. At midnight, each beetle crawled into the center of a cell. It turned out that the distance between any two beetles sitting in the adjacent (along the side) nodes didn't increase. Prove that at least one beetle crawled into the center of a cell at the vertex of which it sat initially. (A. Voidelevich)
Problem
Source: 2019 Belarusian National Olympiad 11.8
Tags: combinatorics, Boards
Pathological
02.09.2019 18:02
This problem's quite funny . First, we will exterminate the beetles. Associate each node with the corresponding cell that the beetle walks to. Place a button on each node, which when stepped on will illuminate the cell it corresponds too. The condition is that any two adjacent nodes are associated with either adjacent cells or the same cell. Define the taxicab distance between a node and a cell as the fewest number of steps you can travel to reach any vertex of the cell from the node. Now, we will consider the following algorithm. Start by placing a robot on an arbitrary node. Repeatedly move the robot so that the taxicab distance between the node and the illuminated cell decreases. Note that in the process of doing so, the illuminated cell may move to an adjacent cell or stay in the same place. The robot will stop only if he is standing on a node which has a taxicab distance of $0$ from the illuminated cell. To solve the problem, it suffices only to show that the robot stops. It is easy to see that the taxicab distance between the robot and the illuminated cell is nonincreasing. We will show that it cannot remain constant for an infinite period of time. This would imply the desired result. Suppose, at any given moment in time, that the entirety of the illuminated cell is to the right and above the robot. In other words, the illuminated cell is in the "first quadrant" w.r.t. the robot. Observe that if the robot eventually switches quadrants after a move, then the taxicab distance will decrease. Otherwise, suppose that the robot never switches quadrants.Then, it must continually move up and to the right. However, since the checkerboard is finite, this is impossible. We've therefore shown that the taxicab distance between the robot and the illuminated cell cannot remain constant and nonzero forever, and therefore must eventually be $0$. $\square$
rafayaashary1
22.06.2020 08:05
A sketch: Partition the board as below (the case of n=4). Extend the obvious map sending blue vertices to green vertices and blue edges to green vertices or edges from the blue square space to the green square space in the obvious way so that it is piecewise linear on each solid blue-livid blue-livid blue triangle. Now apply Brouwer's fixed point theorem, and do some small amount of casework.