Формула. В. В. Прасолов задачи по планиметрии

• Название: В. В. Прасолов задачи по планиметрии
• Анкор: Формула
• Дата: 17.06.2022
• Размер: 6.7 Mb.
• Имя файла: planim5.pdf
• Тип: Учебное пособие; #599309
• страница: 53 из 70

§ 3. Инварианты
23.11.
Дана шахматная доска. Разрешается перекрашивать в другой цвет сразу все клетки какой-либо горизонтали или вертикали. Может ли при этом получиться доска, у которой ровно одна чёрная клетка

Условия задач
455
23.12.
Дана шахматная доска. Разрешается перекрашивать в другой цвет сразу все клетки, расположенные внутри квадрата размером 2. Может ли при этом на доске остаться ровно одна чёрная клетка?
23.13*.
Дан выпуклый угольник A
1
. . . A
2m
. Внутри его взята точка P, не лежащая ни на одной из диагоналей. Докажите, что точка P принадлежит чётному числу треугольников с вершинами в точках A
1
, . . . , В центре каждой клетки шахматной доски стоит по фишке.
Фишки переставили так, что попарные расстояния между ними не уменьшились. Докажите, что в действительности попарные расстояния не изменились.
23.15*.
Многоугольник разрезан на несколько многоугольников.
Пусть p — количество полученных многоугольников, q — количество отрезков, являющихся их сторонами, r — количество точек, являющихся их вершинами. Докажите, что p − q + r = 1 (формула Эйлера).
23.16*.
Выпуклый многоугольник разрезан на p треугольников так, что на их сторонах нет вершин других треугольников. Пусть и m — количества вершин этих треугольников, лежащих на границе исходного многоугольника и внутри его.
а) Докажите, чтоб) Докажите, что количество отрезков, являющихся сторонами полученных треугольников, равно 2n + 3m − Квадратное поле разбито на 100 одинаковых квадратных участков, 9 из которых поросли бурьяном. Известно, что бурьян за год распространяется нате и только те участки, у которых не менее двух соседних (те. имеющих общую сторону) участков уже поросли бурьяном. Докажите, что поле никогда не зарастёт бурьяном полно- стью.
23.18*.
Докажите, что существуют равновеликие многоугольники,
которые нельзя разбить на многоугольники (возможно, невыпуклые),
переводящиеся друг в друга параллельным переносом.
23.19*.
Докажите, что выпуклый многоугольник нельзя разрезать наконечное число невыпуклых четырёхугольников.
23.20*.
Даны точки A
1
, . . . , A
n
. Рассмотрим окружность радиуса содержащую некоторые из них. Построим затем окружность радиуса с центром в центре масс точек, лежащих внутри первой окружности, и т. д. Докажите, что этот процесс остановится, те. окружности начнут совпадать 4. Вспомогательные раскраски в шахматном порядке
23.21.
В каждой клетке доски 5
× 5 клеток сидит жук. В некоторый момент все жуки переползают на соседние (по горизонтали или вертикали) клетки. Обязательно ли при этом останется пустая клетка

