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

Лемма 2. (Обратная теорема о вписанном угле). "Если угол равен половине дуги, на которую он опирается, то он вписанный". Строго говоря, если угол высекает на окружности дугу и равен половине этой дуги, то его вершина лежит на окружности.
Доказательство леммы 2: От противного: пусть угол AXB высекает на окружности дугу AB, ^AXB=AB/2 (здесь и далее под AB и CD будут пониматься не отрезки, а дуги), но X не лежит на окружности. Если X - внутри окружности, то мы имеем ситуацию как на рис. к лемме 1 слева. Тогда ^AXB=(AB+CD)/2>AB/2 (по лемме 1). Если же X - вне окружности, то ситуация как на рис. к лемме 1 справа. Здесь уже ^AXB=(AB-CD)/2<AB/2 (тоже по лемме 1). В обоих случаях - противоречие, ч. т.д.

Теперь доказательство уже элементарно. Пусть в четырехугольника ABCD, например, ^CAD=^CBD (см. рис. в начале параграфа). Опишем окружность вокруг треугольника BCD (вокруг любого треугольника можно описать окружность - этот факт тоже есть в школьном учебнике геометрии). Рассмотри дугу CD этой окружности. На нее опирается угол CBD, поэтому ^CBD=CD/2. Тогда и ^CAD=CD/2. Отсюда, по лемме 2, получаем, что A лежит на той же окружности. Т. о., ABCD вписанный, ч. т.д. (его описанная окружность, заметим, строится как описанная окружность треугольника из трех его вершин).

Примеры задач на счет углов:

Задача 7. В равнобедренном треугольнике ABC с углом 36 градусов при вершине A проведена биссектриса BK. Докажите, что BK=BC.
Решение: В треугольнике ABC угол A равен 36 градусов, ^B=^C, а сумма всех трех, конечно, 180 градусов. Поэтому ^B=^C=72, а ^ABK=^B/2=36 градусов. В треугольнике ABK: ^AKB=180-^BAK-^ABK=180-36-36=108 градусов (опять из суммы углов треугольника). Смежный с ним угол BKC равен 72 градуса. Тогда в треугольнике BCK ^BKC=^BCK=72 и поэтому он равнобедренный, то есть BK=BC, ч. т.д.

Задача 8. Две окружности пересекаются в точках A и B. C и D - диаметрально противоположные A точки на первой и второй окружностях соответственно Докажите, что B, C и D лежат на одной прямой.
Решение: Угол ABC вписан в первую окружность и опирается на ее диаметр, поэтому он прямой (диаметр ограничивает дугу в 180 градусов). А угол ABD тоже прямой, так как вписан во вторую окружность и опирается на ее диаметр. Тогда ^CBD=^ABC+^ABD=90+90=180 градусов. Поэтому B, C и D лежат на одной прямой, ч. т.д.
(!) Обратите внимание на стандартный метод доказательства того, что три точки лежат на одной прямой: доказать (т. е. посчитать), что какой-то угол, образованный этими тремя точками равен нулю или 180 градусов.

Задача 9. Две хорды, AC и BD, окружности S параллельны. Докажите, что AC=BD.
Решение: Четырехугольник ABDC вписанный, поэтому в нем равны пары углов, опирающихся на одну дугу. Например, ^BAD=^BCD и ^ABC=^ADC. Поскольку AB и CD параллельны, то равны накрест лежащие углы при пересечении их секущей: ^BAD=^ADC и ^ABC=^ADC. Тогда равны все четыре угла (на рис. они все обозначены одной дужкой). Поэтому треугольники ABX и CDX (X - точка пересечения AD и BC) равнобедренные, то есть AX=BX и CX=DX. Кроме того, смежные углы AXC и BXD равны, откуда получаем равенство треугольников ACX и BDX по двум сторонам и углу между ними. А раз треугольники равны, то AC=BD, ч. т.д.
(!) Какое-нибудь равенство, подобие или равнобедренность треугольников может сильно облегчить решение, особенно если его вовремя заметить ;-)

Задача 10. Точки K и L на сторонах AB и AC остроугольного треугольника ABC таковы, что KL||BC. Перпендикуляры к сторонам AB и AC в K и L соответственно пересекаются в M. Докажите, что A, M и центр O описанной окружности ABC лежат на одной прямой
Решение: Рассмотрим четырехугольник AKML. В нем два противоположных угла (AKM и ALM) - прямые, поэтому они в сумме дают 180 и AKML - вписанный. Поэтому в нем ^KAM=^KLM=^ALM-^ALK=90-^ALK. Из того, что KL||BC, получаем равенство соответственных углов ACB и ALK, то есть ^C (в треугольнике ABC) и ^ALK, откуда ^KAM=90-^C, то есть ^BAM=90-^C. Теперь рассмотрим центр O описанной окружности. ^ACB - вписанный и опирается на дугу AB, поэтому равен ее половине, то есть половине центрального угла AOB. Отсюда ^AOB=2^C. Кроме того, AO=BO=R (за R стандартно обозначается радиус описанной окружности), так что ^BAO=^ABO=(^BAO+^ABO)/2=(180-^AOB)/2=90-^C. Таким образом, ^BAM=^BAO, т. е. O и M лежат на одном луче, выходящем из A, ч. т.д.
(!) Еще один метод доказывать, что три точки лежат на одной прямой: доказать, что лучи, выходящие из одной из этих точек в направлении двух других, образуют равные углы с некоторой прямой (и, конечно, лежат по одну сторону от нее - в данном случае, по ту, где лежит треугольник ABC).

Лекция 2: Принцип Дирихле.

