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

[avva]

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

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

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

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

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

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

Comments

[kobak]

В квадрате 4х4 можно (несложно явно предъявить решение), так что и в 10х10, наверное, можно :)

[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]

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

[oooooo]

промптик: придумай олимпиадную задачку про доску 10х10 и сочини рассказ как я её решал, страдал и наконец решил.

[tropicalizator]

Вроде достаточно пометить 48 клеток.
Ищем периодическое решение. Первый шаг заполнить столбцы 2,3; 5,6; 8,9. Тогда в любом квадрате 3х3 будет ровно 6 крестиков, а нам достаточно 5. Второй шаг стереть в столбцах 2,5,8 крестики на местах 1,4,7,10. Теперь в любом квадрате 3х3 есть ровно 5 крестиков, а всего крестиков 48.

[ny_quant]

> любая задача, не требующая специализированной математики, доступна моделям

Еще несколько месяцев назад это было не так. Надо будет снова проверить. Но по-прежнему очень сомневаюсь.

[ile_eli]

Доказал, что невозможно, нашел дырку в доказательстве, соответстевенно понял, как это да возможно.

[avva]

У меня так же было.