, 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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.