Let $n$ be a positive integer, and Megavan has a $(3n+1)\times (3n+1)$ board. All squares, except one, are tiled by non-overlapping $1\times 3$ triominoes. In each step, he can choose a triomino that is untouched in the step right before it, and then shift this triomino horizontally or vertically by one square, as long as the triominoes remain non-overlapping after this move. Show that there exist some $k$, such that after $k$ moves Megavan can no longer make any valid moves irregardless of the initial configuration, and find the smallest possible $k$ for each $n$. (Note: While he cannot undo a move immediately before the current step, he may still choose to move a triomino that has already been moved at least two steps before.) Proposed by Ivan Chan Kai Chin
Problem
Source: Own. Malaysian SST 2024 P6
Tags: combinatorics
07.09.2024 17:38
Answer: $\;\boxed{k=n^2+2n}$ Construction: We show the case when $n=3$, [asy][asy] filldraw((0,6)--(1,6)--(1,9)--(0,9)--cycle, red); filldraw((0,3)--(1,3)--(1,6)--(0,6)--cycle, red); filldraw((0,0)--(1,0)--(1,3)--(0,3)--cycle, red); filldraw((3,7)--(4,7)--(4,10)--(3,10)--cycle, red); filldraw((3,4)--(4,4)--(4,7)--(3,7)--cycle, red); filldraw((3,1)--(4,1)--(4,4)--(3,4)--cycle, red); filldraw((6,6)--(7,6)--(7,9)--(6,9)--cycle, red); filldraw((6,3)--(7,3)--(7,6)--(6,6)--cycle, red); filldraw((6,0)--(7,0)--(7,3)--(6,3)--cycle, red); filldraw((9,7)--(10,7)--(10,10)--(9,10)--cycle, red); filldraw((9,4)--(10,4)--(10,7)--(9,7)--cycle, red); filldraw((9,1)--(10,1)--(10,4)--(9,4)--cycle, red); filldraw((1,0)--(4,0)--(4,1)--(1,1)--cycle, red); filldraw((4,9)--(7,9)--(7,10)--(4,10)--cycle, red); filldraw((7,0)--(10,0)--(10,1)--(7,1)--cycle, red); filldraw((1,7)--(2,7)--(2,10)--(1,10)--cycle, lightgrey); filldraw((1,4)--(2,4)--(2,7)--(1,7)--cycle, lightgrey); filldraw((1,4)--(2,4)--(2,1)--(1,1)--cycle, lightgrey); filldraw((2,7)--(3,7)--(3,10)--(2,10)--cycle, lightgrey); filldraw((3,4)--(2,4)--(2,7)--(3,7)--cycle, lightgrey); filldraw((3,4)--(2,4)--(2,1)--(3,1)--cycle, lightgrey); filldraw((4,6)--(5,6)--(5,9)--(4,9)--cycle, lightgrey); filldraw((4,3)--(5,3)--(5,6)--(4,6)--cycle, lightgrey); filldraw((4,3)--(5,3)--(5,0)--(4,0)--cycle, lightgrey); filldraw((5,6)--(6,6)--(6,9)--(5,9)--cycle, lightgrey); filldraw((6,3)--(5,3)--(5,6)--(6,6)--cycle, lightgrey); filldraw((6,3)--(5,3)--(5,0)--(6,0)--cycle, lightgrey); filldraw((7,7)--(8,7)--(8,10)--(7,10)--cycle, lightgrey); filldraw((7,4)--(8,4)--(8,7)--(7,7)--cycle, lightgrey); filldraw((7,4)--(8,4)--(8,1)--(7,1)--cycle, lightgrey); filldraw((8,7)--(9,7)--(9,10)--(8,10)--cycle, lightgrey); filldraw((9,4)--(8,4)--(8,7)--(9,7)--cycle, lightgrey); filldraw((9,4)--(8,4)--(8,1)--(9,1)--cycle, lightgrey); draw((0,9)--(0,10)--(1,10)--(1,9)--cycle); [/asy][/asy] Notice that we can 'snake' the $n^2+2n$ red dominoes resulting in $k=n^2+2n$ moves. Bound: First observe that the coordinates of the vacant square are invariant $\pmod{3}$. Now we claim that a square can never be vacant twice. Assume their was a cycle and consider the smallest such one, with the vacant square moving from cells $c_1,c_2,\dots,c_n$ back to $c_1$. Notice that $n>2$ by the restraints of the problem and we must have $c_i$ and $c_{i+1}$ being $3$ away either vertically or horizontally ($c_{n+1}=c_1$). Thus in this cycle we must have some number of triominoes and $1$ vacant square, but the cycle consists of exactly $3n$ cells, a contradiction. Thus the vacant square can visit once at most $(n+1)^2$ cells so it may not make more than $(n+1)^2-1=n^2+2n$ moves.