Поиск сокровища

[EUgeneUS]

PETIKANTROP в сообщении #1626711 писал(а):

5

Да.
Там по забавной причине не достигается теоретический минимум в четыре хода для фигур из 10 клеток.

PETIKANTROP в сообщении #1626711 писал(а):

В пятидесяти процентах случаев можно за 4

Вообще говоря, только в одном случае из 10 требуется 5 ходов, в остальных - меньше.

[PETIKANTROP]

EUgeneUS
5 это ответ venco

Я рассуждала так.
Где бы ни был клад, вскрывать надо центральную клетку любого из крестов. Если обнаружился флажок, то минимизировать количество ходов можно вскрытием клетки соседнего креста по диагонали от флажка.

[EUgeneUS]

Кстати, как-то выпал вопрос доказательства, что 10 ходов за квадрата $6 \times 6$ - это минимальное количество.

[venco]

Вряд ли это можно доказать не перебором.

[Dmitriy40]

Ну уж точно не меньше $\lceil36/5\rceil=8$.
8 крестов покрывают не более 40 клеток, т.е. не более четырём можно разрешить вылезти за пределы поля или перекрываться внутри. Сомневаюсь что такое замощение крестами существует. Думаю несложно прикинуть сколько полей вылезет за границы поля при любом размещении крестов и получится что 8 крестов недостаточно. Вариантов замощения плоскости крестами вроде немного.
Останется вопрос с 9.

[EUgeneUS]

venco

У меня были некоторые построения, из которых следовало, что для любой фигуры из 36 клеток нужно не менее 10 ходов.
Но... Удалось построить фигуру из 11 клеток, которую можно проверить за 4 хода, и это сломало эти построения.

-- 21.01.2024, 20:40 --

Dmitriy40
С крестами там такой нюанс. Открыв флажок, скажем в последнем кресте, нужно ещё четыре хода, чтобы "пробить" весь крест.
Поэтому последние ходы должны проверять не более чем (перечисление с конца) - $1, 2, 3, 4$ клетки.

На этом были основаны мои построения.
Есть последовательность $1, 2, 3, 4, 5, ... 5 ...$, сколько нужно взять первых слагаемых из этой последовательности, чтобы получить число большее или равное числу клеток - столько ходов минимально и нужно.
Но, как писал выше, есть фигура из 11 клеток, которая проверяется за 4 хода, а это ломает эту оценку.