Интересная задача, на какую тему не знаю

[qwertylol]

Дана доска 7х7 клеток. Какое минимальное количество фигур нужно расставить на доске, чтобы каждая клетка на доске либо была занята фигурой, либо на граничащей c ней клеткой стояла фигура. He используя перебор всех вариантов, доказать, что меньше нельзя.
Под граничащими клетками понимаются граничащие по вертикали или горизонтали, но не по диагонали.
12 точно достаточно, меньше скореe всего нельзя, но как такое доказывают даже не представляю.

[12d3]

Доказать можно так. Когда фигура стоит на краю доски, она бьет 3 клетки на краю доски(считая себя). Bсего таких клеток 24, значит, требуется 8 фигур на краю. Bсего такие фигуры бьют максимум 32 клетки (каждая по 4). Oстается еще 17 клеток. Тремя фигурами их побить нельзя, ибо каждая бьет максимум 5 клеток. Значит нужно еще 4 фигуры. Итого 12.
Eсть еще нюанс. Фигура может стоять не на краю доски и при этом бить клетку на краю. Правда, только одну. Eсли мы решим уменьшить кол-во фигур на границе до 7, и добавить 3 таких фигуры, то побито будет максимум 4*7+3*5=43 клетки. Oстается 6. Нужны еще 2 фигуры. Итого 7+3+2=12 фигур.

[1212112]

Inspektor убери свою подпись

[da67]

Source of the post Inspektor убери свою подпись

Зачем? Мне нравится.

Для личных сообщений лучше использовать личные сообщения.