Формулировка: Если в n "клетках" сидят не менее n+1 "кроликов", то в какой-то из "клеток" сидят не менее 2-х "кроликов". (Термины "кролики" и "клетки" являются общепринятыми в математике и будут применяться в том числе и в данной лекции.)
Доказательство: Противоречие к формулировке звучит так: "в каждой клетке сидит не более одного кролика". Но тогда кроликов, очевидно, не больше, чем клеток?! Поэтому есть клетка, где кроликов не менее двух ч. т.д.

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

Различные усиления, обобщения и т. п.:

1. Если в n клетках сидят не более n-1 кроликов, то есть пустая клетка.
Также доказывается от противного (как и все последующие пункты): если пустой клетки нет, то в каждой клетке сидит хотя бы 1 кролик. Тогда кроликов не меньше, чем клеток?! Значит, пустая клетка есть, ч. т.д.

2. Если в n клетках сидят ровно n кроликов, то либо в каждой клетке сидит ровно один кролик, либо есть и пустая клетка, и клетка, в которой не менее 2-х кроликов.
Действительно, если не в каждой клетке сидит ровно 1 кролик, то либо (а) есть пустая клетка, либо (б) есть клетка, в которой не менее 2-х кроликов. В случае (а) у нас n кроликов оказываются рассаженными в n-1 клеток, поэтому, по принципу Дирихле, есть и клетка, в которой не менее 2-х кроликов ч. т.д. В случае (б) у нас не более n-2 оставшихся кроликов оказываются рассаженными в n-1 клеток, следовательно, по п.1, есть и пустая клетка ч. т.д.

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

3. Если в n клетках сидят не менее n*(k-1)+1 кроликов, то в какой-то из клеток сидят не менее k кроликов.
Действительно, если в каждой клетке сидит не более k-1 кролика, то во всех клетках сидит не более n*(k-1) кроликов, а их хотя бы на 1 больше?! ч. т.д.

4. Если в n клетках сидят не более n*(k+1)-1 кроликов, то в какой-то из клеток сидят не более k кроликов.
Действительно, если в каждой клетке сидит не менее k+1 кролика, то во всех клетках сидит не менее n*(k+1) кроликов, а их хотя бы на 1 меньше?! ч. т.д.

5. (Это утверждение обобщает принцип Дирихле на случай нецелого числа кроликов.) Если сумма n чисел равна S, то среди них есть число, не меньшее S/n, и число, не большее S/n.
Действительно, если все числа (строго!) меньше S/n, то их сумма меньше S, а если все числа (строго!) больше S/n, то их сумма больше S. В обоих случаях получаем противоречие ч. т.д.

(!) На принцип Дирихле при решении задач на олимпиаде можно прямо ссылаться, на обобщения и усиления - не рекомендуется. Легче подставить в нужное место решения доказательство соответствующего утверждения. Слова "принцип Дирихле" в таком случае можно вообще не упоминать ;-)

Примеры:

Задача 1. В мешке лежат шарики 2-х разных цветов (много белых и много черных). Какое наименьшее количество шариков надо на ощупь вынуть из мешка, чтобы среди них заведомо оказались два одного цвета.
Решение: 3 шарика. Это - просто применение принципа Дирихле: кроликами будут взятые шарики, а клетками - черный и белый цвета. Клеток две, поэтому если кроликов хотя бы три, то какие-то два попадут в одну клетку (будет 2 одноцветных шарика). С другой стороны, взять два шарика мало, потому что они могут быть двух разных цветов.

Задача 2. Дано 233 целых числа. Доказать, что разность каких-то двух из них делится на 232. (Принцип Дирихле часто используется и в задачах по теории чисел!)
Решение: У нас есть 233 числа, которые мы, скорее всего, сделаем кроликами. Найдем подходящие клетки: их должно быть не более 232, и разность 2-х чисел, "сидящих в одной клетке" должна делится на 232. Остатки от деления на 232 как раз подходят. Применяем принцип Дирихле для 233 кроликов-чисел и 232 клеток-остатков и получаем требуемое. (В теоретико-числовых задачах на Дирихле чаще всего клетками бывают остатки от деления чего-либо на какое-то число!)

Задача 3. В магазин привезли 25 ящиков яблок 3-х сортов (в каждом ящике все яблоки одного сорта). Доказать, что среди них есть, по крайней мере, 9 ящиков с яблоками одного сорта.
Решение: Возьмем ящики в качестве кроликов и сорта в качестве клеток. Тогда нам в точности подходит утверждение п.3 при n=3, k=9.

Задача 4. Пятеро программистов получили на всех зарплату - 1750 долларов. Каждый из них хочет купить себе новый компьютер за 360 долларов. Докажите, что кому-то из них это не светит.
Решение: Воспользуемся утверждением п.5 для n=5, S=1750. Тогда понятно, что зарплата одного из программистов не более S/n=350 долларов. Ему и не светит покупка.

Очень часто в задаче на принцип Дирихле нужны разные дополнительные соображения (либо он вообще появляется, как промежуточное соображение):

Примеры:

Задача 1. На олимпиаде 10 школьников решили в сумме 35 задач, причем среди них были решившие ровно одну, ровно две и ровно три задачи. Доказать, что кто-то из них решил не менее 5 задач.
Решение: (Стандартное соображение: если известно, что какие-то объекты есть, то есть хотя бы по одному экземпляру, который можно выделить и рассмотреть!) Возьмем одного школьника, решившего ровно одну задачу, одного, решившего ровно две и одного, решившего ровно три. Эти трое решили в сумме 6 задач. Остается еще 7 школьников, решивших в сумме 29 задач. Если взять задачи в качестве кроликов и школьников в качестве клеток, то получается в точности утверждение п.3 при n=7, k=5 ч. т.д.