Задача 2.4. Сапёр и лампочка

Сколько всего вариантов

Квадрат $2\times2$ задаётся своей левой верхней клеткой. Она может стоять в одном из $4$ верхних рядов (в пятом ряду квадрату уже не поместиться) и в одном из $8$ левых столбцов. Всего $4\cdot8=32$ положения.

Почему четырёх измерений мало

Каждое измерение делит оставшиеся положения на две группы: при которых лампочка загорится и при которых нет. Какая-то из групп содержит не меньше половины положений — и при неудачном ответе останется именно она.

После первого измерения в худшем случае останется не меньше $16$ положений, после второго — не меньше $8$, после третьего — не меньше $4$, после четвёртого — не меньше $2$. Значит, после четырёх измерений нельзя гарантированно указать мины.

Ключевые клетки

Как это заметить: положений $32=8\cdot4$, поэтому ищем $8$ клеток, каждую из которых накрывают ровно $4$ квадрата. Отметим $8$ ключевых клеток — на пересечении столбцов $2$, $4$, $6$, $8$ и рядов $2$, $4$.

Любой квадрат $2\times2$ накрывает ровно одну из них. Действительно, два соседних столбца — это всегда один чётный и один нечётный, а чётные столбцы как раз $2$, $4$, $6$, $8$. С рядами то же самое: из двух соседних рядов (среди пяти) ровно один — второй или четвёртый.

Пять измерений: ищем ключевую клетку

Сначала найдём ключевую клетку под квадратом — их $8$, хватит трёх измерений.

• Измерение 1: столбцы $2$ и $4$. Горит — ключевой столбец $2$ или $4$, иначе $6$ или $8$.
• Измерение 2: один из двух оставшихся столбцов (например, $2$). Теперь ключевой столбец известен.
• Измерение 3: ряд $2$. Горит — ключевой ряд $2$, иначе $4$.

Выделяем столбцы целиком. Квадрат занимает ровно один чётный столбец, поэтому лампочка горит, только если это один из выделенных. С рядами $2$ и $4$ так же.

Пять измерений: где квадрат вокруг неё

Ключевую клетку накрывают ровно $4$ квадрата: она может быть в любом углу квадрата. Осталось узнать, с какой стороны от неё квадрат.

• Измерение 4: столбец слева от ключевой клетки. Горит — квадрат слева от неё, иначе справа.
• Измерение 5: ряд над ключевой клеткой. Горит — квадрат сверху, иначе снизу.

После пяти измерений положение квадрата известно точно, какими бы ни были ответы.