И кое-что еще, и кое-что другое
О чем не говорят, чему не учат в школе.
N! – см. Факториал.
⇔ – равносильно, тогда и только тогда.
[x] – см. Целая часть.
{x} – см. Дробная часть.
НОД(a, b) – см. Наибольший общий делитель.
НОК(a, b) – см. Наименьшее общее кратное.
Для какого наибольшего... предполагает решение из двух частей: приводится пример для конкретного числа и проводится оценка, показывающая что результат нельзя улучшить, то есть что при бóльших значениях примера не существует. Аналогично: при каком наименьшем...
Задачи на движение
Если не оговорено противное, то все объекты движутся с постоянными скоростями.
Игры
Если не оговорено противное, то
1. играют двое (Первый – он делает первый ход – и Второй);
2. игроки ходят по очереди;
3. каждый игрок знает все предыдущие ходы противника и видит позицию;
4. если играют на доске, то на каждое поле ставится не более одной фишки.
Обход ладьей подразумевает, что ладья не может перепрыгивать через клетки, то есть обходит хромая ладья.
Сумма цифр автоматически предполагает, что рассматриваемое число – целое неотрицательное.
Широкоизвестные факты, которым не всегда учат в школе.
Алгоритм – это способ достижения цели через жестко определенную последова-тельность шагов. Когда в ответе надо предъявить алгоритм, естественно рассматривать его как составную конструкцию. Типичные примеры: выигрышная или ничейная стратегия в играх. Кроме того, алгоритмы регулярно возникают в задачах на испытания.
Однако чаще алгоритм возникает как вспомогательное средство для получения результата. Но и в этом случае алгоритм надо строить, то есть конструировать.
Придумывание алгоритма требует изобретательности. Часто помогают общие идеи: причесывание задачи (см. 21.4.2, 22.5.1), узкие места (см. 21.3.4), принцип крайнего (25.1.5), разбиение на группы (см. 21.3.4, 24.3.6, 25.3.2, Д19.3.3, И30.4.7, Д30.4.7), четность (см. 25.1.5, И30.4.7, Д30.4.7), делимость (см. 20.7.1), чередование (см. 19.3.3) и т. п. Однако есть и несколько специфических приемов.
Жадный алгоритм
Если цель – максимум какой-то величины, то ее часто достигают, добиваясь максимально возможного приращения на каждом шаге (см. 25.3.7, 26.3.6).
Постепенное улучшение
Промежуточные ступени могут быть очень разнообразны. Рассуждения сильно облегчаются, если алгоритм проходит через достаточно однотипную цепочку ступеней (см. 25.2.3). Ступени могут различаться лишь значением числового параметра, чаще всего – полуинварианта (см. 21.4.2a, 19.3.3). Улучшение может осуществлять и редукция, то есть сведение ситуации к более простой (см. 23.4.6, 24.3.6, 25.2.3). Еще несколько примеров таких алгоритмов есть в подборке Постепенное конструирование (см. 23.4.6, 23.7.7, 23.8.4).
Подпрограмма
Бывает полезным делать шаги не поодиночке, а группами.
Подпрограмма – это группа шагов, обычно достигающая промежуточной цели (см. 21.3.4, 23.4.6, 27.4.6, Д19.3.3, 25.5.3, Д30.4.7) и/или изменяющая в нужную сторону полуинвариант (см. 20.7.1).
Поскольку при выполнении алгоритма ситуация все время меняется, может быть не очевидным, что все шаги возможны – это надо доказывать (см. 20.7.1, 19.3.3, 27.3.6), особенно в играх. Может понадобиться доказать также достижение цели или оптимальность результата (см. 27.3.3, 27.4.6). См. еще примеры анализа в следующем абзаце.
Естественный алгоритм
Часто последовательность шагов достаточно очевидна, а трудность – в доказательстве осуществимости (см. 21.4.2б), достижения цели (см. 27.1.4, 28.7.7) или оптимальности алгоритма (см. 25.1.5, 21.4.6, 21.3.6).
Ключевые задачи: 21.4.2a, 21.3.4а, 25.1.5
Задачи: 19.3.3, Д19.3.3, 20.7.1, 21.3.4б, 21.3.6, 21.4.2б, 21.4.6, 22.5.1, 23.4.6, 24.3.6, 25.2.3, 25.3.2, 25.3.7, 25.5.3, 26.3.6, 27.1.4, 27.3.3, 27.3.6, 27.4.6, 28.7.7, И30.4.7, Д30.4.7.
Здесь собраны задачи на число способов или объектов: подсчет (см. 19.8.6, 20.3.5, 20.4.4, Д20.8.5, 22.3.4, 23.3.7, 23.4.4, 23.6.4, 26.1.5), оценка и сравнение (см. 19.8.5, 26.8.6) , изучение свойств этого числа (см. 28.4.6). Кроме того, включены задачи, где методы подсчета числа способов оказываются применимы и при подсчетах других величин (см. 20.1.1, 20.5.5, 23.8.6, 27.1.3, И7.2.3).
Правила подсчета соответствуют четырем арифметическим действиям. Сформулируем их на языке множеств, обозначив |A| количество элементов во множестве A.
Правило сложения: если A∩B = ∅, то |A∩B| = |A| + |B| (см. 22.3.4).
Правило умножения: число способов выбрать упорядоченную пару (a, b), где a ∈ A, b ∈ B, равно |A|×|B|. С помощью этого правила устанавливается, что число перестановок из n элеменов равно n!, а число подмножеств во множестве из n элементов равно 2n (см. 19.8.5, 19.8.6, 20.3.5, 20.4.4, 23.4.4, 23.6.4, 28.4.6).
Правило деления: пусть мы насчитали N объектов, но при этом каждый объект учли k раз. Тогда всего есть N/k объектов. С помощью этого правила устанавливается формула для числа сочетаний.
Правило вычитания: |A\B| = |A| – |A∩B|. Это правило обычно связывают идеей дополнения. А именно, пусть надо найти или оценить число объектов, удовлетворяющих каким-то условиям. Может оказаться легче найти или оценить размер дополнения, то есть множества объектов, не удовлетворяющих этим условиям, а затем вычесть его из общего числа объектов (см. 23.3.7-реш.1, 19.8.5). Аналогично, число объектов, удовлетворящих двум условиям можно найти, вычитая из числа объектов, удовлетворящих первому условию, число объектов, удовлетворяющих первому, но не удовлетворяющих второму (см. 23.6.4). Вместо числа объектов может фигурировать другая величина, например сумма чисел (см. 20.1.1), длина (см. 27.1.3, 20.5.5) или четность (см. 23.8.6), важно лишь, что для конкретного объекта она равна общей сумме минус сумма значений по остальным объектам.
При вычислении подобной величины для множеств с комбинацией свойств возникает более сложное правило знаков: формула включения-исключения (см. 20.1.1, Д20.8.5).
Непрямой подсчет числа способов состоит в установлении соответствия между искомым множеством и множеством известного размера или множеством, число элементов которого легче сосчитать (см. 19.8.6, 20.4.4, 23.3.7, 23.4.4, 23.6.4, 26.1.5, 26.8.6, 28.4.6, И7.2.3).
Задачи: 19.8.5, 19.8.6, 20.1.1, 20.3.5, 20.4.4, 20.5.5, Д20.8.5, 22.3.4, 23.3.7, 23.4.4, 23.6.4, 23.8.6, 24.1.1, 26.1.5, 26.8.6, 27.1.3, 28.4.6, И7.2.3
см. Конечная плоскость.
Главное, что мы знаем о бесконечном – оно не конечно. Поэтому основной метод работы с бесконечностью – от противного.
Бесконечная серия
Если у множества есть бесконечное подмножество, то оно тоже бесконечно. Поэтому для доказательства бесконечности некоторого множества не обязательно явно находить все его элементы. Чаще всего находят серию элементов (примеров, решений), занумерованных натуральными числами (см. 21.2.2-реш.2, 27.7.2, 27.8.5, 28.3.5, 28.3.6). Можно начинать нумерацию не с 1, нумеровать нечетными (см. 21.2.2-реш.1) или целыми числами (см. 19.1.2, 19.2.3), а то и любым заведомо бесконечным множеством (см. 26.6.2).
Принцип Дирихле на бесконечности
Если бесконечное множество разделить на конечное число частей, найдется бесконечная часть (см. 24.2.3). Как следствие, ограниченная последовательность натуральных чисел принимает какое-то из значений бесконечно много раз (см. 21.3.5).
Бесконечное больше конечного
В бесконечном множестве натуральных чисел есть числа, бóльшие любого наперед заданного. Выбирая их, часто получают противоречия в рассуждениях «от противного» (см. 23.4.5, 28.2.4). Часто играют на конечности множества корней многочлена (см. 26.2.3) или конечности множества натуральных решений неравенства P(n) ≤ 0, где P – многочлен с положительным старшим коэффициентом (см. 24.8.2).
Принцип Архимеда: прибавляя на каждом шаге по 1, мы превзойдем любое число (см. 21.6.4, 24.2.5, 24.4.6). Как следствие, убывающая последовательность натуральных чисел не может быть бесконечной (см. 23.7.6, 24.8.2).
Ключевые задачи: 21.2.2, 26.2.3, 21.6.4.
Задачи: 19.1.2, 19.2.3, 21.3.5, 23.4.5, 23.7.6, 24.2.3, 24.2.5, 24.4.6, 24.8.2, 26.6.2, 27.7.2, 27.8.5, 28.2.4, 28.3.5, 28.3.6.
Биссектрисы обладают рядом замечательных свойств, часто используемых при решении задач.
1) Биссектриса – ось симметрии угла, и является ГМТ, равноудаленных от сторон угла (см. 20.3.3, 26.4.7-реш.1, 27.4.5, 28.1.4, 28.7.6-реш.2).
2) Биссектрисы смежных углов перпендикулярны (см. 22.3.2, 28.1.4, 28.4.2).
3) Три биссектрисы внутренних углов треугольника пересекаются в одной точке – центре вписанной окружности (см. И18.7.6). Две биссектрисы внешних углов треугольника и внутренняя биссектриса третьего угла пересекаются в одной точке – центре вневписанной окружности (см. 22.7.3, 28.1.4, 28.2.2, 28.4.2).
4а) Биссектриса AL треугольника ABC делит сторону BC в отношении BL:LC = BA:AC.
4б) Биссектриса AK внешнего угла A треугольника ABC делит противоположную сторону BC (внешним образом) в отношении KB:KC = AB:AC.
Задачи: 19.3.2, 20.3.3, 20.5.2, 22.3.2, 22.7.3, 26.4.7, 27.4.5, 28.1.4, 28.2.2, 28.4.2, 28.7.6, И18.7.6
см. Середины сторон четырехугольника. Свойства
Все эти задачи решаются, конечно, и без векторов. Однако применение векторов часто позволяет избежать дополнительных построений и перебора случаев (особенно вырожденных) (см. 21.8.2, 26.4.4, 27.7.3, 28.7.6). Даже одно использование векторной терминологии позволяет более лаконично оформить решение (см. 23.6.2).
Векторы естественно возникают в задачах с параллельным переносом (см. 23.4.7, 23.6.2, Геометрические преобразования).
Часто применяется формула для середины отрезка: если M – середина AB, то для любой точки O (см. 21.4.4, 23.6.2, 27.7.3).
Полезно помнить, что соотношения между векторами сохраняются при проекции (см. 20.4.5, 21.8.2). В задачах на суммы проекций очень эффективно можно использовать скалярное произведение (см. И4.4.5).
Задачи: 20.4.5-реш.2, 21.4.4, 21.8.2, 22.4.3, 23.4.7, 23.6.2, 26.4.4, 27.7.3, 28.7.6, И4.4.5.
1) Пусть диагонали AC и BD выпуклого четырехугольника ABCD пересекаются в точке P. ABCD вписанный PAPC = PBPD.
2) Пусть продолжения сторон AB и CD выпуклого четырехугольника ABCD пересекаются в точке Q.
ABCD вписанный QAQB = QCQD.
Доказательство. 1) PAPC = PBPD треугольники APB и DPC подобны по двум сторонам и углу P между ними ABD = ACD точки A, B, C, D лежат на одной окружности.
2) QAQB = QCQD треугольники QAC и QDB подобны по двум сторонам и углу Q между ними ABD = ACD точки A, B, C, D лежат на одной окружности.
Задачи: 19.6.5, 20.7.5, 20.8.2, 22.6.3, 22.7.3, 23.5.4, 24.3.4, 24.7.6, 25.2.4, 26.7.2.
Взаимно-однозначное соответствие между множествами A и B – это правило, которое сопоставляет каждому элементу множества A ровно один элемент множества B, и при этом каждому элементу из B что-нибудь сопоставляется. На самом деле A и B этом определении совершенно равноправны, потому что по каждому элементу B соответствующий элемент из A восстанавливается однозначно. Поэтому можно проверить, что соответствие является биекцией, установив соответствие в обратную сторону: если прямое соответствие элементу a из A сопоставляет элемент b из B, то обратное должно b сопоставлять a.
Если одно из множеств конечно, то другое – тоже, и элементов в них поровну. Это тоже используется для проверки взаимной-однозначности: если соответствие элеменов не склеивает, и в B не больше элементов, чем в A, то соответствие – биекция.
Классическим примером взаимно-однозначного соответствия служат координаты, которые сопоставляют точкам пары чисел.
Задачи: 20.4.4, 23.6.4, 25.1.3, 26.1.5.
см. Вписанные и вневписанные окружности.
Вневписанная окружность треугольника касается одной стороны и продолжений двух других сторон треугольника (см. рис 1). У треугольника есть три вневписанных окружности. Их центры, как и центр вписанной окружности равноудалены от сторон треугольника.
Есть немало задач, где используются нижеперечисленные свойства вписанной и вневписанных окружностей и их центров, а также свойства описанных многоугольников:
1. Центр вписанной окружности совпадает с точкой пересечения биссектрис. Центр вневписанной окружности, касающейся стороны AB, совпадает с точкой пересечения биссектрисы угла C и биссектрис внешних углов A и B (см. 22.7.3, 28.1.4, 28.2.2, 28.4.2).
2. Радиус r вписанной окружности и радиусы ra, rb, rc вневписанных окружностей можно найти из равенств S = pr = ra(p – a) = rb(p – b) = rc(p – c), где a, b, c – длины соответствующих сторон треугольника, S – его площадь, p – полупериметр (см. 28.3.4).
3. а. Расстояние от вершины A, B и C до точек касания с вписанной окружностью равны соответственно p – a, p – b, p – c, где a, b, c – длины соответствующих сторон треугольника, а p – его полупериметр.
б. Расстояния от вершин A, B и C до точек касания с вневписанной окружностью, касающейся стороны AB равны соответственно p – b, p – a, p.
в. Точки касания стороны треугольника со вписанной и вневписанной окружностями симметричны относительно середины этой стороны.
(см. 19.2.2, 21.4.4, 26.3.5, 28.3.4).
4. Диаметр окружности, вписанной в прямоугольный треугольник, равен сумме катетов минус гипотенуза (см. 28.3.4).
5. Если вписанная и вневписанная окружности прямоугольного треугольника касаются одного катета, то сумма их радиусов равна этому катету (см. 28.3.4).
6. Диаметр вневписанной окружности, касающейся гипотенузы, равен периметру треугольника.
7. Суммы противоположных сторон описанного четырехугольника равны. Сумма взятых через одну сторон описанного 2n-угольника равна сумме оставшихся сторон (см. 24.7.6, 28.3.4).
Задачи. 19.2.2, 20.3.3, 21.4.4, 24.7.6, 25.4.4, 26.3.5, 28.2.2, 28.3.4.
Выпуклая фигура по определению вместе с любыми двумя своими точками содержит соединяющий их отрезок. Важные примеры: полуплоскость, прямая, отрезок, круг.
Важное свойство: пересечение двух выпуклых фигур – выпуклая фигура.
Для выпуклого многоугольника есть еще два равносильных определения: 1) все его углы меньше 180; 2) он лежит по одну сторону от каждой из своих сторон.
Удобный пример выпуклых многоугольников – вписанные многоугольники, в частности – все треугольники.
Все диагонали выпуклых многоугольников – внутренние и пересекаются во внутренних точках (см. 27.8.1).
Соответственно, если все вершины многоугольника лежат по одну сторону от прямой, то и он целиком лежит по одну сторону от прямой (см. 23.4.1).
Все грани выпуклого многогранника являются выпуклыми многоугольниками.
Для решения подавляющего числа задач о выпуклых фигурах хватает опредеделения и «естественных» свойств, более глубокие факты можно найти в книге [Вып].
Задачи: 22.8.6, 23.2.4, 23.4.1, 27.8.1, 28.8.2, И6.8.4
см. выпуклая фигура.
см. выпуклая фигура.
Пусть AA1, BB1, CC1 – высоты остроугольного треугольника ABC. Тогда треугольник AB1C1 подобен треугольнику ABC с коэффициентом cosA.
Доказательство. Есть общий угол A, и равны отношения сторон .
Задачи: 23.8.5.
Нам хотелось бы назвать этот раздел «Комбинаторная геометрия», но этот термин в серьезной математике означает совсем другое.
А здесь собраны задачи, в которых наряду с классическими геометрическими соображениями (геометрической техникой) используются и комбинаторные мотивы. Например, задачи на построение и исследование конструкций из нескольких однотипных геометрических объектов. Конструкции эти изначально не заданы или заданы «не жестко», а количество объектов может быть большим или неопределенным. Пример: разбиение на треугольники диагоналями (см. 23.3.4, 24.3.5). Львиную долю составляют задачи на разрезание (см. 19.4.2, 19.5.5, 19.6.1, 21.3.6, 23.3.4, 23.5.2, 23.6.5, 23.7.5, 24.3.5, 24.6.5, 24.8.3, 26.3.7, 28.1.5, 28.4.4, 28.5.5, 28.6.5, 28.7.4, 28.8.5, Д21.3.6), много задач на расположение (см. 19.4.4, 20.5.4, 20.6.4, 22.8.6, 23.1.5, 23.2.4, 23.4.7, 24.8.7, 25.1.4, 25.2.5, 26.7.5, Д26.7.5, 27.7.1, 27.8.1, 28.2.5). Можно еще выделить задачи на покрытие (см. 22.4.6, 28.3.5, И6.8.4).
При решении комбинаторно-геометрических задач полезны методы, применимые к исследованию конструкций вообще: принципы крайнего (см. 20.5.4, 20.6.4, И6.8.4) и узких мест (см. 19.6.1, 23.2.4, 23.5.2, 23.6.5, 24.8.3, 28.4.4), постепенное конструирование (см. 19.4.4, 22.8.6, 25.2.5), при подсчетах и оценках – соответствие (см. 19.4.4, 22.6.5, 28.1.5), подсчет двумя способами (см. 21.3.6, 23.7.5, 24.8.7). При доказательстве невозможности (но не только!) полезен инвариант (см. 23.4.4, 23.7.5, 24.8.7, И4.2.5), в частности – соображения выпуклости (см. 23.2.4, 23.4.1).
Конкретно же особое внимание уделяют углам: подсчету сумм углов (см. 23.4.4, 23.6.5, 23.7.5, 24.8.3, 26.5.5, 28.7.4), подсчету количества углов: всех или какого-то вида – прямых, тупых (см. 20.3.4, 21.3.6, 21.4.7, 23.7.5, 26.5.5), соответствию углов и дуг (см. 20.3.4, 27.7.6). Еще углы могут быть узкими местам (см. 19.6.1) или крайними объектами: наибольший угол (см. 19.4.2), углы при наиболее удаленных вершинах (см. 20.5.4, 20.6.4).
Вычисление площади полезно в задачах на покрытие, но не только: площадь может быть и узким местом, и инвариантом (см. 22.4.6, 23.4.4, 28.4.4).
Задачи: 19.4.2, 19.4.4, 19.5.5, 19.6.1, 20.3.4, 20.5.4, 20.6.4, 21.3.6, 21.4.2, 21.4.7, 22.4.6, 22.5.4, 22.6.5, 22.8.6, 23.1.5, 23.2.4, 23.3.4, 23.4.1, 23.4.4, 23.4.7, 23.5.2, 23.6.5, 23.7.5, 24.3.5, 24.6.5, 24.8.3, 24.8.7, 25.1.4, 25.2.5, 26.3.7, 26.5.5, 26.7.5, Д26.7.5, 27.3.4, 27.7.1, 27.7.6, 27.8.1, 28.1.5, 28.2.5, 28.3.5, 28.4.4, 28.5.5, 28.6.5, 28.7.4, 28.8.2, 28.8.5, И4.2.5, И6.8.4.
Использование свойств геометрических преобразований часто позволяет упростить доказательство равенства или подобия фигур (например, если один четырехугольник получен из другого поворотом, то они равны); принадлежность нескольких точек одной прямой и т. п. Иногда это позволяет избежать перебора случаев (см. 19.7.2).
Под геометрическим преобразованием обычно понимают взаимно-однозначное отображение плоскости (пространства) на себя. Конечно, интерес представляют только преобразования, имеющие «геометрический смысл». Это прежде всего движения – преобразования, сохраняющие длины отрезков: параллельный перенос (см. 19.4.2, 23.4.7, 23.6.2, 20.3.3-реш.2, 28.8.2, 28.8.5, И7.1.7), поворот (см. 19.1.3, 19.8.4, 27.4.5-реш.2, 27.7.3-реш.2, 27.6.4-реш.2, 28.8.2) и осевая симметрия (см. 19.6.5, 19.7.2, 26.7.4, 25.8.2, 27.4.5-реш.2, 28.6.3, 28.7.6-реш.2, 28.8.7). Центральная симметрия (19.4.2, 20.5.2, 23.4.7, 25.4.4, И7.1.7) является частным случаем поворота.
Теорема Шаля утверждает, что кроме вышеперечисленных есть только один вид движения на плоскости: это скользящая симметрия, то есть композиция симметрии относительно прямой и переноса вдоль этой прямой. При этом повороты и переносы сохраняют ориентацию, а оба вида симметрий меняют ее. Отсюда, например, следует, что композиция двух симметрий – это поворот либо перенос (поскольку сохраняет ориентацию), что также часто используется (см. 19.4.2, 23.6.2).
Нередко при решении задачи применяется несколько геометрических преобразований или их комбинация (см. 19.4.2, 20.3.3-реш.2, 23.4.7, 23.6.2, 28.1.5). В разных решениях одной задачи могут применяться разные преобразования.
При преобразовании подобия (см. 23.8.5) и его важнейшем частном случае –гомотетии (см. 19.3.2 – замечание, 20.3.3, 22.3.2-реш.2, 25.4.4) расстояния не сохраняются, но сохраняется их отношение, а также углы; все фигуры переходят в подобные. Преобразование подобия (как и движение) сохраняет качественные свойства фигуры (см. 20.3.3). Подробнее см. тему Подобие.
К преобразованиям часто относят и инверсию (см. 26.4.7-реш.1, 25.7.4) хотя она и не осуществляет взаимно однозначного соответствия (центр инверсии «меняется местами» с «бесконечно удаленной точкой»).
Проекция отображает плоскость на прямую или пространство на плоскость. Не являясь геометрическим преобразованием, она применяется во многом аналогично им.
В нашем сборнике встречается только ортогональная (прямоугольная) проекция. Она сохраняет параллельность прямых и отношение длин параллельных отрезков. Даже это простое соображение может быть полезным (см. 19.8.2, замечание к 23.8.5). Сохраняются и соотношения между векторами (см. 21.8.2).
При ортогональном проектировании в пространстве отношение площади проекции к площади исходной фигуры равно косинусу угла между плоскостью фигуры и плоскостью проекции (см. 20.4.5 – первое решение, 20.8.1, 25.8.3).
Задачи: 19.1.3, 19.3.2, 19.4.2, 19.6.5, 19.7.2, 19.8.2, 19.8.4, 20.3.3, 20.4.5, 20.5.2, 20.8.1, 21.8.2, 22.3.2, 23.4.7, 23.6.2, 23.8.5, 25.4.4, 25.7.4, 25.8.2, 25.8.3, 26.4.7, 26.7.4, 27.4.5, 27.6.4, 27.7.3, 28.1.5, 28.6.3, 28.7.6, 28.8.2, 28.8.5, 28.8.7, И7.1.7
см. Геометрические преобразования.
Граф состоит из вершин и ребер, соединяющих некоторые пары вершин. Каждая пара вершин соединяется не более чем одним ребром. Обычно вершины изображают точками, а ребра – отрезками или дугами; при этом не важны длина и форма ребер и пересекаются ли они, а важно лишь, какие вершины соединены ребрами. Перевод задачи на язык графов делает условие более наглядным, облегчает подсчеты, позволяет использовать различные известные факты из теории графов. В олимпиадных задачах граф часто появляется «в замаскированном виде», например, говорят о «городах и дорогах» вместо «вершин и ребер».
В связном графе между любыми двумя вершинами есть путь по ребрам. Для доказательства связности достаточно проверить, что одна из вершин связана со всеми остальными (см. 22.8.7). Полезно помнить, что если в графе есть лишь две вершины, из которых выходит нечетное число ребер, то такие вершины связаны путем по ребрам (см. Д24.3.7). Для графов на плоскости без пересекающихся ребер связность может следовать из теоремы о пересечении ломаных (см. 24.3.7, 24.4.7). Подробнее см. Связность.
Цикл в графе – это замкнутый несамопересекающийся путь по ребрам. В цикле из каждой вершины выходит ровно два ребра. Фактически, цикл – это граф многоугольника.
При решении задач чаще всего используется разбиение на циклы (см. 25.3.2). Полезные инструменты: приведенная ниже лемма о разбиении на циклы (см. 23.3.3, 20.3.5), а также перестройка циклов (см. 26.8.6, 27.8.7). В графе без циклов обязательно есть вершина, из которой выходит не более одного ребра (см. 19.3.5, 20.7.6).
Лемма о разбиении на циклы. Если в графе конечное число вершин и из каждой вершины выходит ровно два ребра, то граф является объединением нескольких циклов.
Доказательство. Объявим любую вершину начальной и пойдем по ребрам, не поворачивая назад. Так как вершин конечное число, рано или поздно мы впервые попадем в ту, где уже были. Это может быть только начальная вершина: ребра, ведущие в другие пройденные вершины, уже использованы. Пройденный путь образует цикл. Выбросим его (то есть пройденные вершины и ребра) и будем повторять процедуру, пока ребер не останется.
Двудольный граф – граф, где вершины можно раскрасить в два цвета правильно, то есть концы каждого ребра – разного цвета. Примеры: 2n-угольник; куб (см. 21.5.4, 27.1.2) ; шахматная доска, где ребра – ходы коня или хромой ладьи.
Граф можно правильно раскрасить в два цвета, тогда и только тогда, когда в нем нет циклов нечетной длины. В частности, любой граф без циклов – двудольный.
При решении задач важна тесная связь двудольных графов с чередованием. Так, на любом маршруте чередуются цвета вершин. В частности, на шахматной доске при ходе коня или хромой ладьи чередуются цвета полей. Соответственно, для пары фигур чередуется совпадение и несовпадение цветов полей (см. 22.7.5), а для группы – четность числа фигур на белых полях (см. 21.3.4). А задав на ребрах двудольного графа направление к вершинам одного цвета, мы обеспечим еще и чередование стрелок на любом маршруте (см. замечание к 21.5.4). А в не двудольном графе наоборот: на цикле с нечетным числом ребер чередование невозможно (см. Д21.5.4).
Число ребер
Пусть в графе В вершин и Р ребер. Часто можно решить задачу, связав B и P уравнением или неравенством.
a) Сумма степеней вершин равна удвоенному числу ребер. В частности, если из каждой вершины выходит одинаковое число ребер k, то P = kB/2 (см. 27.6.1, 21.5.3).
б) Если в графе нет циклов, то Р B – 1.
в) Если граф связный, то Р B – 1 (см. 19.8.5, 24.7.5).
г) Если в графе К компонент связности, то Р + K B (см. 28.3.7).
д) Число ребер в двудольном графе с 2n вершинами не превосходит n2, в графе c 2n–1 вершинами не превосходит n(n–1).
Доказательство б) - г). Нарисовав сначала только вершины, получим фигуру из B частей. Будем проводить ребра по одному. Если ребро соединяет две части, то число частей уменьшается на 1, иначе не меняется.
б) Ребро не может соединить две вершины одной части (иначе они уже были соединены, и ребро замкнет цикл). Меньше одной части стать не может, поэтому будет проведено не более B – 1 ребра.
в) Чтобы в конце остался один связный граф, число частей надо уменьшить на B–1, то есть провести не менее B–1 ребра.
Граф без циклов, как уже сказано, двудольный и в нем мало ребер. Кроме того, если в нем конечное число вершин и есть хотя бы одно ребро, то есть и концевая вершина, из которой выходит ровно одно ребро (иначе пойдем, не поворачивая назад, и зациклимся). Такой граф может возникнуть как граф границ связной области, и тогда концевая вершина может оказаться узким местом (см. 19.3.5, 20.7.6).
Задачи: 19.3.5, 19.8.5, 20.3.5, 20.7.6, 21.3.4, 21.5.3, 21.5.4, Д21.5.4, 22.7.5, 22.8.7, 23.3.3, 24.3.7, Д24.3.7, 24.4.7, 24.7.5, 24.8.7, 25.3.2, 26.8.6, 27.1.2, 27.6.1, 27.8.7, 28.3.2, 28.3.7, И32.8.7.
Увиденное двумя глазами больше суммы увиденного каждым глазом. Посчитаем (оценим, исследуем) что-то двумя способами и сопоставим результаты (например, приравняем их). Это может решить задачу (см. 21.8.4, 24.7.3) или дать существенное продвижение, например уравнение (см. 22.5.3, 22.6.1, 23.7.5-реш.2), систему уравнений (см. 23.3.2), неравенство или оценку (см. 24.1.3.бв, 21.3.6, 25.3.4). А если результаты противоречат друг другу, это доказывает невозможность конструкции (см. 21.6.2, 24.1.3.бв, 26.7.7, 22.8.5). При необходимости можно посчитать одно и то же многими способами (см. 19.4.3).
Иногда, чтобы получить ограничение на уже известную величину, полезно ввести дополнительный параметр и сосчитать ее другим способом (см. 21.1.3, 21.2.3).
Ключевые задачи: 21.8.4, 21.6.2, 19.4.3.
Задачи: 21.1.3, 21.3.6, 22.5.3, 22.6.1, 22.8.5, 23.3.2, 23.7.5, 24.1.3, 24.7.3, 25.3.4, 26.7.7.
Многочисленные задачи на делимость тематически естественно разделить на две категории: традиционные – в них нахождение целых чисел и доказательство их свойств является целью (таких большинство), и те, где эти свойства используются как средство исследования ситуаций (см. 20.1.5, 20.7.1, 21.1.3, 21.2.3, Д21.4.5, 22.7.2, 23.5.1, 23.8.7, 24.3.5, 24.5.5, 25.2.3, 25.5.5, 25.7.3, 26.7.3, 26.8.7, 28.2.4). Среди традиционных задач можно выделить так называемые комбинаторные – в них делимость доказывается или используется нетрадиционным для теории чисел способом (см. 20.3.6, Д20.3.6, 21.5.4, Д21.5.4, 22.3.5, 24.1.2, 24.8.5, 25.7.6, 26.4.6, 28.4.6, И30.3.7).
Приемы решения таких задач многочисленны и многократно описаны в литературе. Ограничимся лишь краткими описаниями и перечнями задач.
Почти беспроигрышный прием – записать разложение чисел на простые множители и записать условия на показатели степеней по каждому простому множителю (см. 19.7.1, 24.3.2, 25.7.1, 21.5.4). Использвать единственность разложения на простые множители (см. 23.1.2, 23.5.1, 25.7.3). Использовать, что простых чисел бесконечно много (21.5.4), и среди них есть сколь угодно большие (23.3.1, 23.4.2). Для конкретных чисел обычно удается найти простое число в нужном интервале (см. 24.3.2). Вместо делимости на n бывает проще доказать делимость на число, кратное n. Так, при работе с цифровой записью бывает удобно доказать делимость на 1001, что, учитывая разложение 1001, дает делимость на 7, на 11 и на 13 (см. 19.7.3). Делимость можно доказать, подбирая остаток, а существование нужного остатка доказать из принципа Дирихле (см. Д19.7.3, 24.8.5, 26.6.2, 28.7.5). Определить остаток по цифровой записи (см. 20.1.2, 23.5.3, 25.2.3, 25.5.5). Использовать, что НОД чисел делит их разность (см. 20.3.1, 25.3.1). Сократить на НОД (см. 20.1.5, 20.3.6, 20.4.1, 22.1.3, 28.2.4). Представить все числа как произведения с общим множителем (см. 22.2.2). Заменить все числа остатками (см. 20.3.6, 26.1.1, 28.2.3). Использовать НОД как инвариант (см. 20.7.1). Рассмотреть НОД (см. 20.8.3, 23.5.1). Записать неравенство в связи с делимостью (см. 20.8.3, 22.3.3, 24.1.2, 24.3.5). Разложить выражение на множители (см. 21.1.2, 21.2.2, 25.5.2). Записать равенство произведений, использовать взаимную простоту n и n–1 (см. 21.1.3, 21.2.3, 23.7.6). Использовать единственность представления в виде суммы степеней двойки (см. 22.3.5). Записать неравенство для n-значного числа (см. 22.6.2, 25.5.4). Использовать делимость как инвариант (см. 22.7.2, 24.5.5, 24.8.7, 25.7.6). Показать, что равенства нет из-за разных остатков (см. 23.8.7). Перебрать делители (см. 24.1.2, 25.5.4, 26.4.6). Показать отсутствие делимости: все слагаемые делятся, а одно – нет (см. 23.8.7, 27.4.1, 28.3.6). Доказать делимость комбинаторно (см. 28.4.6). Свести к диофантовому уравнению (см. 21.1.3, 21.2.3, Д21.4.5, 25.7.3). Использовать делимость для сведения к случаю с меньшим номером (см. И30.3.7).
Задачи: 19.7.1, 19.7.3, Д19.7.3, 20.1.2, 20.1.5, 20.3.1, 20.3.6, Д20.3.6, 20.4.1, 20.7.1, 20.8.3, 21.1.2, 21.1.3, 21.2.2, 21.2.3, Д21.4.5, 21.5.3, 21.5.4, Д21.5.4, 21.8.1, 22.1.3, 22.2.2, 22.3.3, 22.3.5, 22.6.2, 22.7.2, 23.1.2, 23.3.1, 23.4.2, 23.5.1, 23.5.3, 23.7.6, 23.8.7, 24.1.2, 24.3.2, 24.3.5, 24.5.5, 24.8.5, 24.8.7, 25.1.3, 25.2.3, 25.3.1, 25.5.2, 25.5.4, 25.5.5, 25.7.1, 25.7.3, 25.7.6, 26.1.1, 26.1.5, 26.2.5, 26.4.6, 26.6.2, 26.7.3, 26.8.7, 27.4.1, 28.2.3, 28.2.4, 28.3.6, 28.4.6, 28.7.5, И30.3.7.
Диофантово уравнение – уравнение в целых числах.
При решении диофантовых уравнений часто используются
а) Разложение части уравнения на множители (19.1.2, 19.2.3)
б) использование свойств Делимости и остатков (20.8.3, 21.4.5)
в) выделение НОД каких-либо неизвестных (20.8.3)
г) оценки и неравенства (21.5.1, 20.8.3, 25.3.3, 27.3.5).
Уравнение Пелля (Д21.4.5).
К задачам на диофантовы уравнения близки (и могут быть сведены) задачи о делимости одних выражений на другие (см. 20.8.3) или представимости выражений в виде точных степеней (см. 26.8.1).
Подробнее см. [УрЦЧ]
Задачи: 19.1.2, 19.2.3, 20.8.3, 21.1.2, 21.4.5, Д21.4.5, 21.5.1, 24.7.1, 25.3.3, 26.8.1, 27.3.5.
Диаграмма Юнга – ступенчатая фигура из единичных квадратиков, причем первые клетки всех строк находятся в одном (первом) столбце, и в каждом следующем столбце квадратиков не больше, чем в предыдущем. При перевороте диаграммы (симметрии относительно биссектрисы левого верхнего угла) снова получается диаграмма Юнга.
Каждая диаграмма Юнга однозначно описывается списком длин строк (невозрастающий набор натуральных чисел). Например, диаграмма на рис. соответствует набору чисел 6, 5, 5, 4, 2, 2, 1.
Говорят, что диаграмма A мажорирует диаграмму B, если для любого k квадратиков в верхних k строках A не меньше чем в верхних k строках B. (Например, (4, 2, 1) мажорирует (3, 3).) Такое мажорирование используется, в частности, в неравенстве Мюрхеда.
Задачи: 20.5.3, 22.8.4
см. Непрерывность
см. Правильные многогранники.
Задачи: 26.8.5, 27.8.7
Домино – игра, в которой участвуют прямоугольные кости (доминошки) размера 21, разбитые на две квадратные половинки. В стандартный комплект домино входят 28 доминошек со всевозможными парами числами от 0 до 6 (если при этом пара состоит из двух одинаковых чисел, доминошка называется дублем). При выкладывании доминошек в цепочку обычно соблюдается правило: доминошки соприкасаются половинками с одинаковыми числами. В клетчатых задачах под доминошкой понимают прямоугольник из двух клеток.
Задачи: 20.3.2, 20.7.6, 22.6.4, 23.7.7, 24.5.5, 25.2.2.
Дробная
часть числа x,
{x}
– разность между числом и его целой частью,
{x}
= x
–[x].
Например, [5,2] = 0,2, [–5,2] = –0,8. Выполнены
неравенство
0
{x}
< 1 и равенство x
=
[x]
+{x}.
См. Целая
часть.
Дробно-линейная функция – функция вида , где хотя бы один из коэффициентов , отличен от нуля, а числитель и знаменатель не имеют общего корня. В частности, линейные функции и функция являются дробно-линейными.
Свойства
1. Область значений дробно-линейной функции – вся числовая прямая кроме, может быть, одной точки ( при 0). Каждое свое значение дробно-линейная функция принимает ровно один раз, т.е. уравнение = c имеет единственное решение при любом c ).
Дробно-линейная функция строго монотонна на каждом из интервалов своей области определения.
2. Дробно-линейная функция обратима. Обратная к ней функция также является дробно-линейной. В частности, функция обратна сама к себе. (см. 20.5.1).
3. Композиция дробно-линейных функций является дробно-линейной функцией.
4. Любая дробно-линейная функция является композицией линейных функций и функции . (Действительно, = + ).
Замечание. В формулировках свойств 3-4 допущена небольшая неточность, связанная с областью определения. Они становятся верными, если равенство фунций следует понимать с точностью до конечного числа точек области определения. Например, композиция двух дробно-линейных функций может быть не определена в двух точках числовой оси, а совпадающая с ней в остальных точках дробно-линейная функция – только в одной.
Задачи: 20.4.6, 20.5.1
– см. Алгоритм
В школьных задачах на движение обычно достаточно связать время, путь и скорость уравнением или системой и решить ее. В собранных здесь задачах это иногда удается, хотя правильный выбор исходных переменных играет важную роль (см. 22.6.1, 21.1.4, 19.1.1). Чаще, однако, для «прямолинейного» решения не хватает данных. Впрочем, при внимательном изучении оказывается, что без некоторых данных можно обойтись. Скажем, ,бывает удобным рассмотреть не сами скорости, а их разности (относительные скорости, см. 26.7.3) или отношения скоростей (см 20.5.1, 26.7.3). Может помочь и подмена объекта, когда наряду с объектами задачи рассматриваются и другие движущиеся объекты (см. 23.1.4, 26.5.1).
Задачи: 19.1.1, 20.5.1, 21.1.4, 22.6.1, 23.1.4, 26.5.1, 26.7.3
Всякая замкнутая несамопересекающаяся ломаная разбивает плоскость на две части – конечную внутреннюю и бесконечную внешнюю (говорят еще, что такая ломаная ограничивает многоугольник – выпуклый или невыпуклый): любая ломаная, соединяющая внутреннюю точку многоугольника с внешней пересекает его границу. Любую пару внутренних или пару внешних точек можно соединить ломаной, не пересекающей границы многоугольника.
В олимпиадных задачах теорему Жордана принято считать известной и не требующей доказательства. Несмотря на очевидность, доказательство не столь уж просто.
Замечание. Сравни с теоремой о пересечении ломаных.
Задачи: 19.3.5, 20.7.6
Пусть система может находиться лишь в конечном числе состояний, причем по каждому состоянию предыдущее и последующее состояния определяются однозначно. Тогда состояния системы циклически повторяются. В частности, в каждое состояние система возвращается бесконечно много раз.
Действительно, в силу конечности какое-то из состояний C повторится. Поскольку последующее состояние определяется однозначно, далее повторится и вся последовательность состояний между двумя C, и будет повторяться и впредь. А поскольку предыдущее состояние определяется однозначно, то такое же циклическое повторение случится и при движении в прошлое. Это означает, в частности, что все состояния, начиная с самого первого, входят в цикл и повторяются сколько угодно раз.
Замечание. Теорема верна и в случае, когда последующее состояние однозначно зависит от фиксированного числа предыдущих состояний и однозначно восстанавливается по фиксированному (возможно другому) числу последующих состояний.
Задачи: 22.8.7, И15.7.5.
см. Кость игральная.
см. Карты игральные.
Подавляющее число встречающихся в задачах игр – это конечные игры с полной информацией для двух игроков (подробнее см. Игры: теория).
Если мы хотим доказать, что кто-то из игроков выигрывает, проще всего предъявить его выигрышную стратегию. У одного игрока может быть несколько различных выигрышных стратегий. Для решения задачи, конечно, достаточно указать одну из них.
Если мы хотим доказать, что игра заканчивается вничью, необходимо доказать, что у каждого из игроков есть ничейная стратегия.
Придумав стратегию, надо доказать ее правильность: убедиться в том, что 1) всегда можно сделать ход согласно указанной стратегии и что 2) при любой игре противника достигается как минимум нужный результат – выигрыш или ничья. При доказательстве мы не можем «заставить» противника делать только «хорошие» ходы: например, если противник в итоге проигрывает, то все его ходы одинаково плохи.
Встречаются игры, где результат – это число: скажем, проигравший выплачивает победителю определенную сумму, зависящую от конечной позиции (см. 20.6.5, 21.7.4, 25.3.7, 26.3.6). В таких задачах обычно надо определить цену игры, то есть подобрать C и предъявить за обе стороны оптимальные стратегии (или доказать их существование), то есть стратегии, как Первому получить не менее С, а Второму отдать не более C. Внимание: оптимальные стратегии игроков надо рассматривать по отдельности; при доказательстве оптимальности нельзя пользоваться тем, что соперник тоже играет оптимально!
Полезно знать несколько распространенных приемов.
Соответствие (симметричные и парные стратегии)
Нередко используются стратегии, где очередной ход определяется только предыдущим ходом противника (см. 23.7.2, 20.6.5, И32.8.7), чаще всего – в каком-то смысле симметричный ходу противника (см. 20.6.5-реш.1). Иногда соответствие устанавливают так: ходы разбиваются на пары, и ответный ход является парным к предыдущему ходу противника (см. 20.6.5-реш.2). При этом могут возникать небольшие исключения вначале (например первый ход не входит в пару, или вначале обеспечивается заповедник, а разбиение на пары возникает лишь потом, (см. 24.5.2), в конце или по ходу (при отсутствии начатой пары делается произвольный ход, и уже противник будет вынужден завершить пару, см. 20.6.5, 24.1.4).
Анализ позиций, или Ставь на минус
Более мощный, но и более хлопотливый прием. Из позиций выделяются плохие (отмечаются минусом) и хорошие, при этом любой ход из плохой позиции ведет в хорошую, а из хорошей позиции всегда есть ход в плохую. Стратегия состоит в ходах, каждый раз «загоняющих» противника в плохую позицию (см. 26.3.6). Часто такая маркировка позиций делается анализом с конца, начиная от проигрышных позиций. Плохие и хорошие позиции могут различаться и инвариантом (см. 24.7.4, 26.4.2, 25.3.7).
Заповедник
Если проигрывает тот, кто не может ходить, бывает полезно создать возможность хода, которой не может помешать противник («отгородить заповедник»). В остальном игра может протекать произвольно, или с помощью соответствия (см. 24.5.2), а ход в заповедник делается в решающий момент. Возможно создание и нескольких заповедников (см. 22.6.4), хотя это уже скорее следующий прием.
Накопление преимущества
В несимметричных играх условия победы могут достигаться постепенно, ход за ходом. Часто победитель своими ходами наращивает до нужного значения некоторый полуинвариант (см. 20.7.3, 22.6.4, 24.8.5).
Передача хода
Встречаются задачи, в которых явно предъявить нужную стратегию не удается, но можно доказать её существование. Передача хода позволяет неконструктивно доказать отсутствие выигрыша у одной из сторон (обычно у Второго). Пусть можно передать ход противнику, не меняя позиции. Если у меня есть выигрывающая стратегия, то у противника ее нет. А если у меня ее нет, то я делаю передачу хода, и у противника снова нет выигрывающей стратегии.
Этот же прием срабатывает в чуть более общей ситуации: когда есть выбор: создать некоторую позицию с нашим ходом или симметричную с ходом противника (см. 26.7.6).
Игра на опережение
В математических играх, как и в жизни, выигрыш может доставаться тому, кто первый займет ключевое положение (или положения). В этом случае стратегия такова: каждый раз оказываться к ним ближе, чем соперник (см. И32.8.7).
Игры-шутки
В некоторых играх результат предопределен и не зависит от желания игроков. В чуть более сложных случаях выигрыш обеспечивается одним-двумя начальными ходами, а дальше выигрывающая сторона может играть как угодно (см. И29.3.4).
Ключевые задачи: 23.7.2, 26.3.6, 24.5.2, 26.7.6.
Задачи: 20.6.5, 20.7.3, 21.7.4, 22.6.4, 24.1.4, 24.7.4, 24.8.5, 25.3.7, 25.7.6, 26.4.2, И29.3.4, И32.8.7.
Договоримся о терминах и докажем существование выигрышной или ничейной стратегии. Приемы решения задач и их список– см. Игры.
Правила игры задают (явно или неявно) все возможные позиции (в позицию включается и очередь хода), ходы (как разрешенные переходы между позициями), конечные позиции (с указанием результата – выигрыш одного из игроков, ничья, или величина выплаты одному из игроков), а также одну начальную позицию.
Слово «позиция» не надо понимать слишком буквально. Скажем, при игре в шахматы позиция включает не только ситуацию на доске, но и предыдущую события партии: например, допустимость рокировки или возможность взятия пешки на проходе.
Конечная игра заканчивается за конечное число ходов. (В частности, шахматы – конечная игра: есть правила, препятствующие ее неограниченному продолжению.) Внимание: в конечной игре количество в принципе возможных позиций может быть и бесконечным – см. 26.3.6.
В игре с полной информацией каждый игрок знает все предыдущие ходы противника и видит позицию (не как при игре в карты, где каждый видит только свои карты).
Первый и Второй. Обычно игроков двое, и они ходят по очереди. Если у них нет имен, то того, кто сделал первый ход, обычно называют Первым, а его противника – Вторым.
Иногда первого игрока называют начинающим (обычно только в вопросе: «Кто выигрывает, начинающий или его партнер?»).
Стратегия – алгоритм, который предусматривает ответ (не обязательно один) на каждый ход противника (и самый первый ход, если речь идет о стратегии Первого).
Выигрышная стратегия ведет к победе игрока при любых ответах противника.
Ничейная стратегия обеспечивает игроку как минимум ничью (см. 26.7.6).
Существование выигрышной стратегии.
В конечной игре без ничьих у одного из игроков есть выигрышная стратегия.
Доказательство. Предположим противное: начальная позиция Р не определена (для нее ни у одного из игроков нет выигрышной стратегии).
Пусть ходит игрок А. Из Р он не может попасть в позицию, в которой у него есть выигрышная стратегия (иначе этот ход был бы началом выигрышной стратегии).
Также все его ходы не могут вести в позиции, где игрок В имеет выигрышную стратегию (иначе выигрышная стратегия в позиции Р есть у В).
Значит, из позиции Р существует ход в неопределенную позицию, из нее – в новую неопределенную и т. д. Заставим игроков ходить только в неопределенные позиции. В силу конечности игра когда-то закончится. Противоречие, так как последняя позиция определена.
Замечание. На самом деле приведенное доказательство дает конструктивный алгоритм определения для каждой позиции выигрышная она или проигрышная – анализ с конца. Разделим изначально все позиции на определенные и неопределенные. Определенные – это конечные, они выигрышные или проигрышные. Поскольку нельзя бесконечно долго ходить по неопределенным позициям, то из некоторой неопределенной позиции P все ходы ведут в определенные. Тогда и P можно определить как выше. Так постепенно определим все позиции: на первом шаге те, из которых игра заканчивается за один ход, потом те, из которых игра заканчивается за два хода и т.д., пока не дойдем до начальной.
Следствия. В любой конечной игре
1) либо у Первого есть выигрышная стратегия, либо у Второго есть ничейная стратегия..
(Для доказательства достаточно рассмотреть новую игру, где ничья считается выигрышем Второго).
2) либо у одного из игроков есть выигрышная стратегия, либо у обоих есть ничейные стратегии.
Игры «с числовым результатом»
Встречаются игры, где результат – это число: проигравший выплачивает победителю определенную сумму, зависящую от конечной позиции. Результатом отдельной игры считается сумма, выплаченная Вторым Первому (а если выигрывает Второй, то результат отрицателен). Играми с числовым результатом можно считать и «традиционные» игры, где выигрыш Первого, его проигрыш или ничья соответствуют выплатам 1, –1, 0.
Цена игры. Если у Первого есть стратегия, приносящая ему не менее C, а у Второго – стратегия, приносящая Первому не более С, то C называется ценой игры, а соответствующие стратегии называются оптимальными для Первого и Второго. Не у всякой игры есть цена, но если есть, то только одна (почему?).
Существование цены игры
У конечной игры с конечным числом выплат всегда есть цена.
Доказательство. Как и в доказательстве существования выигрышной стратегии, рассмотрим неопределенную позицию P, из которой все ходы ведут в определенные. Тогда возможные ходы из P задают конечный список возможных выплат Первому. Если из P ходит Первый, он выберет ход с максимальной выплатой, а если Второй – то с минимальной. Эта выбранная выплата и определяет результат для P. Далее дословно повторяем рассуждения из доказательства существования выигрышной стратегии и последующего замечания.
Замечание. Доказанные утверждения не всегда делают игру неинтересной. Например, они верны и для игры в шахматы. Но никто не знает, есть ли у кого из противников выигрывающая стратегия. Более того, даже если доказано, что выигрышную стратегию имеет Первый, это не означает, что указанная страте-гия может быть предъявлена (доказательство может быть неэффективным – см. 26.7.6, а «существующий» алгоритм может быть необозримо большим – состоять в перечислении всех позиций и «правильных» ходов).
см. Правильные многогранники.
Задачи: 26.8.5
см. Процессы.
Ключевые задачи: 22.7.2, 23.2.5.
Задачи: 20.7.1, 20.7.6, 22.8.5, 23.4.4, 23.7.5, 25.5.3б, 25.4.7, 25.6.4, 26.7.7, 27.8.7, 28.1.1, 28.2.1, 28.3.3.
Инверсия (симметрия) относительно окружности с центром O и радиуса r – это преобразование плоскости, при котором каждая точка A переходит в точку A, находящуюся на луче OA на расстоянии от O. Ясно, что повторное применение инверсии возвращает все точки на свои места. Удобно считать, что O меняется местами с «бесконечно удаленной точкой». Известно, что при инверсии
а) прямые, проходящие через O, переходят в себя (как бы выворачиваются наизнанку;
б) прямые, не проходящие через O, переходят в окружности;
в) окружности, проходящие через O, переходят в прямые;
г) окружности, не проходящие через O, переходят в окружности;
д) инверсия сохраняет углы; например, угол между двумя окружностями (то есть между их касательными в точке пересечения), равен углу между соответствующими им прямыми.
Подробнее см. [Бак].
Задачи: 25.7.4, 26.4.7.
см. Окружности
Математическая индукция помогает коротко записать строгое решения, но не объясняет, как его придумать, и в чем его смысл.
В простых случаях индукция остается «за кадром»: в цепочке, построенной по очевидному закону, вполне хватает многоточия между первыми и последними членами (см. 22.8.2); свойство, которое не меняется на каждом шаге, является инвариантом (см. 25.8.2), хотя формально и там и тут доказательство проводится индукцией по числу шагов. В других случаях мы старались наряду с доказательством по индукции дать и другое решение, отражающее, на наш взгляд, суть задачи точнее (см. 21.6.3, 25.1.3, 21.8.3).
Наиболее оправдано применение индукции при построении сложных конструкций, когда очередной этаж строится на основе уже построенных нижних этажей. Собственно, построение по индукции является частным случаем постепенного конструирования (см. 19.8.3, 23.4.2, 24.3.6, 24.7.3, 25.4.2, 26.8.4, Д30.4.7) и может быть при необходимости преобразовано в явный алгоритм.
Желающим подробностей рекомендуем главу «Индукция» И.С.Рубанова в [ЛМК]
Задачи: 19.8.3, 21.6.3, 21.8.3, 22.8.2, 23.4.2, 24.3.5, 24.3.6, 24.7.3, 25.1.3, 25.4.2, 25.8.2, 26.8.4, И30.3.7, Д30.4.7
В некоторых задачах надо что-то узнать или добиться, проводя испытания и глядя на их результаты. Типичный сюжет крутится вокруг поиска фальшивых монет с помощью взвешиваний (см. 22.2.4, 23.1.3, 23.5.5, 27.1.5). Здесь «монеты» в меньшинстве – подборка очень нестандартная, а вообще среди олимпиадных задач на испытания задачи на взвешивания составляют львиную долю.
По методу это частный случай задач на алгоритмы: надо либо придумать алгоритм испытаний, либо доказать, что при любом алгоритме цель недостижима. Но, кроме общих методов, есть и специфический подход.
Пространство вариантов. Чаще всего перед нами ситуация одного неизвестного варианта из некоторого множества (пространства) возможных элементарных вариантов: монет (см. 27.1.5), чисел (см. 22.7.7, 24.3.2, И30.4.7, Д30.4.7), разбиений (22.2.4, 23.5.5), а в общем случае – комбинаций (23.1.3, 28.1.2, 25.8.6, Д25.8.6, И29.3.5). Типовые цели:
Ц1 – узнать, какой именно вариант имеет место (см. 22.7.7, 27.1.5, 28.1.2a, 28.3.7, И30.4.7, Д30.4.7);
Ц2 – узнать, принадлежит ли вариант некоторому множеству (см. 23.1.3, 24.3.7, 24.4.7, И29.3.5);
Ц3 – за несколько попыток (в условиях неполной информации) предъявить комбинацию с заданными свойствами (см. 22.2.4, 23.5.5, 23.6.3,).
Ц4 – оптимизировать какую-то функцию, например стоимость испытаний или число ошибок (см. 25.8.6, Д25.8.6).
Количество попыток или испытаний обычно ограничено.
Идея решения в том, что узнав результат очередного испытания (попытки), мы часть вариантов отбрасываем, тем самым уменьшая неопределенность. Контроль за множеством остающихся вариантов позволяет выбирать наиболее эффективные способы «отбраковки» (см. 22.7.7, 25.8.6, Д25.8.6). Задача может, однако, состоять и в выяснении, достижима ли цель (см. 22.7.7а,в, 23.1.3, 24.3.2, 28.1.2б) или оценке числа испытаний ( см 24.3.7, 24.4.7). Тогда невозможность гарантированно достичь цели за указанное число попыток доказывается обычно так: мы показываем, что в худшем случае после всех отбрасываний останется множество из более чем одного варианта. Этого достаточно для цели Ц1 (см. 22.7.7, 24.3.7). Для цели Ц2 нужно показать еще, что один из оставшихся вариантов принадлежит указанному множеству, а другой не принадлежит (см. 24.3.7, 24.4.7). Если число испытаний неограничено, достаточно указать два варианта, неразличимые при любом испытании (см. 24.3.2, 28.1.2б).
Ключевая задача: 22.7.7.
Задачи: 22.2.4, 23.1.3, 23.5.5, 23.6.3, 24.3.2, 24.3.7, 24.4.7, 25.8.6, Д25.8.6, 27.1.5, 28.1.2, 28.3.7, И29.3.5, И30.4.7, Д30.4.7.
Карты игральные – плоские прямоугольники, имеют одинаковые обратные стороны (рубашки) и разные лицевые стороны, на которых обозначены масть и достоинство. Обычно есть 13 достоинств (двойка, тройка, ..., десятка, валет, дама, король, туз) и четыре масти: трефы, пики (черные масти), бубны и червы (красные масти). Набор карт со всевозможными комбинациями мастей и досто-инств называется (полной) колодой. В стандартной колоде 134 = 52 карты, но бывают колоды и с меньшим количеством достоинств (36 карт, 32 карты).
Задачи: 19.8.6, 21.8.3, 23.8.6, 25.8.6, 28.3.7, 28.4.6, 28.7.7.
см. Окружности
Здесь собраны задачи, где в условии или решении фигурируют шахматы, прямоугольные и квадратные клетчатые сетки, таблицы (см. 22.1.1, 22.3.1, 22.8.4, 23.3.3, 23.4.3, 24.1.3, 24.5.5, 24.8.6, 25.1.1, 25.4.7, 26.7.7, 27.5.2, 27.7.5, 27.7.7, 28.2.3, 28.3.3), а также сетки из равносторонних треугольников (см. 19.4.6, Д19.4.6). Такие задачи популярны, особенно среди младших школьников, из-за наглядности формулировок и связи с играми.
По постановке вопроса можно выделить задачи на оценку+пример (см. 19.1.4, 19.4.6, Д19.4.6, 19.6.3, 19.7.5, Д20.2.3, 21.3.4, 21.7.5, 22.7.7, 23.3.5, 23.4.3, 24.7.5, 25.1.5, 25.2.2, 25.3.4, 25.7.2, 26.3.3, 26.5.3, 27.1.4, 27.3.3, 27.5.5, 27.6.5, 27.7.5, 28.1.5, 28.5.3, 28.6.1), конструкции и алгоритмы (см. 19.2.4, 19.3.3, Д19.3.3, 20.1.5, 20.6.5, 21.1.5, 21.2.5, 23.3.5, 24.8.6, 25.1.5, 26.5.3, 27.2.5, 27.3.3, И29.3.4), в том числе на расстановку (шахматных фигур, чисел, крестиков и т.п.; см. 19.2.4, 19.4.6, Д19.4.6, 19.7.5, Д20.2.3, 21.1.5, 21.2.5, 21.7.5, 22.3.4, 22.5.5, 22.7.5, 23.2.5, 23.7.2, 24.8.6, 25.1.1, 25.2.2, 25.3.4, 25.4.7, 25.7.2, 26.3.3, 26.7.7, 27.7.5, 28.5.3, 28.6.1, И7.1.7.), разбиения (см. 19.6.3, 20.2.3, 20.3.2, 21.1.5, 21.2.5, 21.4.6, 22.5.5, 24.5.5, Д24.5.5, 24.7.5, 28.1.5), игры (см. 20.6.5, 22.6.4, И29.3.4), раскраску (см. 20.1.5, 22.3.4, 27.5.5, 27.6.5), обходы (см. 19.3.5, Д19.3.5, 19.5.2, 20.7.6, 26.8.6, 27.1.4, 27.2.5). Отметим, что некоторые задачи на заполнение таблиц (чаще всего – последовательными числами) равносильны задачам на обход ладьей (см. 23.4.3, 23.6.4, 28.4.6)
Несмотря на внешнюю схожесть, по идеям решений клетчатые задачи весьма разнообразны и могут быть весьма нетривиальны. Все же можно выделить группу идей, характерных именно для таких задач. Прежде всего, это работа с конечными множествами. Полезно помнить, что наряду с множеством клеток есть и другие множества, в частности, состоящие из сторон клеток (см. 20.7.6, 21.4.6, 25.2.2), вершин клеток (см. 19.7.5, 24.7.5, 27.2.5), расстановок (см. 23.7.2, 24.8.6, 26.7.7), обходов (см. 23.6.4, 26.8.6, 27.1.4, 28.4.6). Широко применяется разбиение этих множеств на группы (см. Д19.3.5, 19.4.6, 20.2.3, 20.3.2, 20.6.5, 21.4.6, 22.1.1, 22.3.4, 22.5.5, 22.7.7, 22.8.4, 23.4.3, 25.2.2, 25.7.2, 27.5.2, 28.2.3) и выделение некоторых “ключевых” или “особых” подмножеств (см. 19.7.5, 20.1.1, 20.2.3, 21.7.5, 22.3.4, 23.6.4, 24.8.6, 25.1.5, 25.2.2, 25.3.4, 25.4.7, 25.7.2, 26.3.3, 26.5.3, 26.8.6, 27.1.4, 27.3.3, 27.5.5, 27.6.5, И7.1.7). Благодаря шахматной раскраске популярна идея чередования цвета клеток (см. 19.2.4, 19.5.2, 20.1.5, Д20.2.3, 21.7.5, 23.4.3, 23.6.4, 25.2.2); но могут чередоваться и расстановки (см. 21.3.4, 22.7.5, 27.2.5), а также границы и области (19.1.4, 26.7.4, И29.3.4). Кроме шахматной, может понадобиться и другая раскраска (20.1.5, 20.7.6, Д24.3.7, 24.5.5, 27.2.5). При подсчетах (но не только) может оказаться полезным рассмотреть площади и периметры (см. 21.4.6, 21.8.4, 24.1.3, 20.7.6, 21.8.4), координаты (см. Д19.4.6, 22.5.5, 26.7.7), расстояния между клетками, измеряемые числом ходов (см. 19.2.4, Д19.3.3, 20.2.3, Д20.2.3). Бывает полезно построить или рассмотреть вспомогательные объекты: граф (см. 23.3.3, 24.7.5, 27.1.4), в том числе – граф перегородок между клетками (см. 19.3.5, 20.7.6, 24.3.7, Д24.3.7, 24.4.7) инвариант расстановки (см. 22.5.5, 22.7.5, 23.2.5, 23.7.2, 25.4.7, 26.7.7, 27.2.5), таблицу (см. 24.5.5, 28.4.6), клетчатую сетку (см. Д24.5.5, 26.7.4, 28.1.5). При построении алгоритмов бывают полезны подпрограммы для отдельных полос (см. Д19.3.3, 21.3.4, 24.8.6, 25.4.7, 26.5.3, 27.1.4). Индукция и редукция могут опираться на вычеркивание строки и столбца (см. 22.3.1, 27.7.7.)
Задачи: 19.1.4, 19.2.4, 19.3.3, Д19.3.3, 19.3.5, Д19.3.5, 19.4.6, Д19.4.6, 19.5.2, 19.6.3, 19.7.5, 20.1.1, 20.1.5, 20.2.3, Д20.2.3, 20.3.2, 20.6.5, 20.7.6, 21.1.5, 21.2.5, 21.3.4, 21.4.6, 21.7.5, 21.8.4, 22.1.1, 22.3.1, 22.3.4, 22.4.5, 22.5.5, 22.6.4, 22.7.5, 22.7.7, 22.8.4, 23.2.5, 23.3.3, 23.3.5, 23.4.3, 23.6.4, 23.7.2, 24.1.3, 24.3.7, Д24.3.7, 24.4.7, 24.5.5, Д.24.5.5, 24.7.5, 24.8.6, 25.1.1, 25.1.5, 25.2.2, 25.3.4, 25.4.7, 25.7.2, 26.3.3, 26.5.3, 26.7.4, 26.7.7, 26.8.6, 27.1.4, 27.2.5, 27.3.3, 27.5.2, 27.5.5, 27.6.5, 27.7.5, 27.7.7, 28.1.5, 28.2.3, 28.3.3, Д28.3.3, 28.4.6, 28.5.3, 28.6.1, И7.1.7, И29.3.4.
см. Соответствие
Ключевая задача: 19.8.6.
Задачи: 19.4.5, 20.5.3, 21. 8.3, 22.2.4, 22.8.4, 23.4.4, 23.6.4, 24.8.6, 25.8.6, Д25.8.6, 28.4.6.
см. Карты игральные.
Среди задач турнира значительная часть – на построение и исследование конструкций. Мы разбили их на несколько разделов. Здесь остались, в основном, те, что не вошли в разделы Оценка+пример, Постепенное конструирование, Алгоритм и Геометрическая комбинаторика.
Чаще всего конструкцию надо построить. Не стоит начинать с чистого листа. Лучше оттолкнуться от чего-нибудь известного. Бывает, что всеми нужными свойствами обладает известная вам конструкция, просто вы об этих ее свойствах не задумывались (см. 26.3.1, 27.6.2, 20.8.1, И31.7.4). Но даже если у пришедшей в голову конструкции выполнена лишь часть условий, попробуйте ее «отремонтировать» (см. 26.2.5). Помогают также редукция и аналогия: строишь пример для упрощенного случая (скажем, для меньших значений параметра), а затем, отталкиваясь от него, для нужного (см. 21.1.5, 21.2.5).
Построение облегчает повторямость. Старайтесь обойтись минимальным числом различных элементов (см. 27.1.2, 25.1.1, 27.4.1, 28.4.7б). В конструкциях на делимость такими элементами чаще всего бывают простые числа, из них все и строят (см. 21.5.4, Д21.5.4, 25.3.1). Для последовательностей пример часто периодичен, или составляется из нескольких периодических кусков. Последнее особенно характерно для серий цифровых примеров (см. 27.3.1, 27.7.2, 27.8.5). Пример может переходить сам в себя при сдвиге, вращении или симметрии (см. 19.4.6, 20.1.5, 21.1.5, 21.2.5, 21.5.3). Многие примеры берут за основу известные конструкции с высокой степенью симметрии: правильные многоугольники, правильные многогранники и их графы (см 22.3.6), конечные плоскости (см. 26.8.7).
Много-мало (мнимо противоречивые конструкции)
Если два фактора (две величины) ведут себя сходно, но не одинаково, можно сыграть на частичном несходстве. И игрок, и казино хотят выиграть. Но если игроку важнее выиграть 9 раз из 10, а казино важнее остаться в плюсе – то это и надо устроить к обоюдному удовольствию! Более серьезный пример: идти под парусом против ветра удается из-за того, что силы сопротивления воды и воздуха действуют по-разному.
Итак, полезно помнить, что «больше и меньше», «много и мало» – понятия относительные.
Прежде чем браться за мнимо противоречивую конструкцию, полезно проанализиро-вать несходство. Чаще всего это удается сделать, составив подходящую систему уравнений или неравенств и решив ее. Тогда мы либо установим невозможность конструкции, либо выясним какие-то важные ее параметры.
Задачи на «много-мало»: 21.6.4, 19.5.1, 19.7.1, 20.2.5, 20.8.1, 22.7.1, 24.1.3, 24.6.2, 27.7.7.
Ну, а если все вышеперечисленные приемы не помогли, то случай сложный. Не дожидаясь озарения, принимайтесь за основательное исследование конструкции, и ее свойства сами подскажут, как строить пример (см. 21.4.5, Д21.4.5, 28.4.7).
Задачи: 19.4.6, 19.5.1, 19.7.1, 20.1.5, 20.2.5, 20.8.1, 21.1.5, 21.2.5, 21.4.5, Д21.4.5, 21.5.3, 21.5.4, Д21.5.4, 21.6.4, 22.3.6, 22.7.1, 24.1.3, 24.6.2, 25.1.1, 25.3.1, 25.6.3, 26.2.5, 26.3.1, 26.8.7, 27.1.2, 27.3.1, 27.4.1, 27.6.2, 27.7.2, 27.7.7, 27.8.5, 28.3.2, 28.4.7, И31.7.4.
Конечная (аффинная) плоскость – это конечное множество, в котором выделен некоторый набор подмножеств так, что выполняются аксиомы A1, A2, A3 (см. ниже).
Используется язык из обычной геометрии: элементы плоскости называются точками, выделенные подмножества – прямыми, говорят: «точка лежит на прямой», «прямая проходит через точку», «точка пересечения двух прямых» и т. п. Прямые параллельны, если они сопадают или не пересекаются.
Аксиомы:
А1. Через любые две различные точки проходит ровно одна прямая.
А2. Через любую точку проходит ровно одна прямая, параллельная данной.
А3. Существуют три точки, не лежащие на одной прямой.
Пример конечной плоскости: множество из 4 точек, где прямыми объявлены все двухэлементные множества.
Рассматривая пучки параллельных прямых и их пересечения, нетрудно вывести из аксиом следующие свойства конечной плоскости.
С1. На каждой прямой лежит одно и то же число точек.
Это число n называется порядком конечной плоскости.
С2. Всего на плоскости порядка n имеется n2 точек и n2 + n прямых.
С3. Через каждую точку проходит ровно n + 1 прямая.
С4. Все прямые разбиваются на n + 1 пучков параллельных прямых. Каждый пучок содержит n прямых.
Конечные плоскости часто используются для построения примеров (см. 26.8.7).
К сожалению, не для каждого натурального n существует плоскость порядка n. Например, не существует плоскости порядка 6; неизвестно, существует ли плоскость порядка 10.
Зато известно, что существуют плоскости порядков pk для любой пары из простого p и натурального k. Плоскость порядка p построить легко: объявим ее точками пары (x, y), а прямые задаются уравнениями y kx + b (mod p) и x b (mod p), все целые числа x, y, k, b могут принимать значения от 0 до p – 1.
Задачи: 26.8.7.
см. Шахматы.
см. Шахматы.
Кость игральная – кубик, на гранях которого нанесены числа от 1 до 6, обычно в виде точек. На стандартной игральной кости сумма чисел на каждой паре противоположных граней равна 7, но используют и нестандартные кости.
Задачи: 19.7.3, Д19.7.3, 21.6.2.
Из n целых чисел всегда можно выбрать несколько (возможно, одно) с суммой, кратной n.
Действительно, пусть исходные числа a1, a2, …, an. Рассмотрим числа S0 = 0,
Sk = a1+ …+ ak. (k = 1, 2, ..., n). Этих чисел больше, чем вариантов остатка от деления на n, поэтому (по принципу Дирихле) найдутся два числа Si и Sj (i < j) с одинаковыми остатками. Тогда их разность кратна n и является искомой суммой: Sj – Si = ai+1 + … + aj.
Задачи: 24.3.6.
Если у поверхности есть плоская развертка (например, у выпуклого многогранника, конуса, цилиндра), то кратчайший путь между двумя точками на поверхности будет отрезком на одной из разверток.
Покажем это для выпуклых многогранников.
1) Ясно, что путь по каждой грани – отрезок, поэтому путь на поверхности (и на каждой развертке) – ломаная.
2) Заметим, что грань не может содержать два звена ломаной. В противном случае, соединив две точки на разных звеньях, мы заменим ломаную в пространстве на отрезок и сократим путь.
3) Заметим, что кратчайший путь не может проходить через вершину (но может начинаться и/или кончаться в вершинах).
Действительно, пусть участок пути ABC проходит через вершину B (точки A и C достаточно близки к B). От AB к CB по поверхности многогранника можно пройти в двух направлениях. В одном из этих направлений сумма плоских углов при вершине B меньше 180 (см. неравенство для многогранных углов в теме Неравенства в геометрии).
Развернем на плоскости грани, которые проходятся на в этом направлении, и соединим точки A и C на этой развертке отрезком. Вернувшись на поверхность многогранника мы получим более короткий путь между A и C, чем ABC.
4) Построим развертку, прикладывая на плоскости грани друг к другу в порядке прохождения по ним кратчайшего пути, (грани, на которые путь не заходит, приклеим к ней произвольно). Докажем, что на этой развертке кратчайший путь представляет собой отрезок.
Предположим противное: путь имеет излом в точке D. Ясно, что D – внутренняя точка некоторого ребра. Но тогда путь можно сократить, соединив отрезком две близкие к D точки, точки, лежащие по разные стороны от этого ребра. Противоречие.
Замечание 1. Отрезок, соединяющий данные точки M и N на какой-нибудь развертке, не обязан быть кратчайшим путем. Чтобы найти кратчайший путь нужно рассмотреть все возможные развертки.
Существование кратчайшего пути
Выше доказано, строго говоря, только утверждение «Если кратчайший путь существует, то на некоторой развертке он прямой.»
Существование кратчайшего пути в школьных учебниках не доказывается, а в вузовских моментально следует из теоремы о компактности. Восполним этот пробел и дадим элементарное доказательство для выпуклого многогранника.
Данную пару точек A и B на поверхности выпуклого многогранника будем соединять ломаной, у которой вершины лежат на ребрах, а на каждой грани лежит не более одного звена. Зафиксируем для такой ломаной цепочку граней в порядке следования. Можно считать, что у соседних граней цепочки всегда есть общее ребро (если нет, а только общая вершина, исправим цепочку добавлением нескольких граней с той же общей вершиной, как бы обходя «вокруг угла». Эта цепочка однозначно задает плоскую развертку этих граней: она получается последовательным присоединением граней друг к другу по соответствующему ребру. Пространственная ломаная развернется в плоскую, при этом, возможно, углы при некоторых ее вершинах станут развернутыми. Назвем такие вершины правильными. Вершину ломаной, совпадающую с вершиной грани (на которой лежит соответствующее звено), назовем жесткой. Ломаную AB на данной развертке назовем хорошей, если каждая ее вершина (кроме конечных) правильная или жесткая. Нетрудно видеть, что число хороших ломаных конечно: хорошая ломаная задается положениями жестких вершин, а положений – конечное число.
Докажем, что при фиксированной цепочке каждая ломаная не короче некоторой хорошей. Отметим на ломаной концы, а также жесткие и неправильные вершины. Пусть есть плохая (то есть неправильная нежесткая) вершина C на ребре l.
Рис. 4
Пойдя от C по ломаной в обе стороны, найдем ближайшие к C отмеченные вершины D и E. Будем двигать точку C по ребру l внутрь угла DCE, следя, чтобы ломаная DCE не вышла за пределы развертки. Мы либо превратим ломаную DCE в отрезок DE (и тогда вершина C станет правильной), либо ломаная пройдет через вершину грани (и тогда некоторая вершина G на фрагменте DCE станет жесткой).
В обоих случаях сумма длин звеньев CD + CE станет меньше. Найдем следующую плохую вершину и повторим операцию. На каждом шаге у нас исчезает плохая вершина или появляется новая жесткая вершина. Так как старые жесткие вершины не исчезают, то процесс появления новых закончится, после чего постепенно исчезнут все плохие вершины.
Осталось заметить, что общее число хороших ломаных конечно: число цепочек конечно, а для каждой цепочки хорошая ломаная задается положениями жестких вершин, число которых тоже конечно. По доказанному выше самая короткая из списка хороших ломаных и даст нам кратчайший путь.
Задачи: 25.3.6.
см. Правильные многогранники.