Library / Baltic Way competition problems /33 of 45

Baltic Way competition problems, 2019

Combinatorics Difficulty 6.5 National Olympiad Prove it Baltic Way

Magician puts on the $3 \times 100$ board cards with numbers from $1$ to $300$ in a "snake-like" line so that consecutive numbers are side-to-side adjacent (either horizontally or vertically, not diagonally). The numbers are written on the bottom sides of the cards, the upper sides are empty. After that the magician turns $k$ cards by his choice. For what minimum $k$ can it happen that open cards determine uniquely the whole snake?

Solution

Answer: $k = 2$ .

Example. Put $300$ in the low left corner and $101$ in the cell above it.

Estimation. One open card does not determine the snake uniquely, because all the cells of $3 \times 100$ board can be considered as one cyclic path: let the rows of the board be denoted by letters a, b, c and columns be numbered from $1$ to $300$ , then that path is
$a_1-b_1-c_1-c_2-b_2-b_3-c_3-c_4-b_4-b_5-\dots-c_{300}-b_{300}-a_{300}-a_{299}-a_{298}-\dots-a_2-a_1$
If we open only one card in this path we can orient this path in two ways and put cards such that they increase in the direction of the chosen orientation. So we have at least two configurations here.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.