MathDB

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 Statement