Глава 23. Делимость, инварианты, раскраски
23.22.
а) Можно ли замостить костями домино размером 1
× шахматную доску размером 8
× 8, из которой вырезаны два противоположных угловых поля?
б)
*
Докажите, что если из шахматной доски размером 8
× 8 вырезаны две произвольные клетки разного цвета, то оставшуюся часть доски всегда можно замостить костями домино размером 1
× Докажите, что доску размером 10
× 10 клеток нельзя разрезать на фигурки в форме буквы T, состоящие из четырёх клеток.
23.24*.
Детали полотна игрушечной железной дороги имеют форму четверти окружности радиуса R. Докажите, что последовательно присоединяя их концами так, чтобы они плавно переходили друг в друга,
Рис. нельзя составить путь, у которого начало совпадает с концом, а первое и последнее звенья образуют тупик,
изображённый на рис. В трёх вершинах квадрата находятся три кузнечика, играющие в чехарду. При этом если кузнечик прыгает через кузнечика B, то после прыжка он оказывается на том же расстоянии от него, но, естественно,
по другую сторону и на той же прямой. Может ли после нескольких прыжков один из кузнечиков попасть в чет- вёртую вершину квадрата?
23.26*.
Дан квадратный лист клетчатой бумаги размером клеток. Проведено несколько несамопере- секающихся ломаных, идущих по сторонам клеток и не имеющих общих точек. Эти ломаные идут строго внутри квадрата, а концами обязательно выходят на границу. Докажите, что кроме вершин квадрата найдётся ещё узел (внутри квадрата или на границе, не принадлежащий ни одной ломаной 5. Другие вспомогательные раскраски
23.27.
Правильный треугольник разбит на одинаковых правильных треугольников (рис. 23.4). Часть из них занумерована числами
Рис. 23.4 1, 2, . . . , m, причём треугольники с последовательными номерами имеют смежные стороны.
Докажите, что m 6 n
2
− n + Дно прямоугольной коробки выложено плитками размером 2
× 2 и 1 × 4. Плитки высыпали из коробки и потеряли одну плитку 2. Вместо неё достали плитку 1 × 4. Докажите, что выложить дно коробки плитками теперь не удастся.
23.29.
Из листа клетчатой бумаги размером клеток вырезано 99 квадратиков

Условия задач
457
размером 2
× 2 клетки. Докажите, что из него можно вырезать ещё
один такой квадратик.
23.30.
Выпуклый угольник разбит на треугольники непересекаю- щимися диагоналями, причём в каждой его вершине сходится нечёт- ное число треугольников. Докажите, что n делится на Можно ли шашечную доску размером 10
× 10 замостить плитками размером 1
× На клетчатой бумаге даны произвольные n клеток. Докажите, что из них можно выбрать не менее n/4 клеток, не имеющих общих точек.
23.33*.
Докажите, что если вершины выпуклого угольника лежат в узлах клетчатой бумаги, а внутри и на его сторонах других узлов нетто Из 16 плиток размером 1
× 3 и одной плитки 1 × 1 сложили квадрат со стороной 7. Докажите, что плитка 1
× 1 лежит в центре квадрата или примыкает к его границе.
23.35*.
Картинная галерея представляет собой невыпуклый угольник. Докажите, что для обзора всей галереи достаточно [n/3] сторожей 6. Задачи о раскрасках
23.36.
Плоскость раскрашена в два цвета. Докажите, что найдутся две точки одного цвета, расстояние между которыми равно Плоскость раскрашена в три цвета. Докажите, что найдутся две точки одного цвета, расстояние между которыми равно Плоскость раскрашена в семь цветов. Обязательно ли найдутся две точки одного цвета, расстояние между которыми равно Точки сторон правильного треугольника раскрашены в два цвета. Докажите, что найдётся прямоугольный треугольник сверши- нами одного цвета.
*
*
*
23.40*.
Триангуляцией многоугольника называют его разбиение на треугольники, обладающее тем свойством, что эти треугольники либо имеют общую сторону, либо имеют общую вершину, либо не имеют общих точек (те. вершина одного треугольника не может лежать на стороне другого. Докажите, что треугольники триангуляции можно раскрасить в три цвета так, что имеющие общую сторону треугольники будут разного цвета.
23.41*.
Многоугольник разрезан непересекающимися диагоналями на треугольники. Докажите, что вершины многоугольника можно раскрасить в три цвета так, что все вершины каждого из полученных треугольников будут разного цвета

Глава 23. Делимость, инварианты, раскраски
23.42*.
Несколько кругов одного радиуса положили на стол так,
что никакие два не перекрываются. Докажите, что круги можно раскрасить в четыре цвета так, что любые два касающихся круга будут разного цвета.
См. также задачу
24.11
Решения
23.1.
а) Пусть прямая пересекает все стороны многоугольника. Рассмотрим все вершины, лежащие по одну сторону от не. Каждой из этих вершин можно поставить в соответствие пару сторон, из неё выходящих. При этом получим разбиение всех сторон многоугольника на пары. Поэтому если прямая пересекает все стороны угольника, то m чётно.
б) Из рис. 23.5 видно, как построить угольники прямую, пересекающую все его стороны, при любом Рис. Рис. Прямая l задаёт две полуплоскости одну из них будем называть верхней, а другую нижней. Пусть соответственно n
2
) — число вершин ломаной, лежащих на прямой l, для которых оба выходящих из них звена лежат в верхней (соответственно в нижней) полуплоскости, а m — число всех остальных точек пересечения прямой l и ломаной. Совершим обход ломаной,
выйдя из некоторой точки, не лежащей на прямой l, и вернувшись в туже точку. При этом мы переходим из одной полуплоскости в другую, только проходя через любую из m точек пересечения. Так как мы вернёмся в туже точку, из которой начали обход, то m чётно. По условию n
1
+ n
2
+ m = поэтому число n
1
+ n
2
нечётно; в частности, n
1 6= n
2
. Пусть для определённости
n
1
> n
2
. Проведём тогда в верхней полуплоскости прямую l
1
, параллельную и удалённую от неё на расстояние меньшее, чем любое ненулевое расстояние от l до вершин ломаной (рис. 23.6). Число точек пересечения ломаной с прямой равно 2n
1
+ m > n
1
+ n
2
+ m = 1985, те искомая прямая.
23.3.
Нет, не могут. После каждого удара изменяется ориентация (те. направление обхода) треугольника Пусть на клетчатой бумаге окрашено несколько клеток и n
k
— число окрашенных клеток, имеющих ровно k окрашенных соседей. Пусть N — число

