Раскраски: мины и доска

[silversurficus]

Некоторые клетки доски $N \times N$ заминированы. Для каждой клетки известно, сколько соседних с ней по стороне заминированы. При каких $N$ по этой информации можно определить общее количество заминированных клеток. Эта задача на раскраски, хотя я не совсем понимаю, где их тут применить.

Моя часть решения:
Для доски с нечётным $N$ определить нельзя. Пусть $N$ нечётно: $N=2k+1$. Заминируем клетки главной диагонали через одну двумя способами: в первом заминировано $k$ клеток, во втором — $k+1$(они отличаются от предыдущих $k$ клеток). Различить их невозможно.

И, соответственно, такой вопрос:
Как доказать, что для любого четного $N$ это можно сделать. И можно ли?

[kotenok gav]

silversurficus в сообщении #1528858 писал(а):

Для доски с нечётным $N$ определить нельзя.

Почему?

[silversurficus]

kotenok gav в сообщении #1528861 писал(а):

silversurficus в сообщении #1528858 писал(а):

Для доски с нечётным $N$ определить нельзя.

Почему?

Я, возможно, недостаточно ясно выразился выше.
Теперь попытаюсь объяснить почему нельзя. Ещё раз допускаем, что $N$ - нечетно. Тогда оно представимо в виде $N=2k+1$. Возьмём наибольшую диагональ (ее длина как раз таки $2k+1$) в этой доске и расположим мины двумя вариантами: с первой клетки и через одну, т.е. $1, 3, ..., N$; со второй клетки и через одну, т.е. $2, 4, ..., N-1$. В одном из этих вариантов $k$ мин, в другом $k+1$, однако если больше мин нет в доске, то номера в других клетках будут идентичны в обоих случаях. То есть эти два случая неотличимы. Это видно по тому, что другие клетки, не входящие в диагональ, но примыкающие к ней, всегда смежны ровно с двумя клетками диагонали, а так как мины мы расположили через одну, то в обоих расположениях другие клетки всегда будут смежны ровно с одной миной

[worm2]

silversurficus, рассуждения правильные.

[silversurficus]

worm2 в сообщении #1528866 писал(а):

silversurficus, рассуждения правильные.

Это очень хорошо) Однако вопрос, или даже два, остаётся открытым: как использовать раскраски и как доказать, что для четного $N$ это можно сделать всегда, если можно?

Я вот думал над обычной шахматной раскраской, думал над тем, чтобы рассмотреть, соответственно ряд черных диагоналей, которые образуются при такой раскраске, и как-то доказать, что, зная числа в белых клетках, можно однозначно узнать количество мин в черных, но что-то не получилось)

[worm2]

Можно попробовать решить немножко другую задачу: всегда ли можно ли в поле $2k \times 2k$ отметить несколько клеток так, чтобы любая клетка поля (включая отмеченные) была смежна (по стороне) ровно с одной отмеченной клеткой? Если найдётся такой набор клеток, то сумма значений в этих клетках будет равна числу мин во всём поле. Если не найдётся, то это ещё не доказывает, что нельзя определить число мин.

[silversurficus]

worm2 в сообщении #1528870 писал(а):

Можно попробовать решить немножко другую задачу: всегда ли можно ли в поле $2k \times 2k$ отметить несколько клеток так, чтобы любая клетка поля (включая отмеченные) была смежна (по стороне) ровно с одной отмеченной клеткой? Если найдётся такой набор клеток, то сумма значений в этих клетках будет равна числу мин во всём поле. Если не найдётся, то это ещё не доказывает, что нельзя определить число мин.

Спасибо за подсказку, сейчас ещё подумаю

[worm2]

Выбирая клетки парами, предположительно, можно ещё упростить задачу, сведя к "замощению" поля фигурками определённого вида.
Вот пример "раскраски" для поля 4x4:

1112
1122
3322
3332

Здесь подчёркнутые цифры означают выбранные клетки, смежные с ними раскрашены одинаковым цветом, а также выделены одинаковыми цифрами. Хотя, по уму, тут цифр должно быть в 2 раза больше, но такая "спаренность", на мой взгляд, чуть более наглядна. Хотя всё равно паршиво выглядит. Если бы можно было цвет фона менять...

А вот вариант раскраски для поля 6x6:

111222
113322
433335
443355
446655
466665

Как бы это объединить в единый алгоритм замощения для всех полей $2k \times 2k$...

[Pphantom]

Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы в стартовом сообщении (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Олимпиадные задачи (М)»

[silversurficus]

worm2
Да, это, возможно, интересная идея!

[silversurficus]

Мне удалось решить задачу, там все довольно тривиально. Раскрашивания нашу доску по-шахматному. Берём один из углов доски, допусти, левый нижний, допустим он белый(роли не играет, т.к. белые и черные клетки симметричны). Берём информацию из этой клетки о минах, потому после этой клетки идёт диагональ из черных клеток, потом идёт диагональ из белых клеток(мы ее пропускаем), затем из черных клеток диагональ , затем из белых длины, вот в ней мы и смотрим на белые клетки через одну, начиная с первой, продолжаем этот алгоритм. В конце получаем информацию о минах во всех черных клетках. Повторяем то же самое для другого цвета.