#7 Раскраски и задачи на досках

Площадь доски равна \(25\), а площадь каждого домино равна \(2\). Суммарная площадь домино всегда четна, поэтому покрыть область площади \(25\) невозможно.

В полной доске \(6\times6\) черных и белых клеток поровну. После удаления двух клеток одного цвета равенство нарушается. Но каждое домино покрывает одну черную и одну белую клетку, значит, любое домино-покрытие закрывает одинаковое число клеток двух цветов. Противоречие.

На доске \(7\times7\) угловой цвет встречается \(25\) раз, другой цвет - \(24\) раза. Домино закрывают равные количества клеток двух цветов. Значит, после покрытия домино должна остаться клетка того цвета, которого было на одну больше, то есть углового цвета.

Каждый ход коня меняет цвет клетки. После нечетного числа ходов цвет будет противоположным начальному. Так как \(9\) нечетно, конь окажется на белой клетке. Поэтому вернуться на черную клетку за \(9\) ходов нельзя.

В раскраске по остатку \(i+j\pmod3\) каждое прямое тримино покрывает по одной клетке каждого цвета. На доске \(5\times5\) цветов \(0,1,2\) соответственно \(9,8,8\). Клетка \((1,1)\) имеет цвет \(2\), значит после удаления получаются числа \(9,8,7\). Они не равны, поэтому покрытия нет.

В шахматной раскраске противоположные углы доски \(8\times8\) одного цвета. После их удаления одного цвета остается на две клетки меньше, чем другого. Каждое домино покрывает по одной клетке каждого цвета, поэтому покрыть оставшуюся область домино невозможно.

В шахматной раскраске клетка \((i,i)\) всегда имеет один и тот же цвет, потому что \(i+i\) четно. Значит, удалены \(8\) клеток одного цвета. В полной доске цветов было поровну, а после удаления равенство нарушилось. Домино покрывают цвета поровну, поэтому замощение невозможно.

Покрасим столбцы попеременно в два цвета. Горизонтальное домино покрывает одну клетку каждого столбцового цвета, а вертикальное домино покрывает две клетки одного столбцового цвета. На всей доске обоих цветов по \(18\) клеток. Горизонтальные домино не меняют баланс, поэтому вертикальные домино должны дать одинаковое число клеток двух цветов. Это означает, что вертикальных домино в столбцах первого и второго цвета должно быть поровну. Но всего их \(5\), что невозможно.

В раскраске \((i,j)\mapsto i+j\pmod3\) каждое прямое тримино покрывает по одной клетке каждого цвета. На доске \(7\times7\) цветов \(0,1,2\) соответственно \(16,16,17\). Клетка \((1,2)\) имеет цвет \(0\), поэтому после удаления остаются количества \(15,16,17\). Они не равны, следовательно, покрыть оставшуюся часть прямыми тримино невозможно.

В раскраске по \(i+j\pmod4\) каждое прямое тетрамино покрывает по одной клетке каждого из четырех цветов. На доске \(5\times5\) количества цветов \(0,1,2,3\) равны \(6,6,7,6\). Клетка \((1,2)\) имеет цвет \(3\), поэтому после удаления остаются количества \(6,6,7,5\). Они не равны, значит покрытия быть не может.

Противоположные углы доски \(4\times4\) имеют один цвет. Но ход коня меняет цвет, поэтому после \(15\) ходов, то есть после нечетного числа ходов, конь должен оказаться на клетке противоположного цвета. Следовательно, закончить в противоположном углу он не может.

Так как \(mn\) нечетно, в шахматной раскраске одного цвета на одну клетку больше. Домино покрывают по одной клетке каждого цвета. Поэтому после удаления всех покрытых домино клеток останется именно клетка цвета, которого было больше.

В шахматной раскраске все клетки главной диагонали имеют один цвет. В полной доске \(10\times10\) цветов поровну, а после удаления \(10\) клеток одного цвета равенство нарушается. Домино всегда покрывает одну клетку каждого цвета, поэтому покрытие невозможно.

При раскраске \((i,j)\mapsto i+j\pmod3\) каждое тримино покрывает по одной клетке каждого цвета. Значит, \(21\) тримино покрывают по \(21\) клетке каждого цвета. На доске \(8\times8\) цветов \(0,1,2\) соответственно \(22,21,21\). Поэтому отдельная клетка обязана иметь цвет \(0\). Но \((1,1)\) имеет цвет \(2\), а \((8,8)\) имеет цвет \(16\equiv1\pmod3\). Значит, ни одна из этих клеток не подходит.