Решения задач
459
общих сторон окрашенных клеток. Так как каждая из них принадлежит ровно двум окрашенным клеткам, то N = (n
1
+ 2n
2
+ 3n
3
+ 4n
4
)/2 = (n
1
+ n
3
)/2 + n
2
+
+ n
3
+ 2n
4
. Поскольку N — целое число, то число n
1
+ n
3
чётно.
Мы доказали, что число окрашенных клеток, имеющих нечётное число окрашенных соседей, всегда чётно. Поэтому нельзя окрасить 25 клеток так, чтобы у каждой из них было нечётное число окрашенных со- седей.
23.5.
Предположим, что окружность разбита на дуги указанным образом,
причём диаметрально противоположных точек деления нет. Тогда против концов любой дуги длиной 1 не лежат точки разбиения, поэтому противне лежит дуга длиной 3. Выбросим одну из дуг длиной 1 и противолежащую ей дугу длиной 3. При этом окружность разбивается на две дуги. Если на одной из них лежит m дуг длиной 1 и n дуг длиной 3, тона другой лежит m дуг длиной 3 и n дуг длиной 1. Общее количество дуг длиной 1 и 3, лежащих на этих двух больших дугах, равно 2(k − 1), поэтому n + m = k − 1. Так как кроме дуг длиной 1 и 3 есть только дуги сч тной длиной, то чётность длины каждой из двух рассматриваемых дуг совпадает сч тностью числа − 1. С другой стороны, длина каждой из них равна (6k − 1 − 3)/2 = 3k − Получено противоречие, так как числа k − 1 и 3k − 2 имеют разную чётность.
Рис. 23.7
23.6.
Возьмём соседние звенья AB и BC и на- зовём уголком угол, симметричный углу относительно точки B на рис. 23.7 уголок заштрихован. Такие же уголки можно рассмотреть для всех вершин ломаной. Ясно, что число особых пар равно числу точек пересечения звеньев с уголками. Остаётся заметить, что число звеньев ломаной, пересекающихся с одним уголком, чёт- но, так как по пути от A к C ломаная входит в уголок столько же раз, сколько выходит из него.
23.7.
Рассмотрим отрезки, на которые разбита сторона 01. Пусть a — число отрезков вида 00,
b — число отрезков вида 01. Для каждого отрезка рассмотрим число нулей, стоящих на его концах, и сложим все эти числа.
В итоге получим 2a + b. С другой стороны, все внутренние нули входят в эту сумму дважды, а есть ещё один нуль, стоящий в вершине исходного треугольника. Поэтому число 2a + b нечётно, те нечётно.
Перейдём теперь к разбиению треугольника. Пусть a
1
— общее количество треугольников вида 001 и 011, а b
1
— число треугольников вида 012. Для каждого треугольника рассмотрим число его сторон вида 01 и сложим все эти числа. В итоге получим 2a
1
+ b
1
. С другой стороны, все «внутренние»
стороны входят в эту сумму дважды, а все граничные лежат на стороне исходного треугольника и число их нечётно по предыдущему рассуждению.
Поэтому число 2a
1
+ b
1
нечётно, в частности, b
1 6= Предположим, что все пары вершин задают отрезки разной длины. Отрезку поставим в соответствие наименьшее из чисел − и 2n − |p − q|. В результате для данных n пар вершин получим числа, 2, . . . , n; пусть среди этих чисел k чётных и n − k нечётных. Нечётным числам соответствуют отрезки A
p
A
q
, где числа p и q разной чётности. Поэтому

