Закрасьте наименьшее число клеток доски...

[Ktina]

Закрасьте наименьшее число клеток доски $5\times 5$ в чёрный цвет так, чтобы любой прямоугольник, состоящий из четырёх клеток этой доски, содержал бы чёрную клетку.

[TOTAL]

$a_1, d_4, c_2,e_2,b_3,b_5$

[Ktina]

TOTAL
Большое спасибо!

Меньше 6, разумеется, нельзя, так как вся доска разбивается на 6 прям-ков из 4 клеток и ещё одну клетку.

-- 23.05.2019, 09:10 --

Нет, стоп!
Тогда прям-к в нижнем ряду остаётся без чёрной клетки!

[TOTAL]

Ktina в сообщении #1394698 писал(а):

Нет, стоп!

Я прямоугольник $1$ на $5$ считал состоящим из $4$ клеток!

[GAA]

$a_4$, $b_1$, $b_5$, $c_3$, $d_2$, $e_4$.

Какая математика может быть использована для получения ответа в этой головоломке?
Есть ли достаточно простые усложнения головоломки, в которых без математики ответ на головоломку дать не получится (затруднительно), а математика поможет?

[gris]

Подобную задачу мы решали на уроках на поле $10\times10$
Мне помнится, что Перельман (не тополог) даже изучал выигрышные стратегии.

[GAA]

GAA в сообщении #1394709 писал(а):

$a_4$, $b_1$, $b_5$, $c_3$, $d_2$, $e_4$.

Посмотрел формулировку. В ней указано, что "Квадрат тоже считается прямоугольником.". В моём варианте это не было учтено (учитывались только прямоугольники с длиной меньшей стороны в 1 клетку).

Если учитывать и квадраты 2x2, то 7 ячеек очевидно закрасить достаточно: $a_3$, $a_5$, $b_1$, $c_3$, $c_5$, $d_2$, $e_4$.

Upd. исправил опечатку $a_1$ на $a_3$, но решение после проверки оказалось неправильным. :( Пойду проверять.

Upd 2. Лучше (меньше) 8 клеток вроде не получается у меня.

[worm2]

GAA в сообщении #1394709 писал(а):

Какая математика может быть использована для получения ответа в этой головоломке?

Minimum hitting set
UPD: нашёл русскоязычную формулировку: http://discopal.ispras.ru/Minimum_Hitting_Set

[daniel starodubtsev]

$a_3, b_1, b_4, c_2, d_3, d_5, e_2$

[GAA]

gris, worm2, спасибо! Если будет что-то ближе к теме, то очень буду рад ссылкам. (Это мне для сына надо. Мне можно и совсем простые книги рекомендовать; для маленьких.)

daniel starodubtsev, я эту комбинацию при беглом переборе пропустил, спасибо!

[waxtep]

Симметричный и несимметричный варианты:

$$\begin{tabular}{|c|c|c|c|c|} \hline &&&\bullet&\\ \hline &\bullet&&&\bullet\\ \hline &&\bullet&&\\ \hline \bullet&&&\bullet&\\ \hline &\bullet&&&\\ \hline \end{tabular}\qquad \begin{tabular}{|c|c|c|c|c|} \hline &&&\bullet&\\ \hline \bullet&&\bullet&&\\ \hline &\bullet&&&\bullet\\ \hline &&&\bullet&\\ \hline &\bullet&&&\\ \hline \end{tabular}