Я все-таки вернусь к задаче про доску 10x10, на которой надо расставить крестики в меньше, чем половине клеток, так чтобы в каждом квадрате 3x3 было большинство клеток с крестиками.
Пока не забыл - ЗНАЕТЕ ЛИ ВЫ, ОТКУДА ЭТА ЗАДАЧА? Я увидел ее где-то то ли в фейсбуке, то ли в телеграме с неделю назад, но забыл, где, и не могу найти. Кажется, какая-то школьная олимпиада, но не уверен. Киньте ссылку, если видели первоисточник, пожалуйста.
Как я написал, LLMы теперь могут решить задачу за вас, но мне очень понравилось красивое "принципиальное" решение, которое привел Никита Гладков в комментариях в телеграме, и я перескажу его здесь. Заодно мы посчитаем число разных решений.
Итак, вопреки интуиции, это можно сделать, и вот как легко это увидеть. Заполним все клетки доски цифрами от 1 до 9, так, чтобы левый верхний квадратик 3x3 был заполнен по порядку, а потом скопирован 9 раз вправо и вниз. См. первую картинку.
Теперь важно понять, что в любом квадрате 3x3 - например, обведенном красным цветом на картинке - встречаются ровно по одной все цифры от 1 до 9. Это значит, что если мы поставим крестики, скажем, "на все пятерки", "на все шестерки" и так далее на все клетки с ПЯТЬЮ разными цифрами, то в любом квадрате 3x3 будет пять крестиков - именно эти пять цифр!
Но можно ли это сделать? Легко подсчитать, что четыре цифры встречаются в квадрате 9 раз - для примера все пятерки обведены кругами; кроме 5 это еще цифры 6,8,9. Четыре цифры встречаются по 12 раз: это 2,3,4,7. И одна цифра встречается 16 раз: это 1. Итого видим, что если мы заполним крестиками все цифры "по 9 раз" и одну "12 раз", всего потратим 9*4+12=48 крестиков и гарантируем пять крестиков в любом квадрате 3x3, что и требовалось доказать. Красиво!
Теперь докажем, что меньшим количеством не обойтись. На второй картинке мы видим шесть зеленых квадратов 3x3 и шесть красных. Они пересекаются в трех квадратах 2x2, которые содержат 12 клеток. В каждом зеленом квадрате обязано быть минимум 5 крестиков, итого 30, и в шести красных тоже 30, вместе 60. Но если какие-то крестики попали в пересечения, то мы их посчитали дважды - таких максимум 12, поэтому из 60 мы можем сэкономить максимум 12 и остается 48. Меньше невозможно. Красиво!
Далее, по этой же картинке мы видим, что в любом решении с 48 клетками все 12 клеток-пересечений обязаны быть с крестиками. Это как раз клетки классов "по 9 раз", цифры 5,6,8,9 с первой картинки. Это не все 9 такие цифр, но на третьей картинке квадраты расположены по-другому, другие клетки пересечения, и видно, что если эту картинку покрутить, то все 9 расположений этих цифр попадают в "обязательные пересечения". Поэтому в любом решении из 48 клеток 36 обязаны полностью закрыть все классы цифр по 9 штук. И наоборот, все белые клетки обязаны быть свободными от крестиков - а это именно все цифры 1.