Лекция 12: Графы - 2 (стр. 10 )

Задача 7. Сколько способов переплести 12 одинаковых книг в красные, зеленые или синие переплеты?
Решение: Опять нас выручает теория "шаров и перегородок": пусть 12 книг - это "шары", а 3 цвета переплетов - "ящики", по которым мы их раскладываем. Приходим к задаче 6 при n=12, k=3. В ответе будет C142=C1412.

Задача 8. Сколько способов разложить 7 белых и 2 черных шара по 9 различным ящикам?
Решение: Давайте посчитаем отдельно число раскладки белых и черных шаров. Для белых получаем C158=C157 (опять задача 6: n=7, k=9), а для черных C108=C102 (та же задача 6 при n=2, k=9). Так как одна раскладка от другой не зависит, то число вариантов надо перемножить. Ответ: C157*C102.

Задача 9. Общество из n человек выбирает председателя из своего состава. Сколько есть разных распределений голосов за различных кандидатов?
Решение: Пусть n голосов - это "шары", а n кандидатов - "ящики". Получаем ту же всенародно любимую :-) задачу 6 (на самом деле, задача 5 тоже нередко применяется), при k=n. А ответ тогда C2n-1n.

Лекция 6: Геометрия.

Неравенство треугольника.
Это неравенство - самое известное, самое главное и практически единственное геометрическое неравенство - в том смысле, что все неравенства в геометрии получаются как следствия неравенства треугольника. Данная лекция посвящена наиболее простым задачам подобного типа.

Формулировка: Длина любой стороны треугольника меньше суммы длин двух других сторон. (таким образом, для одного и того же треугольника, например, ABC - так мы будем стандартно обозначать треугольник - можно написать три разных неравенства треугольника: AB<AC+BC, AC<AB+BC, BC<AB+AC).
Доказательство: Докажем, например, что AB<AC+BC. На продолжении стороны AC за точку C отложим (см. рис. выше) отрезок CB', равный по длине CB. Тогда треугольник BB'C - равнобедренный, поэтому в нем равны углы B'BC и BB'C при основании (на рис. эти углы отмечены одной дужкой). Далее, ^BB'C=^B'BC<^ABC, т. к. является его частью (значком ^ мы обозначаем угол). В треугольнике против большего угла лежит большая сторона (и, конечно, против большей стороны лежит больший угол), поэтому в тр-нике ABB' AB<AB'. Но AB'=AC+CB'=AC+BC, поскольку CB' строился, как отрезок, равный по длине BC. Отсюда AB<AC+BC, ч. т.д.
Доказательство того, почему против большего угла в треугольнике лежит большая сторона, почему в равнобедренном треугольнике равны углы при основании и т. п. фактов желающие могут прочесть в школьном учебнике геометрии (например, "Геометрия 7-9" авторства Анатасяна, Бутузова и др. - общеизвестная желтенькая книжица :-).
Любители алгебраических неравенств могут подоказывать неравенство треугольника в координатах, как оно обычно доказывается в вузовском курсе матанализа.
Случай равенства: Неравенство треугольника также формулируется часто для трех произвольных точек плоскости, причем в этом случае оно будетнестрогим: "для любых трех точек A, B и C на плоскости AB<=AC+BC". В таком виде оно удобно, если мы не знаем, образуют ли три точки, к которым мы хотим применить неравенство, треугольник, или они лежат на одной прямой (в т. ч. и совпадают).
Следует заметить, что неравенство обращается в равенство только тогда, когда три точки лежат на одной прямой (т. е., не образуют треугольник). Точнее: AB=AC+BC тогда и только тогда, когда C лежит на отрезке AB (C - средняя из трех точек), возможно, совпадая с A или с B, в т. ч. и при A=B=C (в случае, когда средней является какая-то другая точка, неравенство все равно строгое).

Основные следствия.
1. Длина любой стороны треугольника больше разности длин двух других сторон (это означает, например, AB>|AC-BC|, т. е. разность считается по абсолютной величине). Соответственно, для любых трех точек на плоскости верно нестрогое неравенство вида AB>=|AC-BC|.
Доказывается этот факт совсем просто (например, что AC>|AB-BC|): По неравенству треугольника, мы имеем AC+BC>AB. Перенесем в другую часть и получим AC>AB-BC. Возьмем другое неравенство треугольника: AB+AC>BC и так же получим AC>BC-AB. Так как |AB-BC| - это либо AB-BC, либо BC-AB (смотря, что больше: AB или BC), то оно в любом случае меньше AC, ч. т.д. Для любых трех точек на плоскости доказательство точно такое же, только неравенство нестрогое.
2. Длина любой стороны треугольника меньше его полупериметра. Если же треугольник может быть вырожденным (это другое название для того, что три вершины в действительности не образуют треугольник), то верно нестрогое неравенство - только периметр вырожденного треугольника мы будем считать как сумму AB+AC+BC.
Здесь арифметики немного больше. К обычному неравенству треугольника (например, BC<AB+AC) прибавляем ту сторону, которая меньше суммы остальных. Получается 2BC<AB+AC+BC - в правой части стоит как раз периметр треугольника (обозначим его буквой P). Теперь поделим все на 2 и получим как раз BC<P/2, ч. т.д. (кстати, полупериметр стандартно обозначается буквой p). Доказательство опять же не меняется для вырожденного треугольника.
3. Кратчайший путь между двумя точками - это отрезок прямой.
Пусть A и B - две точки и они соединены какой-то ломаной AL1L2...LnB. Докажем, что эта ломаная длиннее отрезка AB. Посмотрим на треугольник AL1L2- в нем, по неравенству треугольника, AL2<AL1+L1L2, поэтому ломаная AL2...LnB (см. рис. внизу - то, что начинается с пунктирной линии) будет короче исходной (сплошные линии на том же рисунке). Применим к ней ту же операцию - и получим еще более короткую ломаную AL3...LnB (см. линию из точек на рис.). Многократно повторяя эту операцию, придем к ломаной ALnB. А она, по неравенству треугольника, длиннее отрезка AB, ч. т.д.
Мы доказали только почему любая ломаная длиннее прямой, но на самом деле это верно и для произвольной кривой, потому что любую кривую можно со сколь угодно высокой точностью приблизить ломаной. Но вдаваться в строгое обоснование этого процесса мы здесь не будем.

