задачка про доску

[avva]

Понравилось мучиться над этой задачкой. Может, и вам понравится?

Можно ли пометить крестиками меньше половины клеток на доске 10x10, так, чтобы в любом квадрате 3x3 больше половины клеток были с крестиками?

Скажу, потому что это не спойлер, что в процессе решения я больше одного раз менял мнение о том, каков ответ.

Если же вы не хотите мучить себя и решать, можете спросить любую соседскую модель, и она вам все расскажет. Только не надо в комментарии кидать ответы от моделей, пожалуйста.

(Как изменился мир всего за год - еще год назад, когда я помещал какую-то математическую задачку, то писал в духе "если не будет решений, запощу правильное завтра". Больше уже никогда не будет смысла это делать, любая задача, не требующая специализированной математики, доступна моделям, и любой может за 10 секунд получить решение)

(все посты теперь ИИ-посты, такое время наступило)

Comments

[epimorphisms_split]

А в квадрате 6х6 нельзя.

[kobak]

О! Неожиданно.

А для каких размеров можно, а для каких нельзя? Наверное, зависит от mod 3?

[epimorphisms_split]

Очевидно, для размеров делящихся на 3 нельзя, потому что их можно поделить на неперекрывающиеся квадраты 3х3, в каждом из которых должно быть помечено больше половины клеток. Кажется, для всех остальных можно, но это неочевидно.

[tropicalizator]

Для больших n ответ - нельзя. Поделим с остатком: n=3q+r. Верхний левый квадрат 3q на 3q разбивается на q^2 непересекающихся квадратов 3х3. В каждом должно быть хотя бы 5 крестиков. Итого хотя бы 5q^2 крестиков. При больших n это примерно 55% от n (точнее, при все n>35 это больше половины).

[kobak]

Действительно, спасибо!