Глава 23. Делимость, инварианты, раскраски среди вершин остальных отрезков будет k вершин сч тными номерами и вершин с нечётными номерами, причём отрезки соединяют вершины с номерами одной чётности. Следовательно, число k чётно. Для чисел n вида 4m,
4m + 1, 4m + 2 и 4m + 3 количество k чётных чисел равно 2m, 2m, 2m + и 2m + 1 соответственно, поэтому n = 4m или n = 4m + Предположим, что мы разбили десятиугольник требуемым образом.
Пусть n — число сторон чёрных треугольников, m — число сторон белых треугольников. Так как каждая сторона чёрного треугольника (кроме сторон многоугольника) является также и стороной белого треугольника, то − m = 10. С другой стороны, оба числа n и m делятся на 3. Получено противоречие.
23.10.
Пусть Q — квадратный лист бумаги, L(Q) — сумма длин тех сторон клеток, которые лежат внутри его. Тогда L(Q) делится на 4, так как все рассматриваемые стороны разбиваются на четвёрки сторон, получающихся друг из друга поворотами на
±90
◦
и относительно центра квадрата.
Если квадрат Q разделён на квадраты Q
1
, . . . , Q
n
, то сумма длин отрезков деления равна L(Q) − L(Q
1
) − . . . − L(Q
n
). Ясно, что это число делится на так как числа L(Q), L(Q
1
), . . . , L(Q
n
) делятся на При перекрашивании горизонтали или вертикали, содержащей k
чёрных и 8
− k белых клеток, получится 8 − k чёрных и k белых клеток.
Поэтому число чёрных клеток изменится нате. нач т- ное число. Так как чётность числа чёрных клеток сохраняется, из исходных чёрных клеток мы не сможем получить одну чёрную клетку.
23.12.
При перекрашивании квадрата 2
× 2, содержащего k чёрных и 4 − белых клеток, получится 4
− k чёрных и k белых клеток. Поэтому число чёрных клеток изменится нате. нач тное число. Так как чётность числа чёрных клеток сохраняется, из исходных 32 чёрных клеток мы не сможем получить одну чёрную клетку.
23.13.
Диагонали разбивают многоугольник на несколько частей. Будем называть соседними те из них, у которых есть общая сторона. Ясно, что из любой внутренней точки многоугольника можно попасть в любую другую, переходя каждый раз только в соседнюю часть. Часть плоскости, лежащую вне многоугольника, также можно считать одной из этих частей. Число рассматриваемых треугольников для точек этой части равно нулю, поэтому достаточно доказать, что при переходе в соседнюю часть чётность числа треугольников сохраняется.
Пусть общая сторона двух соседних частей лежит на диагонали (илисто- роне) PQ. Тогда всем рассматриваемым треугольникам, кроме треугольников со стороной PQ, обе эти части одновременно либо принадлежат, либо не принадлежат. Поэтому при переходе из одной части в другую число треугольников изменяется на k
1
− k
2
, где k
1
— число вершин многоугольника, лежащих по одну сторону от PQ, k
2
— число вершин, лежащих по другую сторону от Так как k
1
+ k
2
= 2m − 2, то число k
1
− k
2
чётно.
23.14.
Если хотя бы одно из расстояний между фишками увеличилось бы,
то увеличилась бы и сумма всех попарных расстояний между фишками, но сумма всех попарных расстояний между фишками не изменяется при любой перестановке.
23.15.
Пусть n — число вершин исходного многоугольника, n
1
, . . . , n
p
— числа вершин полученных многоугольников (к вершинам данного многоугольника

Решения задач
461
мы относим и все вершины других многоугольников, лежащие на его сторонах. Представим число r в виде r = n + r
1
+ r
2
, где и r
2
— количества вершин полученных многоугольников, лежащих на сторонах исходного многоугольника и внутри его. С одной стороны, сумма углов всех полученных многоугольников равна 2)
p
=
p
P
i=1
n
i
p
− 2p
p
. С другой стороны, она равна. Остаётся заметить, что 2(q − n − r
1
) + n + а) С одной стороны, сумма всех углов полученных треугольников равна p
p
. С другой стороны, она равна (n − 2)
p
+ 2m
p
. Поэтому = n + 2m − б) Воспользуемся результатом задачи. В рассматриваемой ситуации = n + 2m − 2 и r = n + m; требуется вычислить q. Согласно формуле Эйлера = p + r − 1 = 2n + 3m − Легко проверить, что длина границы всего заросшего бурьяном участка (или нескольких участков) не возрастает. В начальный момент она не превосходит 9 · 4 = 36, поэтому в конечный момент она не может быть равной Фиксируем на плоскости некоторый луч AB. Любому многоугольнику поставим в соответствие число F(M) зависящее от AB) следующим образом. Рассмотрим все стороны M, перпендикулярные AB, и каждой из них поставим в соответствие число, где l — длина этой стороны и знак «плюс»
берётся, если мы, идя от этой стороны в направлении луча AB, попадаем внутрь M, а знак минус — если наружу (рис. 23.8). Сумму всех полученных чисел мы и обозначим F(M); если у M нет сторон, перпендикулярных AB, то) = Рис. Легко видеть, что если многоугольник M разрезан на многоугольники
M
1
и M
2
, то F(M) = F(M
1
) + F(M
2
), а если получен из M параллельным переносом, то F(M
0
) = F(M). Поэтому, если и можно разрезать на части, переводящиеся друг в друга параллельным переносом, то F(M
1
) = F(M
2
).

