Комбинаторика олимпиаднику
 Скачать 0.51 Mb.
|
|
686 8. (Ломоносов, 2012, 7 ) Сколько чисел из набора 1, 2, . . . , 2010, 2011 не делятся ни на 3, ни на 7? 1149 9. (Физтех, 2014, 7, 8, 10 ) На столе рубашкой вверх была разложена колода из 36 игральных карт. Лёша перевернул 30 карт, затем Макс перевернул 19 карта после этого Боря — 21 карту. В результате вся колода оказалась рубашкой вниз. Сколько карт было перевёрнуто трижды 10. (Физтех, 2013, 8–9 ) Трое ребят принялись красить лист ватмана, каждый — в свой цвет. Один закрасил красным 75% листа, второй закрасил зелёным 70% листа, а третий закрасил синим 65% листа. Сколько процентов листа будет заведомо закрашено всеми тремя цветами. (Ломоносов, 2013, 9 ) Найдите количество натуральных делителей числа N = 1 00 . . . а) не являющихся ниточными квадратами (те. квадратами натуральных чисел, ниточными кубами б) не представимых в виде m n , где m и n — натуральные числа, причём n > 1. а)1093; б)981 48 12. (Высшая проба, 2014, 10 ) В группе 17 человек знают английский язык, 14 человек знают китайский язык, 20 человек знают арабский языки человек знают польский язык. При этом человека в группе знают ровно один язык из перечисленных, а остальные — ровно два языка из перечисленных. Сколько человек в группе 13. (Высшая проба, 2014, 11 ) В группе 15 человек знают английский язык, 16 человек знают китайский язык, 20 человек знают арабский языки человек знает польский язык. В группе нет людей, знающих три языка, и 23 человека в группе знают ровно два языка из перечисленных. Сколько человек в группе знают ровно один язык из перечисленных 14. (Высшая проба, 2013, 11 ) В стране шесть городов А, Б, В, Г, Д и Е. Их хотят связать пятью авиалиниями так, чтобы из каждого города можно было (возможно, с пересадками) долететь до любого другого. Сколькими различными способами это можно сделать 15. (Олимпиада ВШЭ, 2011, 9 ) В классе 20 учеников, каждый из которых дружит ровно с шестью одноклассниками. Найдите число таких различных компаний из трёх учеников, что в них либо все школьники дружат друг с другом, либо каждый не дружит ни с одним из двух оставшихся 16. (Олимпиада ВШЭ, 2011, 11 ) Класс из 20 учеников разделён на две половины так, что каждый школьник из первой половины дружит ровно с шестью одноклассниками, а каждый школьник из второй половины дружит ровно с четырьмя одноклассниками. Найдите число таких различных компаний из трёх учеников, что в них либо все школьники дружат друг с другом, либо каждый не дружит ни с одним из двух оставшихся 17. (Физтех, 2014, 11 ) Прямоугольный параллелепипед 35 × 40 × 56, разбитый на единичных кубиков, проткнули иглой по его диагонали. Сколько единичных кубиков протыкает игла 18. (Покори Воробьёвы горы, 2014, 7–9 ) Уходя на работу, мама поручила Мише, Пете и Васе: а) подмести пол в прихожей б) помыть посуду в) купить хлеба г) заплатить за электричество; д) вынести мусоре) пропылесосить ковёр в гостиной. Сколькими различными способами они могут распределить задания так, чтобы каждое задание делал кто-то один из ребят и при условии, чтобы каждый что-нибудь делал 49 Разные комбинаторные приёмы В данном разделе рассмотрены два приёма решения комбинаторных задач — подсчёт двумя способами и составление рекуррентных соотношений. 6.1 Подсчёт двумя способами В некоторых задачах можно получить нужное уравнение, если вычислить двумя способами одну и туже величину. Трудность состоит в том, чтобы додуматься — какую именно величину подсчитывать двумя способами. Задача. Тридцать школьников — семиклассников и восьмиклассников — обменялись рукопожатиями. При этом оказалось, что каждый семиклассник пожал руку восьми восьмиклассникам, а каждый восьмиклассник пожал руку семи семиклассникам. Сколько было семиклассников и сколько восьмиклассников? Решение. Пусть x — число семиклассников, y — число восьмиклассников тогда x + y = Второе уравнение мы получим, если подсчитаем двумя способами общее количество рукопожатий. С одной стороны, число рукопожатий равно 8x, поскольку от каждого семиклассника «исходит» 8 рукопожатий. С другой стороны, число рукопожатий равно 7y, так как от каждого восьмиклассника исходит 7 рукопожатий. Следовательно, 8x = 7y. Решая полученную систему уравнений, находим x = 14, y = Задача. (Турнир Ломоносова, 1985 ) Было 7 пустых ящиков. В некоторые из них положили еще по 7 пустых ящиков и т. д. В итоге стало 10 непустых ящиков. Сколько всего стало ящиков? Решение. Если ящик A лежит непосредственно в ящике B, то будем говорить, что из ящика в ящик B идёт стрелка. Пусть всего стало x ящиков. Подсчитаем двумя способами общее количество стрелок. С одной стороны, оно равно x − 7, поскольку из каждого ящика, кроме начальных семи, выходит ровно одна стрелка. С другой стороны, число стрелок равно 10·7 = поскольку в каждый из 10 непустых ящиков входит ровно 7 стрелок (а нив какой пустой ящик стрелка не входит. Следовательно, x − 7 = 70, откуда x = Данную задачу можно решить и по-другому. На каждом шаге процесса заполняется ровно один ящик — в него кладутся 7 ящиков. Поскольку вначале все ящики пусты, сделано 10 шагов, то есть добавлено 70 ящиков. Плюс семь начальных — итого 77 ящиков. 6.2 Рекуррентные соотношения Говорят, что последовательность a 1 , a 2 , . . . , a n , . . . задана рекуррентно, если существует формула, выражающая й член этой последовательности через один или несколько предыдущих членов такая формула называется рекуррентным соотношением. Например, рекуррентное соотношение a n+1 = a n + 3 с начальным условием a 1 = 2 задаёт арифметическую прогрессию 2, 5, 8, 11, . . Задача. (Физтех, 2014, 8–9 ) На доску выписаны числа a 1 , a 2 , . . . , a 200 . Известно, что a 1 = 3, a 2 = 9. Найдите a 200 , если для любого натурального n справедливо равенство a n+2 = a n+1 − a Решение. Начнём выписывать члены нашей последовательности 3, a 2 = 9, a 3 = 6, a 4 = −3, a 5 = −9, a 6 = −6, a 7 = 3, a 8 = Как видим, последовательность зацикливается — она периодична с периодом 6 (то есть a n+6 = a n ). Иными словами, равны все члены последовательности, номера которых дают при делении на 6 одинаковые остатки. Номер 200 имеет остаток 2 отделения на 6. Значит a 2 = 9. 50 Некоторые задачи комбинаторики можно решить, если составить для искомой величины рекуррентное соотношение, после чего вычислить эту величину вплоть до нужного значения Посмотрим, как это делается. Задача. Сколько существует строк длины 10, состоящих из нулей и единиц, таких, что никакие два нуля не стоят рядом? Решение. Говоря в решении этой задачи о строках, мы имеем ввиду строки, описанные в условии, то есть составленные из нулей и единиц так, что никакие два нуля не стоят рядом. Обозначим через x число строк длины n. Ясно, что x 1 = 2 (это строки 0 и 1), x 2 = 3 (это строки 01, 10 и 11). Будем искать рекуррентное соотношение, задающее последовательность x Предположим, что n > 3. Пусть N 1 — число строк длины n, которые начинаются с единицы. Вторым числом такой строки может быть либо 0, либо 1; иными словами, к первой цифре пристыковывается любая строка длины n − 1. Поэтому строк, начинающихся с единицы, столько же, сколько существует строк длины n − 1, то есть N 1 = x Пусть теперь N 0 — число строк длины n, которые начинаются с нуля. Вторым числом такой строки обязательно служит единица, а к этой единице уже пристыковывается любая строка длины n − 2. Поэтому N 0 = x В результате получаем n = N 1 + N 0 = x n−1 + x n−2 (n > Теперь с учётом начальных условий x 1 = 2, x 2 = 3 находим x 2 + x 1 = 5; x 4 = x 3 + x 2 = 8; x 5 = x 4 + x 3 = итак далее вплоть до интересующего нас значения x 10 = 144. Таким образом, строк длины получается Заметим, что полученная последовательность 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . . . — это знаменитые числа Фибоначчи. Задача. Сколько слов длины 5 можно составить из букв a, b итак, чтобы буквы a и b не стояли рядом? Решение. Пусть x n — число слов длины n (описанных в условии. Ясно, что x 1 = 3 (это слова a, b и c). Если n = 2, то всевозможные слова суть aa, ac, bb, bc, ca, cb, cc; таким образом, x 2 = Обозначим a n , b и c число слов длины n, начинающихся с буквы a, b и c соответственно. Тогда, очевидно n = a n + b n + c Предположим, что n > 3. Пусть слово длины n начинается с буквы a. Поскольку на втором месте не может быть b, к букве a пристыковывается любое слово длины n − 1, начинающееся с a или c. Поэтому a n = a n−1 + c Аналогично n = b n−1 + c n−1 , (12) c n = a n−1 + b n−1 + c n−1 = x Сложим ( 11 ) и ( 12 ), после чего используем ( 13 ): a n + b n = (a n−1 + b n−1 + c n−1 ) + c n−1 = x n−1 + c n−1 = x n−1 + x Подставляем это в ( 10 ): x n = x n−1 + x n−2 + c n = x n−1 + x n−2 + x n−1 = 2x n−1 + x n−2 51 Итак, имеем рекуррентное соотношение n = 2x n−1 + x n−2 (n > 3; x 1 = 3, x 2 = Последовательно вычисляем x 3 = 17, x 4 = 41 и, наконец, x 5 = 99. Итак, слов длины получается Задача. Шеренга солдат называется неправильной, если никакие три подряд стоящих солдата не стоят по росту (нив порядке возрастания, нив порядке убывания. Сколько неправильных шеренг можно построить из n солдат разного роста? Решение. Случаи n = 4 и n = 5 предлагались в качестве задачи к разделу 1 (е можно решить перебором вариантов. Сейчас мы рассмотрим данную задачу в общем виде. Пусть x n — число неправильных шеренг длины n. Как ив предыдущих задачах, ищем рекуррентное соотношение для x Рассмотрим неправильную шеренгу длины n + 1 (n > 1). Пусть Z — самый высокий солдат шеренги. Он может стоять на любом месте от 1 до n + 1 (перечисляем солдат слева направо). Предположим, что Z стоит нам месте (k = 0, 1, . . . , n); то есть, слева отстоят солдат (которых можно выбрать C k способами, а справа отстоят оставшиеся n − k солдат. Заметим, что слева отстоит неправильная шеренга длины k, ноне произвольная, а такая, у которой предпоследний солдат X выше последнего солдата Y (в противном случае солдаты, Y и Z окажутся стоящими по росту. Ясно, что таких шеренг вдвое меньше общего числа неправильных шеренг длины k; стало быть, слева от Z можно выстроить x k /2 шеренг. Чтобы это было справедливо при k = 0 и k = 1 (одна шеренга в обоих случаях, мы полагаем x 0 = x 1 = Аналогично, справа отстоит неправильная шеренга длины n − k, ноне произвольная, а такая, у которой второй солдат выше первого. Таких шеренг будет x n−k /2. Остаётся заметить, что k солдат слева от Z можно выбрать C k способами (и при каждом таком способе однозначно выбраны n − k солдат справа от Z). Таким образом, если Z стоит нам месте, то число неправильных шеренг будет равно n · x k 2 · x n−k 2 = 1 4 C k n x k x Суммируя по k, находим число неправильных шеренг длины n + 1: x n+1 = 1 4 n X k=0 C k n x k x n−k (n = 1, 2, . . . ; x 0 = x 1 = Читатель может самостоятельно убедиться, что выполнены равенства x 4 = 10 и x 5 = 32 это результат задачи 11 раздела Задачи. (Физтех, 2013, 8–11 ) В большую коробку положили 10 коробок поменьше. В некоторые из них положили 10 коробок ещё поменьше. В некоторые из этих последних коробок положили коробок ещё меньшего размера итак далее. В результате оказалось, что имеется ровно коробок, в которых что-то лежит. Какое наибольшее число коробок могут при этом быть пустыми 2. (Турнир им. Ломоносова, 1985 ) В классе каждый мальчик дружит ровно с двумя девочками, а каждая девочка — ровно стремя мальчиками. Еще известно, что в классе 31 пионер и 19 парт. Сколько человек в этом классе 52 3. (Математический праздник, 1996, 7 ) По кругу расставлены цифры 1, 2, 3, . . . , 9 в произвольном порядке. Каждые три цифры, стоящие подряд почасовой стрелке, образуют трёхзначное число. Найдите сумму всех девяти таких чисел. Зависит ли она от порядка, в котором записаны цифры? 4995;не зависит. (Математический праздник, 1996, 7 ) Футбольный мяч сшит из 32 лоскутков белых шестиугольников и чёрных пятиугольников. Каждый чёрный лоскут граничит только с белыми, а каждый белый — стремя чёрными и тремя белыми. Сколько лоскутков белого цвета 5. (Математический праздник, 1998, 7 ) В банановой республике прошли выборы в парламент, в котором участвовали все жители. Все голосовавшие за партию Мандарин любят мандарины. Среди голосовавших за другие партии 90% не любят мандарины. Сколько процентов голосов набрала партия Мандарин на выборах, если ровно 46% жителей любят мандарины. (Физтех, 2014, 7–8 ) Олег с папой пошли в тир. Они договорились, что Олег делает шесть выстрелов и за каждое попадание в цель получает право сделать ещё два выстрела. Всего Олег сделал 20 выстрелов. Сколько раз он попал в цель 7. (Физтех, 2014, 7–8 ) У Царя Гороха было четверо сыновей, а дочерей не было. Его потомки тоже не имели дочерей, среди них 25 имели каждый потри сына, ау остальных вообще не было детей. Сколько потомков было у царя Гороха 8. (Турнир городов, 2013, 8–9 ) Про группу из пяти человек известно, что Алёша на 1 год старше Алексеева, Боря на 2 года старше Борисова, Вася на 3 года старше Васильева, Гриша на 4 года старше Григорьева, а ещё в этой группе есть Дима и Дмитриев. Кто старше и насколько Дима или Дмитриев? Дмитриевст аршеДимы налет. (Всеросс., 2012, II этап, 11 ) Туристическая фирма провела акцию Купи путёвку в Египет, приведи четырёх друзей, которые также купят путёвку, и получи стоимость путёвки обратно». За время действия акции 13 покупателей пришли сами, остальных привели друзья. Некоторые из них привели ровно по 4 новых клиента, а остальные 100 не привели никого. Сколько туристов отправились в Страну Пирамид бесплатно 10. (Физтех, 2014, 10–11 ) Последовательность a такова, что a 1 = 4, a 2 = 25. Найдите если для любого натурального n справедливо равенство a n+1 = a n · a n+2 25 53 11. Сколько семибуквенных слов можно составить из букв a итак, чтобы после буквы a стояла хотя бы одна буква b? (Букве a разрешается быть последней 12. Сколько имеется разбиений отрезка длины 8 на отрезки длины 1, 2 и 3? (Разбиения, отличающиеся порядком следования отрезков, считаются различными 13. (Ломоносов, 2014, 10–11 ) Первоклассница Маша, заходя в школу, каждый раз поднимается на школьное крыльцо по лестнице, имеющей 9 ступенек. Находясь внизу лестницы или на очередной её ступеньке, она может либо подняться наследующую ступеньку, либо перепрыгнуть через одну ступеньку вверх (перепрыгнуть через две или более ступенек Маша пока не может. Какое минимальное количество раз Маше нужно зайти в школу, чтобы подняться на крыльцо всеми возможными способами 14. (Покори Воробьёвы горы, 2012, 7–8 ) Мария Ивановна — строгая учительница по алгебре. Она ставит в журнал только двойки, тройки и четвёрки, причём никогда не ставит одному ученику две двойки подряд. Известно, что она поставила Вовочке 6 оценок за четверть. Сколькими различными способами она могла это сделать 15. (Физтех, 2014, 11 ) Кузнечик прыгает по вершинам правильного треугольника прыгая каждый разв одну из соседних вершин. Сколькими способами он может попасть из вершины A обратно в вершину A за 9 прыжков 16. (Покори Воробьёвы горы, 2011, 9–11 ) Имеются 12 карандашей попарно различной длины. Сколькими способами можно уложить их в коробку в два слоя по шесть карандашей так, чтобы в каждом слое карандаши были упорядочены по возрастанию длины (слева направо, а каждый карандаш верхнего слоя лежал строго над карандашом нижнего слоя и был короче его 17. (Высшая проба, 2014, 11 ) На клетчатой доске размером 2 × n клеток некоторые клетки закрашиваются в чёрный цвет. Раскраска называется правильной, если среди закрашенных нет двух соседних клеток (соседними называются клетки, имеющие общую сторону. Раскраска, в которой ни одна клетка не закрашена, тоже считается правильной. Пусть A n — количество правильных раскрасок сч тным числом закрашенных клеток, количество правильных раскрасок с нечётным числом закрашенных клеток. Найдите всевозможные значения A n − B n ±1 54 |