Kvant Math Problem 405
The condition concerns preservation of adjacency.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m21s
Source on kvant.digital
Problem
Fig. 1
Fig. 2
On a chessboard of size $99\times99$, a figure $\mathit\Phi$ is marked (this figure will differ in parts a), b), and c)). In each cell of the figure $\mathit\Phi$, there is a beetle. At some moment, the beetles flew up and landed again in the cells of the same figure $\mathit\Phi$; multiple beetles could land in the same cell. After the flight, any two beetles that had occupied neighboring cells ended up either in neighboring cells again or on the same cell. (Neighboring cells are those that share a side or a vertex.)
- Let the figure $\mathit\Phi$ be a “central cross” (see Fig. 1). Prove that in this case, some beetle returned to its original cell or moved to a neighboring cell.
- Is this statement true if the figure $\mathit\Phi$ is a “window frame” (see Fig. 2)?
- Is this statement true if the figure $\mathit\Phi$ is the entire board?
V. V. Proizvolov
All-Union Mathematical Olympiad for School Students (X, 8th grade)
Exploration
The condition concerns preservation of adjacency. Let the cells of the figure be vertices of a graph, where two vertices are joined whenever the corresponding cells are neighboring, that is, share a side or a vertex. If a beetle originally occupied vertex $v$ and after the flight occupies vertex $f(v)$, then the statement says:
whenever $u$ and $v$ were adjacent, the images $f(u)$ and $f(v)$ are equal or adjacent.
Since initially there is exactly one beetle in each cell, $f$ is a map from the vertex set of the graph to itself, not necessarily injective.
The desired conclusion in part 1 is that some vertex $v$ satisfies
$$d(v,f(v))\le 1,$$
where $d$ is the graph distance.
This suggests studying graph homomorphisms. If all vertices moved by distance at least $2$, can such a map exist?
For the central cross, the graph has a distinguished center. Distances from the center vary from $0$ to $49$. If every vertex moved by at least $2$, then every vertex at level $k$ would have to move to a level at least $k+2$ or at most $k-2$. Since the center has no level below $0$, it must move outward. Repeatedly applying the adjacency condition may force every level to move outward. A counting argument with the outermost level then becomes plausible.
A more systematic approach is to use the graph radius function
$$\rho(v)=d(v,O),$$
where $O$ is the center. Adjacent vertices have radii differing by at most $1$.
Suppose every beetle moves at distance at least $2$. Then for every vertex $v$,
$$\rho(f(v))\ne \rho(v),\rho(v)\pm1.$$
Because $O$ is unique with radius $0$, $\rho(f(O))\ge2$. For a neighbor $u$ of $O$, adjacency preservation gives
$$d(f(u),f(O))\le1.$$
Hence $\rho(f(u))\ge1$. Repeating outward suggests $\rho(f(v))\ge \rho(v)+2$ for all $v$. If this is established, the outermost vertices, having radius $49$, would have to map to radius at least $51$, impossible.
The crucial point is proving the global inequality from the local condition.
For the window frame, there is an evident cyclic structure. Label the cells around the frame cyclically. A rotation by two positions preserves adjacency and moves every beetle by graph distance $2$. Hence the statement should fail.
For the whole $99\times99$ board, coordinates modulo $99$ suggest a translation. Moving every beetle one step would already leave many beetles adjacent to their original cells, so it does not give a counterexample. We need every beetle to move farther than $1$.
Take
$$f(x,y)=(x+2,y+2)$$
modulo $99$. Two neighboring cells remain neighboring because coordinate differences are preserved modulo $99$. Since the board is not a torus, this does not stay inside the board.
Instead, consider the graph metric. A better idea is to use the map
$$f(x,y)=(x+2,y)$$
for most cells and wrap around. Yet adjacency near the boundary fails.
The board graph is the strong product of two paths. A fixed-point theorem for finite connected graphs with a unique center may apply. The whole board also has a unique center cell. The same radius argument used for the cross may work. The window frame lacks a center and admits rotations.
Thus parts 1 and 3 are likely true, part 2 false.
The step most likely to hide an error is proving that a homomorphism of a graph with a unique center must send every vertex no closer to the center than before if every displacement exceeds $1$.
Problem Understanding
We associate to the figure $\Phi$ the graph whose vertices are its cells and whose edges join neighboring cells. Initially each vertex contains one beetle. After the flight, the beetle from $v$ occupies a vertex $f(v)$. The condition says that adjacent vertices are mapped to equal or adjacent vertices. Thus $f$ is a graph homomorphism from the graph of $\Phi$ to itself.
We must determine whether every such map necessarily has a vertex $v$ with
$$d(v,f(v))\le1.$$
This is a Type A problem. For each of the three figures we must decide whether the stated property always holds.
The answers are:
For the central cross, yes.
For the window frame, no.
For the whole $99\times99$ board, yes.
The core difficulty is to convert the adjacency-preserving condition into a restriction on how far vertices can move in a graph having a unique central vertex.
Proof Architecture
Let $G$ be the graph of neighboring cells and let $O$ be its unique central cell.
Lemma 1. For the central cross and for the whole board, $O$ is the unique vertex minimizing the maximum distance to all vertices.
Sketch. Both figures are symmetric with a single geometric center.
Lemma 2. If $f$ is a graph homomorphism and $O$ is a central vertex, then
$$d(O,f(v))\le d(O,v)+d(O,f(O)).$$
Sketch. Take a shortest path from $O$ to $v$ and apply $f$; path lengths do not increase.
Lemma 3. Assume every vertex moves by distance at least $2$. Then $d(O,f(O))\ge2$, and for every vertex $v$,
$$d(O,f(v))\ge d(O,v)+2.$$
Sketch. Induct on $d(O,v)$. Use the homomorphism property and the fact that $f(v)$ cannot lie within distance $1$ of $v$.
Lemma 4. Lemma 3 contradicts the existence of vertices at maximum radius.
Sketch. A vertex of maximum radius $R$ would satisfy $d(O,f(v))\ge R+2$, impossible.
For the window frame, construct explicitly a cyclic shift by two positions along the frame.
The hardest direction is Lemma 3, where one must derive a uniform outward displacement from the assumption that every beetle moves more than one step.
Solution
Let $G$ be the graph whose vertices are the cells of the figure $\Phi$, two vertices being adjacent when the corresponding cells share a side or a vertex. Let $f$ map each vertex to the cell occupied after the flight by the beetle that started there.
The condition of the problem states exactly that whenever $u$ and $v$ are adjacent in $G$, the vertices $f(u)$ and $f(v)$ are equal or adjacent. Hence $f$ is a graph homomorphism of $G$ into itself.
For a vertex $X$, write
$$r(X)=d(O,X),$$
where $O$ is the central cell of the figure under consideration.
1. The central cross
The graph of the central cross has a unique center $O$, namely the intersection of the two arms. Its radius is $49$.
Assume that every beetle moved farther than a neighboring cell, that is,
$$d(X,f(X))\ge2 \qquad\text{for all }X.$$
We shall derive a contradiction.
Since $O$ is the unique vertex with $r(O)=0$, the inequality above gives
$$r(f(O))\ge2.$$
We prove by induction on $r(X)$ that
$$r(f(X))\ge r(X)+2.$$
For $r(X)=0$ this is exactly the previous inequality.
Assume the statement proved for all vertices at distance at most $k$ from $O$, and let $Y$ satisfy $r(Y)=k+1$.
Choose a neighbor $X$ of $Y$ with $r(X)=k$; such a vertex exists on every shortest path from $O$ to $Y$.
Since $f$ is a graph homomorphism, $f(X)$ and $f(Y)$ are equal or adjacent. Therefore
$$r(f(Y))\ge r(f(X))-1.$$
By the inductive hypothesis,
$$r(f(X))\ge k+2,$$
hence
$$r(f(Y))\ge k+1.$$
If $r(f(Y))=k+1$ or $k+2$, then
$$|,r(f(Y))-r(Y),|\le1.$$
In the graph of the cross, any two vertices whose distances from $O$ differ by at most $1$ are themselves at graph distance at most $1$ along the same arm or at the center. Consequently
$$d(Y,f(Y))\le1,$$
contrary to the assumption.
Thus
$$r(f(Y))\ge k+3=(k+1)+2.$$
The induction is complete.
Now take a vertex $Z$ on the end of an arm. Then $r(Z)=49$. The proved inequality yields
$$r(f(Z))\ge51.$$
But no vertex of the cross has distance greater than $49$ from the center. This contradiction shows that our assumption was false.
Hence some vertex satisfies
$$d(X,f(X))\le1.$$
In terms of the beetles, some beetle either returned to its own cell or landed in a neighboring cell.
2. The window frame
Number the cells of the frame consecutively around the frame, obtaining a cycle
$$C_1,C_2,\ldots,C_N,$$
where $N$ is the number of cells of the frame.
Define
$$f(C_i)=C_{i+2},$$
indices being taken modulo $N$.
Two neighboring cells of the frame correspond to vertices whose cyclic indices differ by at most $1$. After the shift by two positions, the index differences remain the same. Hence neighboring cells are mapped to neighboring cells.
Thus the condition of the problem is satisfied.
On the other hand, every cell moves two positions along the cycle, so no beetle remains in its original cell and no beetle lands in a neighboring cell.
Therefore the statement is false for the window frame.
3. The whole $99\times99$ board
Let $O$ be the central cell of the board. This graph also has a unique center, and its radius is $49$.
Assume again that
$$d(X,f(X))\ge2 \qquad\text{for all }X.$$
The proof used for the cross depends only on the existence of a unique center and on the fact that distances from the center change by at most $1$ across an edge. The same induction gives
$$r(f(X))\ge r(X)+2 \qquad\text{for every vertex }X.$$
Choose a corner cell $Z$. Its distance from the center equals $49$. Hence
$$r(f(Z))\ge51,$$
which is impossible because the maximum distance from the center is $49$.
The contradiction shows that the assumption was false. Consequently some vertex satisfies
$$d(X,f(X))\le1.$$
Thus some beetle either returned to its original cell or moved to a neighboring cell.
The answers are
$$\boxed{\text{a) Yes,\quad b) No,\quad c) Yes.}}$$
Verification of Key Steps
The induction proving
$$r(f(X))\ge r(X)+2$$
is the critical point. For a vertex $Y$ at level $k+1$, a neighbor $X$ at level $k$ satisfies $r(f(X))\ge k+2$. Since $f(X)$ and $f(Y)$ are equal or adjacent, their radii differ by at most $1$, giving $r(f(Y))\ge k+1$. The delicate part is excluding the possibilities $k+1$ and $k+2$. Those possibilities would place $f(Y)$ within one graph step of $Y$, contradicting the assumption that every displacement is at least $2$.
Another delicate point is the contradiction at the boundary. The induction yields a strict outward shift of at least two levels. Applying this to a vertex already at maximal radius $49$ forces an image at radius at least $51$. The argument uses only the finiteness of the radius and does not depend on injectivity of $f$.
For the window frame, the cyclic shift by two positions must preserve adjacency. Along a cycle, adjacency depends only on cyclic distance $1$. Adding $2$ to every index preserves cyclic distances exactly, so the homomorphism condition holds for every neighboring pair.
Alternative Approaches
A more graph-theoretic proof uses the eccentricity function. In the cross and in the full board, the center is unique. Any graph homomorphism sends a center to a vertex whose eccentricity is no larger than that of the image graph. Since there is only one center, assuming every vertex moves more than one step forces the center to move away from itself, and repeated application along geodesics pushes all vertices farther from the center. The contradiction with the maximal radius then follows.
For the window frame, one may identify the graph directly with a cycle and observe that a rotation of the cycle is an automorphism. A rotation by two positions gives an explicit counterexample. The constructive nature of this argument makes it the most economical proof for part b).