Глава 23. Делимость, инварианты, раскраски
Рис. На рис.
23.9
изображены равные правильные треугольники
PQR
и
PQS
и луч AB, перпендикулярный стороне Легко видеть, что F(PQR) = a и F(PQS) =
= −a, где a — длина сторон этих правильных треугольников. Поэтому равные треугольники и PQS нельзя разрезать на части, переводящиеся друг в друга параллельным переносом.
23.19.
Предположим,
что выпуклый многоугольник M разрезан на невыпук- лые четырёхугольники M
1
, . . . , M
n
. Каждому многоугольнику N поставим в соответствие число f(N), равное разности между суммой его внутренних углов, меньших, и суммой углов, дополняющих до его углы, большие. Сравним числа A = f(M) и B = f(M
1
) + . . . + f(M
n
). Рассмотрим для этого все точки,
являющиеся вершинами четырёхугольников M
1
, . . . , M
n
. Их можно разбить на четыре типа. Вершины многоугольника M. Эти точки дают одинаковые вклады в A и B.
2. Точки на сторонах многоугольника M или M
i
. Вклад каждой такой точки в B на больше, чем в A.
3. Внутренние точки многоугольника, в которых сходятся углы четырёх- угольника, меньшие 180
◦
. Вклад каждой такой точки в B на 360
◦
больше,
чем в A.
4. Внутренние точки многоугольника M, в которых сходятся углы четы- рёхугольников, причём один из них больше 180
◦
. Такие точки дают нулевые вклады в A и В итоге получаем A 6 B. С другой стороны, A > 0, а B = 0. Неравенство > 0 очевидно, а для доказательства равенства B = 0 достаточно проверить,
что если N — невыпуклый четырёхугольник, то f(N) = 0. Пусть углы N равны a
>
b
>
g
>
d
. У любого невыпуклого четырёхугольника ровно один угол больше 180
◦
, поэтому f(N) =
b
+
g
+
d
− (360
◦
−
a
) =
a
+
b
+
g
+
d
− 360
◦
=
= Получено противоречие, поэтому выпуклый многоугольник нельзя разрезать наконечное число невыпуклых четырёхугольников.
23.20.
Пусть S
n
— окружность, построенная нам шаге, O
n
— её центр.
Рассмотрим величину F
n
=
P(R
2
− O
n
A
2
i
), где суммирование ведётся только по точкам, оказавшимся внутри окружности S
n
. Будем обозначать точки,
лежащие внутри окружностей и S
n+1
, буквами B с индексом точки, лежащие внутри окружности S
n
, но вне окружности S
n+1
, буквами C, а точки,
лежащие внутри окружности S
n+1
, но вне окружности S
n
, буквами D. Тогда O
n
B
2
i
) +
P(R
2
− O
n
C
2
i
) и F
n+1
=
P(R
2
− O
n+1
B
2
i
) +
P(R
2
− Так как точка является центром масс системы точек B и C, то O
n
B
2
i
+
P O
n
C
2
i
=qO
n
O
2
n+1
+
P O
n+1
B
2
i
+
P O
n+1
C
2
i
, где q — общее количество точек и C. Следовательно, F
n+1
− F
n
= qO
n
O
2
n+1
+
P(R
2
− O
n+1
D
2
i
) −
P(R
2
− O
n+1
C
2
i
).

Решения задач
463
Все три слагаемых неотрицательны, поэтому F
n+1
>F
n
. В частности, F
n
>F
1
> те Центров масс различных наборов данных точек конечное число, поэтому различных положений окружностей конечное число. Следовательно для некоторого n, а значит, qO
n
O
2
n+1
= 0, те Так как общее число клеток шахматной доски 5
× 5 клеток нечётно,
то чёрных и белых клеток не может быть поровну. Пусть для определённости чёрных клеток больше. Тогда жуков, сидящих на белых клетках, меньше, чем чёрных клеток. Поэтому хотя бы одна из чёрных клеток останется пустой,
так как нач рные клетки переползают только жуки, сидящие на белых клетках.
23.22.
а) Вырезаны поля одного цвета, пусть для определённости чёрного.
Поэтому остаётся 32 белых и 30 чёрных клеток. Так как кость домино всегда
Рис. Рис. накрывает одну белую и одну чёрную клетку,
то костями домино нельзя замостить шахматную доску 8
× 8 клеток, из которой вырезаны два противоположных угловых поля.
б) Рис. 23.10 показывает, что клетки шахматной доски можно обойти в циклическом порядке так, чтобы вернуться на тоже самое место,
с которого начинали обход. При этом полученный коридор можно замостить костями домино двумя разными способами, положив первую кость произвольно (на поворотах есть два способа положить кости домино).
При указанном обходе цвета клеток чередуются, поэтому если мы вырежем две клетки разного цвета, то наш цикл распадётся на два отрезка, состоящих из чётного числа клеток (если вырезаны две соседние клетки, то может получиться один отрезок. Каждый из этих отрезков мы можем замостить очевидным образом.
23.23.
Предположим, что доска 10
× 10 клеток разбита на такие фигурки. Каждая фигурка содержит либо 1, либо 3 чёрные клетки, те. всегда нечётное число. Самих фигурок должно быть = 25 штук. Поэтому они содержат нечёт- ное число чёрных клеток, а всего чёрных клеток = 50 штук. Получено противоречие.
23.24.
Разрежем плоскость на одинаковые квадраты со стороной 2R и раскрасим их вшах- матном порядке.
Впишем в
каждый из них окружность. Тогда детали полотна можно считать расположенными на этих окружностях, причём движение поезда, идущего изначала в конец,
происходит в белых клетках почасовой стрелке,
а в чёрных — против (или наоборот см. рис. 23.11). Поэтому тупик образоваться не может, так как по обоим звеньям тупика движение происходит в одну сторону

Глава 23. Делимость, инварианты, раскраски
Рис. Рассмотрим решётку, изображённую на рис. 23.12, и раскрасим её в два цвета, как показано на этом рисунке (белые узлы на этом рисунке не закрашены исходный квадрат заштрихован, причём кузнечики сидят в его белых вершинах. Докажем, что кузнечики могут попасть только в белые узлы, те. при симметрии относительно белого узла белый узел переходит в белый. Для этого достаточно доказать, что при симметрии относительно белого узла чёрный узел переходит в чёрный. Пусть A — чёрный узел — белый, а A
1
— образ точки A при симметрии относительно B. Точка является чёрным узлом тогда и только тогда, когда –
AA
1
= 2m
e
1
+ 2n
e
2
, где m и n — целые числа.
Ясно, что # –
AA
1
= 2
# –
AB = 2(m
e
1
+ n
e
2
), поэтому A
1
— чёрный узел. Таким образом, кузнечик не может попасть в четвёртую вершину квадрата.
23.26.
Раскрасим узлы клетчатой бумаги в шахматном порядке (рис. Так как концы любого единичного отрезка разноцветны, то ломаная с одно-
Рис. Рис. цветными концами содержит нечётное число узлов,
а с разноцветными — чётное. Предположим, что из всех узлов границы (кроме вершин квадрата) выходят ломаные. Докажем, что тогда все ломаные вместе содержат чётное число узлов. Для этого достаточно доказать, что число ломаных с одноцветными концами чётно. Пусть на границе квадрата расположено белых и 4n чёрных узлов (вершины квадрата не учитываются. Обозначим число ломаных, у которых оба конца белые, через k. Тогда имеется 4m − 2k ломаных с разноцветными концами и [4n − (4m − 2k)]/2 = 2(n − m) + k ломаных сч рными концами. Поэтому ломаных с одноцветными концами будет k + 2(n − m) + k = 2(n − m + k) — чётное число.
Остаётся заметить, что квадратный лист бумаги размером клеток содержит нечётное число узлов.
Поэтому ломаные, содержащие в совокупности чётное число узлов, не могут проходить через все узлы.
23.27.
Раскрасим треугольники,
как показано на рис.
23.14.
Тогда чёрных треугольников будет + 2 + . . . + n = n(n + а белых + 2 + . . .
. . . + (n − 1) = n(n − 1)/2. Ясно, что два треугольника с последовательными номерами разноцветные. Поэтому среди занумерованных треугольников чёрных может быть только на 1 больше, чем белых. Следовательно, общее число занумерованных треугольников не превосходит n(n − 1) + Раскрасим дно коробки в два цвета, как показано на рис. Тогда каждая плитка 2
× 2 покрывает ровно одну чёрную клетку, а плитка 4 покрывает 2 или 0. Поэтому чётность числа чёрных клеток дна коробки

Решения задач
465
Рис. Рис. совпадает сч тностью числа плиток 2
× 2. Так как при замене плитки 2 × 2 на плитку 1
× 4 чётность числа плиток 2 × 2 изменится, выложить дно коробки плитками не удастся.
23.29.
Заштрихуем на данном квадратном листе бумаги квадратики 2
× так, как показано на рис. 23.16. При этом получится 100 заштрихованных квадратиков. Каждый вырезанный квадратик задевает ровно один заштрихованный квадратик, поэтому хотя бы один заштрихованный квадратик остаётся целыми его можно вырезать.
23.30.
Если многоугольник разбит на части несколькими диагоналями, то эти части можно окрасить в два цвета так, чтобы части, имеющие общую сторону, были разного цвета. Это можно сделать следующим образом. Будем последовательно проводить диагонали. Каждая диагональ разбивает многоугольник на две части. Водной из них сохраняем раскраску, а другую перекрашиваем, заменяя везде белый цвет нач рный, а чёрный — на белый.
Проделав эту операцию для всех нужных диагоналей, получим требуемую раскраску. Так как в нашем случаев каждой вершине сходится нечётное число треугольников, то при такой раскраске все стороны многоугольника будут принадлежать треугольникам одного цвета, например чёрного (рис. Рис. Обозначим число сторон белых треугольников через m. Ясно, что m делится на 3. Так как каждая сторона белого треугольника является также и стороной чёрного треугольника, а все стороны многоугольника являются сторонами чёрных треугольников, то число сторон чёрных треугольников равно n + Поэтому n + m делится на 3, а поскольку m делится на 3, то и n делится на 3.

Глава 23. Делимость, инварианты, раскраски
Рис. Раскрасим доску в четыре цвета, как показано на рис. 23.18. Легко сосчитать, что клеток второго цвета 26, а четвёртого 24. Каждая плитка 1
× накрывает по одной клетке каждого цвета. Поэтому плитками 1
× 4 нельзя замостить доску 10
× 10, так как иначе клеток каждого цвета было бы поровну.
23.32.
Раскрасим клетчатую бумагу в четыре цвета, как показано на рис. 23.19. Среди данных n клеток найдётся не менее n/4 одноцветных клеток, а одноцветные клетки не имеют общих точек.
23.33.
Раскрасим узлы клетчатой бумаги в четыре цвета в том же порядке,
в каком раскрашены клетки на рис. 23.19. Если n > 5, то найдутся две одноцветные вершины угольника. Середина отрезка с концами в одноцветных узлах является узлом. Так как угольник выпуклый, то середина отрезка с концами в его вершинах лежит либо внутри его, либо на стороне.
23.34.
Разобьём полученный квадрат на клетки размером 1
× 1 и раскрасим их в три цвета, как показано на рис. 23.20. Легко проверить, что плитки 3 можно разбить на два типа плитка го типа накрывает одну клетку
1-го цвета и две клетки го цвета, а плитка го типа накрывает одну клетку
2-го цвета и две клетки го цвета. Предположим, что все клетки го цвета накрыты плитками 1
× 3. Тогда плиток го типа 9, а плиток го типа Рис. Рис. 23.20

Решения задач
467
Следовательно, они накрывают 9 · 2 + 7 = 25 клеток го цвета и 7 · 2 = клеток го цвета. Получено противоречие, поэтому одна из клеток го цвета накрыта плиткой 1
× Разрежем данный угольник непересекающимися диагоналями на треугольники (см. задачу. Вершины угольника можно раскрасить в три цвета так, что все вершины каждого из полученных треугольников будут разного цвета (см. задачу. Вершин какого-нибудь цвета будет не более [n/3]; сторожей достаточно поставить в этих вершинах.
23.36.
Рассмотрим правильный треугольник со стороной 1. Все три его вершины не могут быть разного цвета, поэтому две вершины имеют один цвет расстояние между ними равно Предположим, что любые две точки, лежащие на расстоянии окрашены в разные цвета. Рассмотрим правильный треугольник ABC со стороной все его вершины разного цвета. Пусть точка симметрична относительно прямой BC. Так как A
1
B = A
1
C = 1, то цвет точки отличен от цветов точек B и C, те. она окрашена в тот же цвет, что и точка A. Эти рассуждения показывают, что если AA
1
=
√
3, то точки A и одного цвета.
Поэтому все точки окружности радиуса с центром A одного цвета. Ясно,
что на этой окружности найдутся две точки, расстояние между которыми равно 1. Получено противоречие.
23.38.
Приведём пример раскраски плоскости в семь цветов, для которой расстояние между любыми двумя одноцветными точками неравно. Разобьём плоскость на равные шестиугольники со стороной a и окрасим их, как пока-
Рис. 23.21

Глава 23. Делимость, инварианты, раскраски зано на рис. 23.21 (точки, принадлежащие двум или трём шестиугольникам,
можно красить в любой из цветов этих шестиугольников. Наибольшее расстояние между точками одного цвета, лежащими водном шестиугольнике,
не превосходит 2a, а наименьшее расстояние между точками одного цвета, лежащими в разных шестиугольниках, не меньше длины отрезка см. рис. 23.21). Ясно, что AB
2
= AC
2
+ BC
2
= 4a
2
+ 3a
2
= 7a
2
> (2a)
2
. Поэтому,
если 2a < 1 <
√
7a, те, то расстояние между точками одного цвета не может быть равно Предположим, что нет прямоугольного треугольника с вершинами одного цвета. Разделим каждую сторону правильного треугольника двумя точками натри равные части. Эти точки образуют правильный шестиугольник. Если две его противоположные вершины одного цвета, то все остальные вершины будут второго цвета, а значит, есть прямоугольный треугольник с вершинами второго цвета. Следовательно, противоположные вершины шестиугольника разноцветные. Поэтому найдутся две соседние разноцветные вершины противоположные им вершины тоже разноцветные. Одна из этих пар разноцветных вершин лежит на стороне треугольника. Точки этой стороны, отличные от вершин шестиугольника, не могут быть ни первого, ни второго цвета. Получено противоречие.
23.40.
Докажем это утверждение индукцией по числу треугольников триангуляции. Для одного треугольника требуемая раскраска существует. Предположим теперь, что можно раскрасить требуемым образом любую триангуляцию,
состоящую менее чем из n треугольников, и докажем, что тогда можно раскрасить любую триангуляцию, состоящую из n треугольников. Выбросим треугольник, одна из сторон которого лежит на стороне триангулированной фигуры. Оставшуюся часть можно раскрасить по предположению индукции
(она, конечно, может состоять из нескольких кусков, но это не мешает. Увы- брошенного треугольника только две стороны могут граничить с остальными треугольниками. Поэтому его можно окрасить в цвет, отличный от цветов двух соседних с ним треугольников.
23.41.
Доказательство аналогично решению задачи. Главное отличие заключается в том, что выбрасывать нужно треугольник, выходящий двумя сторонами на границу многоугольника (см. задачу
22.46
).
23.42.
Доказательство проведём индукцией по числу кругов n. При n = утверждение очевидно. Пусть M — любая точка, O — наиболее удалённый от неё центр круга. Тогда круг с центром O касается не более трёх других данных кругов. Выбросим его и раскрасим остальные круги согласно предположению индукции. Этот круг можно окрасить цветом, отличным от цветов касающихся его кругов

ГЛАВА ЦЕЛОЧИСЛЕННЫЕ РЕШЁТКИ
Основные сведения
Рассмотрим на плоскости систему прямых, заданных уравнениями x = и y = n, где m и n — целые числа. Эти прямые образуют решётку квадратов или целочисленную решётку. Вершины этих квадратов, те. точки с целочисленными координатами, называют узлами целочисленной решётки.