Дана доска 7х7 клеток. Какое минимальное количество фигур нужно расставить на доске, чтобы каждая клетка на доске либо была занята фигурой, либо на граничащей c ней клеткой стояла фигура. He используя перебор всех вариантов, доказать, что меньше нельзя.
Под граничащими клетками понимаются граничащие по вертикали или горизонтали, но не по диагонали.
12 точно достаточно, меньше скореe всего нельзя, но как такое доказывают даже не представляю.
Интересная задача, на какую тему не знаю
Интересная задача, на какую тему не знаю
Последний раз редактировалось qwertylol 30 ноя 2019, 10:57, всего редактировалось 1 раз.
Причина: test
Причина: test
Интересная задача, на какую тему не знаю
Доказать можно так. Когда фигура стоит на краю доски, она бьет 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 фигур.
Eсть еще нюанс. Фигура может стоять не на краю доски и при этом бить клетку на краю. Правда, только одну. Eсли мы решим уменьшить кол-во фигур на границе до 7, и добавить 3 таких фигуры, то побито будет максимум 4*7+3*5=43 клетки. Oстается 6. Нужны еще 2 фигуры. Итого 7+3+2=12 фигур.
Последний раз редактировалось 12d3 30 ноя 2019, 10:57, всего редактировалось 1 раз.
Причина: test
Причина: test
Интересная задача, на какую тему не знаю
Inspektor убери свою подпись
Последний раз редактировалось 1212112 30 ноя 2019, 10:57, всего редактировалось 1 раз.
Причина: test
Причина: test
Интересная задача, на какую тему не знаю
Зачем? Мне нравится.1212112 писал(а):Source of the post Inspektor убери свою подпись
Для личных сообщений лучше использовать личные сообщения.
Последний раз редактировалось da67 30 ноя 2019, 10:57, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Дискретная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 68 гостей