Покрасим столбцы попеременно. Горизонтальное домино всегда покрывает одну клетку каждого столбцового цвета. Вертикальное домино покрывает две клетки одного цвета. Так как на доске цветов поровну, вертикальные домино должны распределиться поровну между столбцами двух цветов. Их число должно быть четным. Число \(17\) нечетно, значит такое покрытие невозможно.

Покрасим доску шахматно. Каждый ход коня меняет цвет, значит граф ходов коня двудольный: все ребра идут между двумя цветами. Замкнутый путь, проходящий через \(25\) клеток, был бы циклом длины \(25\). Но в двудольном графе все циклы имеют четную длину, потому что цвета чередуются. Противоречие.

На доске \(9\times9\) угловой цвет встречается \(41\) раз, другой цвет - \(40\) раз. Все домино вместе закрывают одинаковое число клеток двух цветов. Оставшаяся одна клетка, покрытая мономино, должна быть клеткой цвета, которого было больше, то есть углового цвета.

Покрасим клетку \((i,j)\) по остатку \(i+j\pmod4\). Прямое тетрамино покрывает по одной клетке каждого цвета. На полной доске \(8\times8\) каждого цвета \(16\) клеток. На главной диагонали цвета чередуются только между \(0\) и \(2\): удаляются по \(4\) клетки цветов \(0\) и \(2\), а цвета \(1\) и \(3\) не удаляются. Остаются количества \(12,16,12,16\), не все равны. Поэтому покрытия нет.

При раскраске по \(i+j\pmod3\) каждое прямое тримино покрывает по одной клетке каждого цвета. Значит, \(16\) тримино покрывают по \(16\) клеток каждого цвета. На доске \(7\times7\) количества цветов равны \(16,16,17\), причем лишний цвет - это \(2\). Поэтому мономино обязано стоять на клетке цвета \(2\), то есть на клетке с \(i+j\equiv2\pmod3\).

В полной доске \(8\times8\) по \(32\) клетки каждого цвета. Домино покрывают равные количества черных и белых клеток. Значит, после удаления всех покрытых домино клеток остаток тоже должен иметь равные изменения относительно двух цветов: если одна непокрытая клетка черная и одна белая, покрытые клетки были бы \(31\) черная и \(31\) белая, что возможно. Значит утверждение в такой формулировке неверно: две непокрытые клетки могут быть разных цветов. Например, можно оставить две соседние клетки и покрыть остальное. Следовательно, правильный вывод: по раскраске нельзя доказать одинаковый цвет; условие недостаточно.

Покрасим клетку \((i,j)\) по остатку \(i+j\pmod4\). Каждое прямое тетрамино закрывает по одной клетке каждого цвета. На полной доске \(8\times8\) каждого цвета по \(16\). Углы имеют цвета \(2,1,1,0\), поэтому после удаления остаются числа \(15,14,15,16\). Они не равны, а значит область не может быть разбита на фигуры, каждая из которых берет один цвет каждого вида.

Покрасим клетку \((i,j)\) по остатку \(i+j\pmod4\). Каждое прямое тетрамино покрывает по одной клетке каждого цвета, поэтому \(20\) тетрамино покрывают по \(20\) клеток каждого цвета. На доске \(9\times9\) количества цветов \(0,1,2,3\) равны \(20,20,21,20\). Следовательно, единственная клетка, покрытая мономино, должна быть лишней клеткой цвета \(2\).

Покрасим столбцы попеременно. Как и раньше, горизонтальные домино покрывают по одной клетке двух цветов, а вертикальные - две клетки одного цвета. Так как на всей доске цветов поровну, вертикальные домино должны распределиться поровну между двумя типами столбцов. Значит, их общее число четно. Поэтому нечетное число вертикальных домино невозможно. Пример с \(16\): в первых четырех столбцах положим все домино вертикально, получим \(16\) вертикальных домино; оставшиеся четыре столбца можно покрыть горизонтальными домино по строкам.

Покрасим клетку \((i,j)\) по остатку \(i+j\pmod4\). Любое прямое тетрамино покрывает по одной клетке каждого из четырех цветов. На полной доске \(10\times10\) количества цветов \(0,1,2,3\) равны \(25,24,25,26\). На главной диагонали \((i,i)\) цвета чередуются между \(2\) и \(0\), поэтому удаляются \(5\) клеток цвета \(0\) и \(5\) клеток цвета \(2\). На побочной диагонали \((i,11-i)\) сумма индексов равна \(11\), значит все эти \(10\) клеток имеют цвет \(3\). После удаления остаются количества \(20,24,20,16\). Они не равны. Но замощение прямыми тетрамино требовало бы равного числа клеток каждого цвета. Противоречие.