In a checkered square, there is a closed door between any two cells adjacent by side. A beetle starts from some cell and travels through cells, passing through doors; she opens a closed door in the direction she is moving and leaves that door open. Through an open door, the beetle can only pass in the direction the door is opened. Prove that if at any moment the beetle wants to return to the starting cell, it is possible for her to do that.
Problem
Source: 44th International Tournament of Towns, Senior A-Level P4, Fall 2022
Tags: board, combinatorics, Tournament of Towns
sn6dh
06.03.2023 05:47
Let's prove it by contradiction, and suppose at some moment, the beetle can't return to the starting cell anymore.
Let $S$ denote the set of cells that the beetle can go to at this moment. For any adjacent $a\in S, b\in S^c$, since the beetle can go to $a$ but not $b$, the door should be open and the direction the door is open is from $b$ to $a$.
$\Rightarrow$ no door is open in the direction from $S$ to $S^c$. That is, the beetle goes from $S^c$ to $S$ for only one time any never leaves $S$.
$\Rightarrow$ the beetle can only open one door between $S$ and $S^c$, but the number of doors between them $>1$.
$\therefore$ some doors between $S$ and $S^c$ are closed, contradiction, and this finished the proof.
ReaperGod
06.03.2023 06:08
isnt it possible for the beetle to be trapped at some moment or am i being really dumb edit - nvm im being dumb is it possible for the beetle to close any doors?
math_comb01
28.03.2023 21:04
If at a moment beetle wants to go where she started then beetled should go to a square on the diagonal of the checkered square then she can use diagonal symmetry by doing the moves she had done before by reflecting them along the diagonal