Сборник материалов выездных школ команды Москвы на Всероссийскую математическую олимпиаду
 Скачать 3.42 Mb.
|
|
(невидимых ребер нет. Возможны ли такие многогранники? в) При каких условиях на точки E и F внутри выпуклого четырехугольника данный рисунок может быть видом сверху некоторого многогранника? См. также http://www.turgor.ru/lktg/2001/skewline/lines/zip , Подсчет по частям. Углы, отрезки... 255 A B C D E F а б http://www.turgor.ru/lktg/2001/skewline/lines/zip , http://www.turgor.ru/lktg/2004/lines.en/index.htm , http://www.turgor.ru/lktg/2004/lines.en/index.htm Подсчет по частям. Углы, отрезки. (А. А. Гаврилюк 1. Правильный многоугольник A 1 A 2 . . . A n вписан в окружность радиуса с центром в точке O, M — произвольная точка плоскости. Докажите, что A 1 M 2 + A 2 M 2 + . . . + A n M 2 = n(R 2 + OM 2 ). 2. Диагонали вписанного четырехугольника ABCD пересекаются в точке E. Пусть O 1 — центр окружности, вписанной в треугольник, O 2 — центр окружности, вписанной в треугольник ABD. Докажите, что прямая отсекает от треугольника ABE равнобедренный треугольник. Пусть P и Q — середины сторон AB и CD четырехугольника M и N — середины диагоналей AC и BD. Докажите, что если прямые M N и P Q перпендикулярны, то длины отрезков BC и AD равны. Четыре окружности расположены так, что каждая касается внешним образом двух других. Каждая из этих окружностей касается внутренним образом пятой окружности в точках A, B, C, D. Докажите, что AB · CD = BC · DA. 5. Высоты AA 1 , и остроугольного треугольника продолжены до пересечения c описанной около этого треугольника окружностью в точках A 2 , и соответственно. Докажите, что 4. Гл. 9. Разные задачи по геометрии. Дан вписанный четырехугольник ABCD. Докажите, что центры окружностей, вписанных в треугольники ABD, ABC, BCD и ACD, являются вершинами прямоугольника. На плоскости даны прямая l и треугольник ABC по одну сторону от нее. Пусть A 1 , и C 1 — точки, симметричные A, B и C относительно. Через точку проведена прямая, параллельная BC, через точку прямая, параллельная AC, через точку C 1 — прямая, параллельная. Докажите, что три построенные прямые пересекаются водной точке. Геометрический винегрет (А. А. Гаврилюк 1. Назовем выпуклый многоугольник константным, если суммы расстояний от точки внутри него до прямых, содержащих стороны постоянна. Докажите, что многоугольник A 1 A 2 . . . A n константен тогда и только тогда, когда A 1 A 2 A 1 A 2 + . . . + # A n A 1 A n A 1 = # 0 . 2. На сторонах BC, CA и AB треугольника так взяты точки A 1 , соответственно, что отрезки AA 1 , и пересекаются водной точке. Пусть M — проекция точки на B 1 C 1 . Докажите, что M биссектриса угла BM C. 3. Дан угол с вершиной A. На одной из его сторон взяты точки и B 1 , на другой — точки C итак, что отрезки BC и пересекаются в точке K. В окружности, описанной около треугольника проведена хорда AD, параллельная B 1 C 1 , а в окружности, описанной около треугольника AB 1 C 1 , проведена хорда AD 1 , параллельная Докажите, что точки D, и K лежат на одной прямой. Диагонали выпуклого четырехугольника ABCD пересекаются в точке M , ∠AM D = 120 ◦ , AM = M D. На стороне BC взята произвольная точка E, а на сторонах AB и CD — соответственно точки итак, что KE k AC и EP k BD. Докажите, что центр окружности, описанной около треугольника KEP , лежит на стороне AD. 5. Дан параллелограмм ABCD (∠BAD — острый. Биссектриса угла BAD пересекает сторону CD в точке L, а прямую BC — в точке. Пусть O — центр окружности, описанной около треугольника Докажите, что точки D, B, C и O лежат на одной окружности. Через точку M, лежащую внутри окружности, проведены 4 различные хорды A k B k , где k = 1, 2, 3, 4. Докажите, что точка P пересече- Геометрический винегрет 257 ния прямых и A 3 A 4 , точка Q пересечения прямых и а также точка M лежат на одной прямой. Прямая, проходящая через центр вписанной в треугольник окружности, пересекает стороны AC ив точках E и F . Докажите, что CE + CF > 4BC · AC AB + BC + CA 8. Пусть ABCD — выпуклый четырехугольник S AB , S BC , S CD , S DA — окружности, построенные на сторонах AB, BC, CD и DA соответственно как на диаметрах. Известно, что окружность касается окружности S CD , а окружность касается окружности Докажите, что ABCD — ромб. Дан выпуклый пятиугольник ABCDE, в котором AB = BC, ∠ C = ∠A = 90 ◦ . Внутри него выбрана точка X так, что AX ⊥ BE, CX ⊥ BD. Докажите, что BX ⊥ DE. 10. Дан треугольник ABC, все углы которого выражаются целым числом градусов и отличны от 45 ◦ , 90 ◦ , 135 ◦ . Точки A 1 , B 1 , C 1 — основания его высот, точки A 2 , B 2 , C 2 — основания высот треугольника, и т. д. Докажите, что среди треугольников A n B n C n бесконечно много подобных между собой. В остроугольном треугольнике ABC проведены высоты и CD. Различные точки F и G на стороне AC таковы, что DF k и EG k AB. Докажите, что четырехугольник DEF G — вписанный. В выпуклом пятиугольнике ABCDE AB = BC, ∠ ABE + ∠DBC = и ∠AEB + ∠BCD = Докажите, что ортоцентр треугольника BDE лежит на диагонали AC. 13. На сторонах AB и BC треугольника ABC выбраны такие точки и L соответственно, что ∠KCB = ∠LAB = α. Из точки B опущены перпендикуляры BD и BE на прямые AL и CK соответственно. Точка — середина стороны AC. Найдите углы треугольника DEF . 14. Вокруг остроугольного треугольника ABC описана окружность. Высоты треугольника из вершин A и C пересекают окружность в точках E и F соответственно, D — произвольная точка на (меньшей) дуге AC, K — точка пресечения DF и AB, L — точка пересечения и BC. Докажите, что прямая KL проходит через ортоцентр треугольника. В треугольнике ABC проведены чевианы AA 1 , BB 1 , CC 1 , пересекающиеся в точке O. Докажите, что O лежит внутри серединного треугольника для A 1 B 1 C 1 Часть III КОМБИНАТОРИКА ГЛАВА ПОДСЧЕТЫ В КОМБИНАТОРИКЕ Подсчеты числа способов (А. А. Гаврилюк Данный раздел не требует никаких знаний и подходит для первого знакомства с комбинаторикой. Сто человек сидят за круглым столом, причем более половины из них — мужчины. Докажите, что какие-то двое из мужчин сидят друг напротив друга. а) Назовем натуральное число симпатичным, если в его записи встречаются только четные цифры. Сколько существует пятизначных симпатичных чисел? б) Сколько существует шестизначных чисел, в записи которых есть хотя бы одна четная цифра? в) Каких семизначных чисел больше тех, в записи которых есть единица, или остальных. Имеется 2k + 1 карточек, занумерованных числами от 1 до 2k + Какое наибольшее число карточек можно выбрать так, чтобы ни один из извлеченных номеров не был равен сумме двух других извлеченных номеров. Из двух математиков и десяти экономистов надо составить комиссию из восьми человек. Сколькими способами можно составить комиссию, если в нее должен входить хотя бы один математик. Найдите сумму всех семизначных чисел, которые можно получить всевозможными перестановками цифра) На двух клетках шахматной доски стоят черный и белый короли. За один ход можно пойти любым королем (короли дружат, так что могут стоять на соседних клетках, ноне водной и той же. Могут ли в результате их передвижений встретиться всевозможные варианты расположения этих королей, причем ровно по одному разу? б) Тот же вопрос, если короли разучились ходить по диагонали. Зачетные задачи все Гл. 10. Подсчеты в комбинаторике Подсчеты с подмножествами (ДА. Пермяков. Сколькими способами множество из n элементов можно разбить на 2 множества. Сколько различных неупорядоченных пар непересекающихся подмножеств найдется для множества из n элементов. Во скольких подмножествах множества {1, 2, 3, . . . , 11} не найдется двух подряд идущих чисел. Во скольких подмножествах множества {1, 2, 3, . . . , 11} не найдется трех подряд идущих чисел. Рассмотрим всевозможные непустые подмножества множества, 2, . . . , N}, не содержащие подряд идущих чисел. Для каждого подмножества вычислим произведение его элементов. Докажите, что сумма квадратов этих произведений равна (N + 1)! − 1. 6. Из цифр 1, 2, 3, . . . , 9 составлены все четырехзначные числа, не содержащие повторяющихся цифр. Найдите сумму этих чисел. Найдите сумму всех четырехзначных чисел, не содержащих повторяющихся цифр. Зачетные задачи все, кроме любой одной. Решения 1. Разбиение множества на два подмножества будем считать выбором некоторого подмножества и его дополнения. Выбирая подмножество, мы можем каждый элемент либо взять в него, либо не взять. Значит, всего способов выбрать подмножество равняется 2 n . Но каждое разбиение мы посчитали дважды первый — выбирая одно подмножество как основное, а второе как дополнение, и второй раз, выбирая второе подмножество как основное, а первое — как дополнение. Следовательно, всего разбиений 2 n−1 2. Посчитаем сначала количество способов выбрать упорядоченную пару непересекающихся подмножеств. Для каждого элемента есть три варианта он попадает либо в первое подмножество, либо во второе, либо нив одно из них. Значит, всего упорядоченных пар 3 n . Неупорядоченной паре из двух пустых подмножеств соответствует одна упорядоченная пара из пустых подмножеств. Любой другой неупорядоченной паре соответствует две упорядоченные пары подмножеств. Значит, всего неупорядоченных пар (3 n + 1)/2. Наборы подмножеств 3. Пусть A n — количество подмножеств множества {1, 2, . . . , n}, не содержащих двух подряд идущих чисел. Количество таких подмножеств, не содержащих число n, равняется A n−1 , так как в этом случае подмножества являются также подмножествами в {1, 2, . . . , n − Количество таких подмножеств, содержащих число n, равняется так как в этом случае подмножества при выкидывании числа n становятся подмножествами в {1, 2, . . . , n − 2}. Получаем равенство A n = = A n−1 + A n−2 . Очевидно, A 1 = 1 и A 2 = 1. Осталось вычислить последовательно. Получаем A 11 = Наборы подмножеств (ДА. Пермяков. Дядька Черномор каждый вечер назначает на дежурство 9 или из своих 33 богатырей. Через какое наименьшее число дней может оказаться, что все богатыри выходили на дежурство одинаковое число раз. В классе 33 человека. У каждого ученика спросили, сколько у него в классе тезок и сколько однофамильцев (включая родственников). Оказалось, что среди названных чисел встретились все целые от 0 до включительно. Докажите, что в классе есть два ученика с одинаковыми именем и фамилией. Какое максимальное число попарно пересекающихся подмножеств можно выбрать в множестве из 100 элементов. Дано 2007 множеств, каждое из которых содержит ровно по элементов. Известно, что любые два из этих множеств имеют ровно один общий элемент. Докажите, что существует элемент, принадлежащий каждому из 2007 множеств. В множестве, состоящем из 100 элементов, выбрали несколько различных трехэлементных подмножеств. Докажите, что если выбрано подмножество, то среди них найдутся два, имеющие ровно один общий элемент. В стране провели анкету, в которой требовалось назвать своего любимого писателя, художника и композитора. Оказалось, что каждый упомянутый хоть раз деятель искусств является любимым для не более чем k человек. Докажите, что всех проанкетированных можно разделить на не более чем 3k − 2 группы, чтобы в каждой группе любые два человека имели абсолютно разные вкусы. Зачетные задачи все, кроме любого одного пункта Гл. 10. Подсчеты в комбинаторике Решения 1. Ответ 7. Пусть m > 0 дней дежурят по 9 богатырей и n > 0 дней по 10. Тогда число 9m + 10n делится на 33. Перебором возможных значений числа n показывается, что уравнение 9m + 10n = 33 не имеет решений в целых неотрицательных числах. Для уравнения 9m + 10n = = 66 находим решение m = 4, n = 3. Легко построить пример, когда богатыри действительно могут продежурить задней ровно по 2 раза. Если же 9m + 10n > 99, то m + n > 99/10 > 7. Значит, минимальное число дней равно 7. 3. Ответ 2 99 . Всего подмножеств 2 100 . Разобьем все множества на пары каждому множеству поставим в пару его дополнение. Тогда всего будет 2 пари из каждой пары мы можем выбрать не более одного множества. Чтобы найти 2 попарно пересекающихся подмножеств, достаточно взять все подмножества, содержащие некоторый фиксированный элемент. Формула включения-исключения (ДА. Пермяков Данный раздел посвящен доказательству и использованию формулы включения-исключения. Эта формула позволяет отвечать на основной вопрос главы Сколько существует объектов сданными свойствами?» во многих непростых случаях. Перед решением задач этого раздела нужны базовые навыки решения задач комбинаторики. Например, полезно прорешать разделы Подсчеты числа способов и Наборы подмножеств Обозначим через C k количество способов выбрать k элементов из некоторых n различных элементов (без учета порядка. Иными словами, это количество элементных подмножеств элементного множества, или количество слов длины n из букв Аи Б, в которых ровно k букв А. Числа C k называются биномиальными коэффициентами. Можно доказать равенство C k n = n! k!(n − k)! , нов задачах этого раздела это не понадобится. В ответах на задачи этого раздела разрешается использовать биномиальные коэффициенты. а) Сколькими способами можно переставить числа от 1 до n, чтобы и 1, и 2 оказались не на своих местах? б) Сколькими способами можно переставить числа от 1 до n, чтобы ровно одно из чисел 1, 2 и 3 оказалось на своем месте? в) Сколькими способами можно переставить числа от 1 до n, чтобы каждое из чисел 1, 2 и 3 оказалось не на своем месте Формула включения-исключения 265 г) Сколькими способами можно переставить числа от 1 до n, чтобы каждое из чисел 1, 2, 3 и 4 оказалось не на своем месте. а) Найдите сумму всех 6-значных чисел, получаемых при всех перестановках цифр 4, 5, 5, 6, 6, б) Найдите сумму всех 10-значных чисел, получаемых при всех перестановках цифра) Дано множество A и его подмножества A 1 , A 2 , A 3 . Докажите, что количество элементов вне принадлежащих ни одному из, равняется |A| − |A 1 | − |A 2 | − |A 3 | + |A 1 ∩ A 2 | + |A 2 ∩ A 3 | + |A 1 ∩ A 3 | − − |A 1 ∩A 2 ∩A 3 |. Здесь через |A i | обозначается количество элементов в A i б) Дано множество A и его подмножества A 1 , A 2 , A 3 , A 4 . Обозначим через S k сумму k 6 4 |A i 1 ∩ . . . ∩ A i k |. Докажите, что количество элементов вне принадлежащих ни одному из A i , равняется − S 1 + S 2 − S 3 + в) В условиях пункта б) докажите, что количество элементов, принадлежащих ровно одному из множеств A i , равняется C 1 1 S 1 − C 1 2 S 2 + + C 1 3 S 3 − C 1 4 S 4 4. а) Тому Сойеру сказали покрасить забор из 8 досок в белый цвет. В силу своей лени, он покрасит не более 3 досок. Сколько у него способов это сделать? В хорошем настроении он может покрасить даже не более 5 досок. Сколько у него способов? А за обещанный десерт он может покрасить любое количество досок. Сколько у него способов? б) Докажите формулу C 0 n + C 1 n + . . . + C n n = 2 n 5. а) Докажите, что в любом непустом множестве количество подмножеств из четного числа элементов равно количеству подмножеств из нечетного числа элементов. Другими словами, верна формула C 1 n + C 2 n − . . . + (−1) n C n n = б) Докажите равенство C k n C r k = C r n C k−r n−r 6. Формула включения-исключения. Пусть имеется множество из N элементов и n его подмножеств A 1 , . . . , A n . Обозначим через число элементов в множестве A i 1 ∩ A i 2 ∩ . . . ∩ A i k . Пусть и S k = X 16i 1 <...6 n N i 1 ,...,i где 1 6 k 6 Пусть N (=r) — число элементов, принадлежащих ровно r подмножествам. Докажите, что справедливы следующие формулы k S k Гл. 10. Подсчеты в комбинаторике Замечание. Если число N i 1 ,...,i зависит только от k и не зависит от набора индексов, то S k = C k n N 1,...,k 7. По кругу стоят n различных предметов. Докажите, что число способов выбрать k из них, чтобы никакие два выбранных не стояли рядом, равняется n n − k C k n−k 8. Используя предыдущую задачу, найдите число способов рассадить пар враждующих рыцарей за круглый стол с нумерованными местами, чтобы никакие два враждующих рыцаря не сидели рядом. Куб с ребром длины 20 разбит на 8000 единичных кубиков, и в каждом кубике записано число. Известно, что в каждом столбике из кубиков, параллельном ребру куба, сумма чисел равна 1 (рассматриваются столбики всех трех направлений. В некотором кубике записано число 10. Через этот кубик проходит три слоя 1 × 20 × 20, параллельных граням куба. Найдите сумму всех чисел вне этих слоев. Зачетные задачи 1 б)–г); 2 б 3 б, в 5 б Решения. а) Всего имеется n! способов переставить наши числа. Вычтем из них (n − 1)! способов перестановки, при которых число 1 остается на месте. Вычтем также (n − 1)! способов перестановки, при которых число 2 остается на месте. При этом (n − 2)! способов перестановки, при которых оба числа 1 и 2 остаются на месте, мы вычли дважды. Значит, число (n − 2)! нужно добавить, чтобы в итоге мы эти способы посчитали раз. Получаем ответа) Узнаем, сколько всего чисел мы складываем. Шесть цифр можно расставить вряд способами. Но при этом неотличимы способы, отличающиеся перестановкой шестерок между собой и пятерок между собой. Значит, всего чисел · 2! = 60. Каждая цифра будет встречаться во всех разрядах равное число раз. Четверка встретится всего 60 раз, значит в каждом разряде по 10 раз. Пятерка всего раз, значит в каждом разряде по 20 раз. Шестерка всего раз, значит в каждом разряде по 30 раз. Сумма цифр в каждом разряде равна 4 · 10 + 5 · 20 + 6 · 30 = 320. Значит, сумма всех чисел равна 320 · 111111. 4. а) Если Том красит не более трех досок, то он может покрасить, 1, 2 или 3 доски. Он может это сделать 8 + C 1 8 + C 2 8 + C 3 8 = 93 Комбинаторика классов эквивалентности 267 способами. Аналогично не более 5 досок можно покрасить 8 + C 1 8 + C 2 8 + C 3 8 + C 4 8 + C 5 8 = способами, а произвольное число досок 8 + C 1 8 + C 2 8 + C 3 8 + C 4 8 + C 5 8 + C 6 8 + C 7 8 + C 8 8 = 256 способами. Можно решить задачу проще. Каждую из 8 досок Том либо красит, либо нет. Значит, у него всего 2 8 способов. б) Посчитаем количество подмножеств элементного множества. В нем элементных подмножеств ровно C i n , значит, всего подмножеств+ C 1 n + C 2 n + . . . + C n n . С другой стороны, выбирая подмножество, мы можем каждый элемент либо взять в подмножество, либо не взять. Значит, всего подмножеств 2 n , откуда получаем требуемое равенство. а) Выделим в множестве какой-нибудь элемент. Каждому подмножеству, содержащему выделенный элемент, поставим в пару подмножество, отличающееся от исходного удалением выделенного элемента. При этом все подмножества разобьются на пары, причем в каждой паре одно четное подмножество, а другое нечетное. Комбинаторика классов эквивалентности 1) (9–11) А. Б. Скопенков 1. Сколькими способами можно раскрасить грани куба в красный и серый цвета Раскраски, совмещающиеся в (трехмерном) пространстве, считаются одинаковыми. Найдите число раскрасок карусели из n вагончиков в a цветов (т.е. количество раскрасок вершин правильного угольника в a цветов, если раскраски, совмещающиеся поворотом, неотличимы) для а) n = б) n = в) n = 6. 3*. Найдите число замкнутых ориентированных связных ломаных с вершинами в вершинах данного правильного угольника (где p простое. Ломаные, совмещающиеся поворотом, неотличимы. Решение задачи 2 в. Простой способ решения обычно придумывается и разбирается на занятиях. Аналогично этому способу можно решить задачу 2 для произвольного n, однако решение будет громоздким. Приведем более сложный для простых n, зато более простой для очень непростых n способна примере решения задачи 2 в). 1) Это обновленная версия части статьи Скопенков А. Олимпиады и математика Матем. просвещение. 2006. № 10. С. 57 – 63. Гл. 10. Подсчеты в комбинаторике Всего имеется раскрасок поезда из 6 вагончиков. Посчитаем двумя способами число P пар (α, s), в которых s ∈ {0, 1, 2, 3, 4, 5} и α раскраска поезда, переходящая в себя при циклическом сдвиге на s ва- гончиков. Циклический сдвиг на s переводит в себя ровно раскрасок поезда, поэтому P = a 6 + a + a 2 + a 3 + a 2 + С другой стороны, обозначим через X искомое число раскрасок, а через) наименьшую положительную величину циклического сдвига, при котором раскраска α поезда переходит в себя. Тогда число тех s ∈ ∈ {0, 1, 2, 3, 4, 5}, для которых циклический сдвиг на s вагончиков переводит раскраску α поезда в себя, равно 6/d(α). Поэтому поездам α 6/d(α) каруселям β d(β) · 6/d(β) = Здесь второе равенство выполнено, поскольку для раскрасок и поезда, переводящихся друг в друга циклическими сдвигами, d(α 1 ) = d(α 2 ) (эти равные числа обозначаются где β — соответствующая раскраска карусели количество раскрасок поезда, получающихся циклическими сдвигами изданной раскраски α поезда (те. дающих туже раскраску карусели, равно Итак, X = 1 6 (a 6 + 2a + 2a 2 + a 3 ). 4. Найдите число а) раскрасок карусели из n вагончиков в a цветов; |