(!) Важно отметить, что последние три утверждения не просто следствия неравенства треугольника, а его равносильные переформулировки. То есть, доказательство этих утверждений можно проделать в обратную сторону (упражнение для любознательных читателей) - и из них вывести неравенство треугольника.

Алгебраическая комбинация.
Самый "дешевый и практичный" способ получения геометрических неравенств - это алгебраическая комбинация нескольких неравенств треугольника: умножить/разделить неравенство на какое-то число, поскаладывать несколько таких неравенств, подставить одно неравенство в другое и т. п. Геометрические соображения, напротив, практически не используются (ну, иногда надо бывает написать в формуле вместо одного отрезка другой - равный, заведомо больший или заведоио меньший, смотря по обстоятельствам). Типичные задачи на алгебраическую комбинацию - какие-нибудь красиво-симметричные, где фигурирует периметр или сумма длин диагоналей многоугольника.

Задача 1. Найти точку внутри выпуклого четырехугольника с минимальной суммой расстояний до вершин.
Решение: Пусть ABCD - четырехугольник, O - какая-то (произвольная) точка внутри (см. рис. внизу). Тогда искомая точка - та, где достигается минимум величины AO+BO+CO+DO. Теперь мы хотим оценить эту сумму снизу (т. е. найти какую-то заведомо не большую) по неравенству треугольника, причем желательно так, чтобы эта оценка обращалась в равенство в какой-то известной точке. Выражения вида AO+BO>=AB - явно не то, что нужно, т. к. из них обращается в равенство не более двух сразу. Попробуем сложить их по-другому: AO+CO>=AC, BO+DO>=BD. Первое неравенство обращается в равенство, если O лежит на диагонали AC, второе - если O на диагонали BD. Т. о., AO+BO+CO+DO>=AC+BD - и равенство достигается, если O - точка пересечения диагоналей (E на рис. внизу). Ответ: Искомая точка - это точка пересечения диагоналей.

(!) Для невыпуклого четырехугольника найти такую точку гораздо сложнее. Про поиск аналогичной точки для треугольника еще будет сказано ниже. Поиск подобной точки для пяти - и более угольника - безумно сложная задача, ответ в которой даже не имеет приличного вида.

Задача 2. Докажите, что сумма длин диагоналей выпуклого четырехугольника меньше его периметра.
Решение: Здесь нам хочется применить неравенства треугольника, оценивающие диагонали четырехугольника сверху, а стороны - снизу (т. е. стороны должны стоять в той части неравенства, которая больше, а диагонали - в той, которая меньше). Таких неравенств мы можем найти 4 штуки (для наглядности можно смотреть на рис. вверху): AC<AB+BC, AC<CD+AD, BD<BC+CD, BD<AD+AB. В левых частях этих неравенств каждая диагональ встречается по 2 раза. В правых частях - каждая сторона по 2 раза. Поэтому, если сложить все неравенства и поделить сумму на 2, то получим... AC+BD<AB+BC+CD+AD, ч. т.д.

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

Геометрические преобразования.
Мы уже выводили из неравенства треугольника, что кратчайший путь между точками - это отрезок прямой. Но что делать, если мы ищем не просто кратчайший путь, а кратчайший среди путей какого-то специального вида, среди которых нет прямолинейного??? Оказывается, и здесь обычно выручает то, что ломаная длиннее прямой. Надо искать геометрическое преобразование со следующими свойствами:
1.) оно не меняет длин путей (или, как минимум, переводит более длинный путь в более длинный, а более короткий - в более короткий);
2.) после преобразования интересующий нас путь может быть прямолинейным.
Теперь надо найти все пути (их может быть много!), переходящие при преобразовании в отрезок прямой. Они и будут кратчайшими.
В качестве преобразований хорошо подходят движения плоскости (симметрии, повороты, параллельные переносы), применяемые часто не ко всему пути, а к каким-то его кускам.