Чётность. Раскраска. Задачи на решётках
Немного теории
В некоторых олимпиадных задачах важны соображения чётности. Например, число вершин графа, к которым примыкает нечётное число рёбер, всегда чётно. Соображения подобного рода полезны и в других задачах. Так для решения классической задачи: можно ли шахматную доску 8 на 8 клеток без двух клеток в противоположных углах покрыть костяшками домино 1 на 2 – достаточно заметить, что каждая кость домино покрывает две клетки разного цвета (при обычной шахматной раскраске), а угловые клетки – одного цвета. Оставшиеся 62 клетки имеют 32 клетки одного и 30 клеток другого цвета. Покрытие невозможно.
В большинстве задач величину, которая сохраняет свою чётность, необходимо сконструировать. При решении подобного рода задач бывает полезно использовать метод от противного.
Бывает полезна и раскраска в большее число цветов.
Помимо чётности или раскраски, в задачах на клетчатой бумаге и других плоских и пространственных решётках также нередко используются различные геометрические и комбинаторные соображения, метод координат.
Если рассмотреть на плоскости систему прямых, заданных уравнениями x = m и y = n, где m и n – целые числа, то эти прямые образуют решётку квадратов или целочисленную решётку. Вершины этих квадратов, то есть точки с целочисленными координатами, называют узлами целочисленной решётки. Бывает полезно рассматривать клетчатую бумагу как числовую плоскость, на которой узлы решетки – точки с целочисленными координатами, или квадрат из р2 узлов, координаты которых – пары остатков (х; у) при делении на р.
Задачи с решениями
1. По кругу в произвольном порядке записано 4 единицы и 5 нулей. Над этими числами выполняется следующая операция: между одинаковыми цифрами пишут ноль, а между различными – единицу, после чего предыдущие цифры вытирают. Затем такая же операция выполняется над полученными цифрами и так далее. Докажите, что после нескольких таких операций невозможно получить 9 нулей.
Допустим, что после k таких операций получено 9 нулей. Тогда после (k–1)-й операции все цифры должны были быть единицами, а потому после (k–2)-й операции произвольные две соседние цифры, записанные по кругу, должны были быть различными. Тогда нулей должно быть столько же, сколько и единиц, откуда получаем, что общее количество цифр – чётное число, что противоречит условию. Предположение ложно, значит, 9 нулей описанным способом получить невозможно.
2. Шахматная доска размером 6×6 покрыта 18 костями домино размером 1×2 (каждая кость покрывает две клетки). Докажите, что при любом таком покрытии можно разрезать доску на две части по горизонтальной или вертикальной линии, не повредив ни одной кости домино.
Предположим, что можно уложить кости домино на доску так, что каждая из горизонтальных и вертикальных прямых, разделяющих доску на клетки, пересекает хотя бы одну кость домино.
Всего имеется 10 таких прямых. Каждая из этих прямых разбивает доску на 2 части, состоящие из чётного числа клеток. В любой из этих частей содержится какое-то количество неразрезанных костей домино. Эти кости занимают чётное число клеток. Оставшиеся клетки заняты половинками разрезанных костей, а так как их чётное число, то и число разрезанных костей тоже чётно.
Итак, каждая из 10 прямых разрезает не меньше двух костей, а так как каждую кость пересекает только одна прямая, то число разрезанных костей не меньше 20. Однако общее количество костей, покрывающих доску, – 18. Противоречие.
Доказательство окончено.
3. Все вершины выпуклого многогранника находятся в узлах решётки, причём других узлов решётки внутри, на гранях и на рёбрах нет. Докажите, что число вершин многогранника не превосходит восьми.
Каждая из трёх координат узла решётки может быть либо чётной, либо нечётной; всего получается 23 = 8 различных вариантов. Поэтому если у многогранника есть девять вершин, расположенных в узлах решётки, то две из них имеют координаты одной чётности. Середина отрезка, соединяющего эти вершины, является узлом решётки, и лежит внутри многогранника, если этот отрезок – его диагональ; принадлежит грани, если отрезок – диагональ грани; лежит на ребре, если отрезок – ребро многогранника.
4. Докажите, что если из шахматной доски размером 8×8 вырезаны две произвольные клетки разного цвета, то оставшуюся часть доски всегда можно замостить костями домино размером 1×2.
На рисунке показано, что клетки шахматной доски можно обойти в циклическом порядке так, чтобы вернуться на то же самое место, с которого начинали обход. При этом полученный коридор можно замостить костями домино двумя разными способами, положив первую кость произвольно (на поворотах есть два способа положить кости домино).
При указанном обходе цвета клеток чередуются, поэтому если мы вырежем две клетки разного цвета, то наш цикл распадётся на два отрезка пути, состоящих из чётного числа клеток (если вырезаны две соседние клетки, то может получиться один отрезок). Каждый из этих отрезков мы можем замостить очевидным образом.
5. На клетчатой бумаге отмечены произвольные n клеток. Доказать, что из них всегда можно выбрать не менее чем n/4 клеток, попарно не соприкасающихся друг с другом (соприкасающимися считаются клетки, имеющие хотя бы одну общую вершину).
Разобьём всю плоскость на одинаковые квадраты, состоящие из четырёх клеток каждый. Далее, в каждом из этих квадратов «левую верхнюю» клетку назовем чёрной, «правую верхнюю» – белой, «левую нижнюю» – красной, а «правую нижнюю» – синей. Тогда, с одной стороны, любые две клетки одного цвета не соприкасаются. С другой стороны, среди отмеченных клеток можно выбрать не менее четверти таких, которые имеют одинаковый цвет, ибо в противном случае всего клеток было бы менее чем 4·(n/4) = n.
6. Клетки квадрата со стороной 50 раскрашены в четыре цвета. Докажите, что существует клетка, с четырех сторон от которой (сверху, снизу, слева и справа) имеются клетки одного с ней цвета (не обязательно соседние с этой клеткой).
Предположим, что клетки квадрата со стороной n удалось раскрасить таким образом, что для любой клетки с какой-то стороны от нее нет клетки одного с ней цвета.
Рассмотрим тогда все клетки одного цвета и в каждой из них нарисуем стрелочку в том из четырех направлений, в котором клетки того же цвета нет. Тогда на каждую клетку каемки нашего квадрата, кроме угловых, будет указывать не более одной стрелки, а на угловую – не более двух.
Так как клеток каемки всего 4n–4, то клеток каждого цвета не более 4n. С другой стороны, каждая из n2 клеток нашего квадрата раскрашена в один из четырех цветов, то есть
n2 < 4·4n.
Для решения задачи теперь достаточно заметить, что последнее неравенство неверно при n = 50.
Замечание. Несложно убедиться, что оно неверно при всех n > 17, и, следовательно, утверждение задачи верно уже в квадрате 17×17 – а заодно и в любом большем квадрате.
Уточнив немного рассуждение, можно показать, что клеток каждого цвета не более, чем 4n–4, поэтому утверждение неверно уже в квадрате 15×15.
7. На бесконечной во все стороны клетчатой доске, на которой первоначально расставлены фишки, заполняющие в точности прямоугольник (3k)×n, происходит игра по следующим правилам: любой фишкой можно перепрыгнуть через любую соседнюю (по вертикали или по горизонтали) фишку, за которой следует незанятая клетка, после чего фишка, через которую перепрыгнули, должна быть убрана с доски. Доказать, что на доске никогда не останется ровно одна фишка.
Разобьем все клетки бесконечной доски на 3 множества, как показано на рисунке (разным цветом раскрашены клетки разных множеств).
Тогда при каждом ходе количество фишек в двух множествах уменьшается на единицу, а в одном – увеличивается на единицу. При этом четность количества фишек в каждом множестве меняется на противоположную. Если сначала фишки занимали прямоугольник 3k на n, то их количества в каждом множестве были равны. Следовательно, после каждого хода четности количеств фишек в каждом из трех множеств должны совпадать. Если бы после какого-то хода на доске осталась одна фишка, то в двух множествах количество фишек было бы четно, а в одном – нечетно. Поэтому такая ситуация возникнуть не может.
Замечание. На рисунке бежевым контуром выделен прямоугольник со сторонами 3k и n при k=5, n=4 (частный случай); первоначальное количество фишек каждого цвета равно 20.
8. Какой наименьший периметр может иметь выпуклый 32-угольник, все вершины которого лежат в узлах клетчатой бумаги со стороной клетки 1?
Контур 32-угольныка А1А2…А32 мы представим как изображение суммы 32 векторов
А1А2 + А2А3 + . . . + А32А1 = 0.
Так как из любых 32-х различных по направлению векторов с суммой 0 можно составить выпуклый 32-угольник, задача сводится к следующей; найти 32 вектора, удовлетворяющий условиям:
(1) начало и конец каждого вектора лежат в узлах клетчатой бумаги;
(2) любые два вектора имеют разные направления;
(3) сумма всех векторов равна 0;
(4) при выполнении условий (1) – (3) сумма длин всех векторов минимальна.
Будем откладывать векторы от одной точки. Система 32-х векторов, изображенная на следующем рисунке удовлетворяет всем условиям (1) – (4).
Среди этих векторов четыре вектора длины 1, четыре – длины √2 и по восемь векторов длины √5, √10 и √13.
Замечание. Аналогичный прием «плотного заполнения уровней» – выбор n четверок различных целочисленных векторов наименьшей длины – позволяет сконструировать 4n -угольник минимального периметра с вершинами в узлах.
Ответ: 4 + 4√2 + 8(√5 + √10 + √13).
9. Можно ли так раскрасить все клетки бесконечной клетчатой плоскости в белый и чёрный цвета, чтобы каждая вертикальная прямая и каждая горизонтальная прямая пересекали конечное число белых клеток, а каждая наклонная прямая конечное число чёрных?
Введем такую систему координат хOy, чтобы вертикальные и горизонтальные линии сетки имели уравнения x = n и y = m (n и m – целые числа). Раскрасим в чёрный цвет те и только те клетки, все точки которых удовлетворяют одному из неравенств |y| > x2 или |x| > y2, остальные клетки покрасим в белый цвет, как показано на рисунке.
Всякая вертикальная прямая будет пересекать конечное число белых клеток между параболами y = x2 и y = –x2, всякая горизонтальная – конечное число белых клеток между параболами х = у2 и х = –у2. Всякая наклонная прямая будет пересекать лишь конечное число чёрных клеток, так как ее пересечение с каждой из четырёх "чёрных" областей может быть либо пустым, либо являться точкой, либо отрезком.
Ответ: можно.
10. На столе лежит большой лист клетчатой бумаги со стороной клетки 1 см и неограниченное количество одинаковых монет; радиус монеты равен 1,3 см. Доказать, что лист можно покрыть монетами, не налегающими друг на друга, так, чтобы все узлы листа оказались покрытыми.
На клетчатой плоскости можно так расположить одинаковые пятиугольники с вершинами в узлах («домики» на следующем рисунке), чтобы они покрывали все узлы.
С помощью простых геометрических вычислений не трудно убедиться, что каждый пятиугольник можно покрыть монетой с радиусом 1,3 см так, чтобы монеты не соприкасались.
Задачи без решений
1. За круглым столом сидят n рыцарей из двух враждующих стран. Число пар соседей-друзей равно числу пар соседей-врагов. Докажите, что n делится на 4.
2. Мышка грызёт куб сыра с ребром 3, разбитый на 27 единичных кубиков. Когда мышка съедает какой-либо кубик, она переходит к кубику, имеющему общую грань с предыдущим. Может ли мышка съесть весь куб кроме центрального кубика?
3. Вершины треугольника ABC расположены в узлах целочисленной решётки, причём на его сторонах других узлов нет, а внутри его есть ровно один узел O. Докажите, что O – точка пересечения медиан треугольника ABC.
4. На бесконечном листе клетчатой бумаги двое играют в такую игру: первый окрашивает произвольную клетку в красный цвет; второй окрашивает произвольную неокрашенную клетку в синий цвет; затем первый окрашивает произвольную неокрашенную клетку в красный цвет, а второй еще одну неокрашенную клетку в синий цвет и так далее. Первый стремится к тому, чтобы центры каких-то четырёх красных клеток образовали квадрат со сторонами, параллельными линиям сетки, а второй хочет ему помешать. Может ли выиграть первый игрок?
Каков будет ответ на этот вопрос, если второй игрок закрашивает синим цветом сразу по две клетки?
5. Дано простое число р > 3. Рассмотрим на координатной плоскости множество М, состоящее из таких точек с целыми координатами (х; у), что 0 < х < р, 0 < у < р. Докажите, что можно отметить р различных точек множества М так, чтобы никакие четыре из них не лежали в вершинах параллелограмма и никакие три из них не лежали на одной прямой.
Создано на конструкторе сайтов Okis при поддержке Flexsmm - накрутка вк