Комбинаторика олимпиаднику
 Скачать 0.51 Mb.
|
|
Задача. На подносе лежат 5 яблоки груши. Сколькими способами можно выбрать фрукт с подноса? Решение. Яблоко можно выбрать пятью способами. Грушу можно выбрать тремя способами. Стало быть, один из этих фруктов можно выбрать 5 + 3 = 8 способами. Задача. На полке стоят десять томов Пушкина, четыре тома Лермонтова и шесть томов Гоголя. Сколькими способами можно выбрать с полки одну книгу? Решение. Понятно, что 10 + 4 + 6 = 20 способами. Правило суммы. Пусть объект a можно выбрать m способами, а объект b можно выбрать n способами, причём выбор одного объекта исключает одновременный выбор другого объекта. Тогда выбор либо a, либо b» можно сделать m + n способами. Более общим образом, пусть объект можно выбрать способами, объект можно выбрать способами, . . . , объект a можно выбрать n способами, причём выбор одного объекта исключает одновременный выбор другого объекта. Тогда выбор либо a 1 , либо a 2 , . . . , либо a можно осуществить n 1 + n 2 + . . . + n k способами. Правило суммы отражает тот очевидный факт, что число элементов в объединении попарно непересекающихся множеств равно сумме числа элементов в каждом из множеств. Так, впервой задаче множество яблок (Я) состоит из пяти элементов, а множество груш (Г) состоит из трёх элементов эти множества не пересекаются, так что множество фруктов (ЯГ) состоит из 5 + элементов. Аналогично, во второй задаче множество ПЛ Г (обозначения очевидны) состоит из 10+4+6 элементов. Соответственно, имеем вторую (эквивалентную) формулировку правила суммы. Правило суммы в терминах множеств. Пусть множество A состоит из m элементов, а множество состоит из n элементов, причём множества A и B не пересекаются. Тогда множество ∪ B состоит из m + n элементов. Более общим образом, пусть множество состоит из элементов, множество состоит из элементов, . . . , множество A k состоит из n элементов, и множества A 1 , A 2 , . . . , A k попарно не пересекаются. Тогда множество A 1 ∪ A 2 ∪ . . . ∪ A k состоит из n 1 + n 2 + . . . + n k элементов. 3.2 Правило произведения При решении комбинаторных задач часто приходится умножать число способов выбора одного объекта на число способов выбора другого объекта. Рассмотрим некоторые примеры. Задача. Имеются три города A, B и C. Изв ведут три дороги, изв пять дорог. Сколько различных путей ведут изв Прямого пути между A и C нет. Решение. Обозначим дороги буквами и цифрами. Именно, дороги изв назовём a, b, дороги изв назовём 1, 2, 3, 4, 5. 12 A B C a b c 1 2 3 Тогда любой маршрут изв получает уникальное имя в виде пары из буквы и цифры. Например, маршрут b4 означает, что из A и B мы пошли по дороге b, а изв по дороге Выпишем все такие пары в виде таблицы: a1 a2 a3 a4 a5 b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 Всего получилось 3 · 5 = 15 маршрутов. Как видим, число маршрутов равно произведению числа дорог изв на число дорог изв Задача. В магазине есть 7 видов пиджаков, 5 видов брюки вида галстуков. Сколькими способами можно купить комплект из пиджака, брюки галстука? Решение. Предположим, что пиджак уже выбран (это можно сделать 7 способами. К пиджаку выбираем брюки 5 способами. Итого пару (пиджак, брюки) можно выбрать 7 · 5 способами. К этой паре можно купить галстук 4 способами. Следовательно, для покупки пиджака, брюки галстука имеется 7 · 5 · 4 = 140 способов. Задача. Сколько существует пятизначных чисел, у которых все цифры чётные? Решение. Представим себе пять последовательных позиций для цифр пятизначного числа. На первую позицию можно поставить четыре цифры 2, 4, 6 или 8. На вторую позицию можно поставить пять цифр 0, 2, 4, 6 или 8. На третью, четвёртую и пятую позиции можно поставить те же пять цифр 0, 2, 4, 6 или 8. Всего имеем 4 · 5 · 5 · 5 · 5 = 2500 вариантов заполнения позиций; именно столько и будет искомых чисел. Вы уже, несомненно, уловили суть второго правила комбинаторики — правила произведения. Остаётся дать его строгую формулировку. Правило произведения. Пусть объект a можно выбрать m способами, после чего объект b можно выбрать n способами. Тогда упорядоченную пару (a, b) можно выбрать mn способами; иными словами, существует mn различных упорядоченных пар (a, Более общим образом, пусть объект можно выбрать способами, после чего объект можно выбрать способами, . . . , после чего объект a можно выбрать n способами. Тогда цепочку (a 1 , a 2 , . . . , a k ) можно выбрать n 1 n 2 . . . n способами иными словами, существует n 1 n 2 . . . n цепочек (a 1 , a 2 , . . . , a Задача. Сколько подмножеству элементного множества У n-элементного? Решение. Пусть имеется множество из 5 элементов A = {a 1 , a 2 , a 3 , a 4 , a 5 }. Каждому его подмножеству можно дать уникальное имя в виде упорядоченной пятёрки нулей и единиц последующему правилу если на й позиции пятёрки стоит единица, то a i ∈ B; если жена й позиции пятёрки стоит нуль, то a i / ∈ Например, пятёрка 10010 обозначает подмножество {a 1 , a 4 }. Пятёрки 00000 и 11111 обозначают соответственно пустое множество и само множество Таким образом, у множества A имеется ровно столько подмножеств, сколько существует упорядоченных пятёрок из нулей и единиц. Каждую позицию пятёрки можно заполнить двумя способами (0 или 1), поэтому таких пятёрок 2 · 2 · 2 · 2 · 2 = 2 5 = 32. Это и есть число подмножеств 5-элементного множества. Для элементного множества рассуждение аналогично. Каждое его подмножество получает уникальное имя (потому же правилу) в виде цепочки длины n, состоящей из нулей и единиц. Всего таких цепочек 2 n . Следовательно, число всех подмножеств элементного множества равно Задача. (Размещения с повторениями) Сколькими способами можно разложить m различных шаров в n различных ящиков На число шаров в ящике ограничений нет. Решение. Представим себе m клеток (это шары. В каждую клетку можно вписать любое число от 1 до n (номер ящика, в который кладётся шар. Всего получится n всевозможных способов заполнить клетки, то есть разложить шары по ящикам. Число разложений m различных шаров по n различным ящикам (без ограничений на число шаров в ящике) называется иногда числом размещений с повторениями из n пои обозначается. Таким образом, ¯ A m n = n m . О более содержательном понятии — числе размещений (без повторений) — речь пойдёт в следующем разделе. Задача. Сколько делителей у числа Решение. Разложим на простые множители 720 = 2 4 · 3 2 · 5. Следовательно, всякий делитель числа 720 должен иметь вид 2 a · 3 b · 5 c , где a ∈ {0, 1, 2, 3, 4}, b ∈ {0, 1, 2}, c ∈ {0, 1}. Мы видим, что каждому делителю соответствует единственная упорядоченная тройка (a, b, c) и наоборот каждой упорядоченной тройке (a, b, c) с элементами изданных множеств отвечает единственный делитель числа 720. Можно сказать, что (a, b, c) — это уникальное имя делителя, и потому делителей будет ровно столько же, сколько получится упорядоченных троек (a, b, Но число a можно выбрать 5 способами, число b можно выбрать 3 способами, число c можно выбрать 2 способами значит, упорядоченную тройку (a, b, c) можно выбрать 5 · 3 · 2 = способами. Таким образом, у числа 720 имеется 30 делителей. Решение последней задачи можно обобщить и найти количество делителей произвольного натурального числа, представленного своим разложением на простые множители. Задача. Пусть p 1 , p 2 , . . . , p n — различные простые числа k 1 , k 2 , . . . , k n — целые неотрицательные числа. Сколько делителей у числа a = p k 1 1 p k 2 2 . . . p k n Решение. Каждый делитель числа a имеет вид p m 1 1 p m 2 2 . . . p m n n , где целые числа m 1 , m 2 , . . . , m удовлетворяют условиям 0 6 m 1 6 k 1 , 0 6 m 2 6 k 2 , . . . , 0 6 m n 6 k n . Следовательно, цепочка (m 1 , m 2 , . . . , m n ) есть уникальное имя делителя, и потому делителей будет столько же, сколько получится цепочек (m 1 , m 2 , . . . , m n ). Первый элемент этой цепочки можно выбрать k 1 + 1 способами, второй элемент k 2 + 1 способами, . . . , й элемент k n + 1 способами. Значит, всего имеется (k 1 + 1)(k 2 + 1) . . . (k n + 1) делителей числа В комбинаторной задаче могут использоваться также факты, связанные с делимостью. Задача. (Физтех, 2013, 9–11 ) Сколько пар натуральных чисел (x, y) удовлетворяют равенству НОД(x, y) + НОК(x, y) = Решение. Напомним для начала некоторые простые факты касательно НОД и НОК. Они наверняка пригодятся вам на олимпиадах. Пусть НОД(x, y) = d. Тогда x = ad и y = bd для некоторых натуральных a и b. При этом числа a и b являются взаимно простыми (то есть не имеют общих делителей, кроме 1). В самом деле, если у a и b есть общий делитель c > 1, то число cd будет общим делителем чисел x и Но это противоречит тому, что d — наибольший общий делитель этих чисел. Пусть z есть общее кратное чисел x и y (необязательно наименьшее. Поскольку z делится на x и на y, имеем z = kx = kad и z = my = mbd для некоторых натуральных k и m. Отсюда kad = mbd, то есть ka = mb; но так как a и b взаимно просты, то m делится на a: m = na для некоторого натурального n. Следовательно, z = nabd, откуда видно, что наименьшее общее кратное получается при n = 1: НОК(x, y) = Заметим попутно, что НОД(x, y) · НОК(x, y) = d · abd = ad · bd = xy. Мы доказали тем самым известный факт произведение НОД и НОК двух чисел равно произведению этих чисел. Теперь переходим к решению задачи. Имеем = d + abd = d(1 + Отсюда следует, что 2011 делится на 1 + ab > 1. Однако 2011 — простое число (убедитесь в этом самостоятельно, поэтому единственным его делителем, большим единицы, может быть лишь оно само 1 + ab = 2011, откуда ab = 2010. Тогда d = 1, то есть x = a и y = Задача свелась к следующему вопросу сколько пар натуральных чисел (a, b) удовлетворяют равенству ab = 2010? Из этого равенства b однозначно определяется по a; поэтому фактически нам надо выяснить, сколько делителей a имеется у числа Для этого раскладываем 2010 на простые множители 2010 = 2 · 3 · 5 · 67. Дальнейшее рассуждение вам уже знакомо каждый делитель числа 2010 имеет вид 2 p · 3 q · 5 r · 67 s , где числа p, q, r, s могут принимать значения 0 или 1. Поэтому количество делителей числа 2010 равно · 2 · 2 · 2 = 16. Это и есть искомое число пар (x, Часто в задачах работают одновременно оба правила — суммы и произведения. Задача. Сколько трёхзначных чисел содержат ровно одну цифру Решение. Единственная цифра 7 может стоять либо на первом месте, либо на втором, либо на третьем. Соответственно находим количества чисел в каждом из этих случаев, после чего пользуемся правилом суммы. Найдём количество n 1 трёхзначных чисел, у которых единственная цифра 7 будет первой. На второй и третьей позициях может стоять любая из цифр, кроме 7; следовательно, вторую и третью позицию мы можем заполнить 9 · 9 = 81 способами. Итак, n 1 = Теперь найдём количество n 2 трёхзначных чисел, у которых единственная цифра 7 стоит на втором месте. Первая цифра может быть любой, кроме 0 и 7 (то есть 8 способов выбора). Вторая цифра — любая, кроме 7 (это 9 способов. Следовательно, n 2 = 8 · 9 = Аналогично находим количество n 3 трёхзначных чисел, у которых единственная цифра стоит на третьем месте n 3 = 8 · 9 = По правилу суммы искомое количество чисел равно n 1 + n 2 + n 3 = 81 + 72 + 72 = Задача. (Высшая проба, 2014, 8 ) Сколько существует способов расставить на шахматной доске 8 × 8 белую ладью и чёрного короля так, чтобы ладья била короля, но король не бил ладью Способы расстановки, получающиеся друг из друга поворотом доски, считаются раз- ными. Решение. Где бы ни стояла на доске ладья, она держит подбоем ровно 14 клеток — 7 по горизонтали и 7 по вертикали. Если король стоит в углу доски (таких клеток 4), тов своих горизонтали и вертикали он бьёт две клетки. Значит, ладью можно поставить на 12 клеток (рисунок слева Если король стоит на краю доски, ноне в углу (таких клеток 24), тов своих горизонтали и вертикали он бьёт три клетки. Значит, ладью можно поставить на 11 клеток (рисунок в центре). Если же король стоит не на краю доски (таких клеток 36), тов своих горизонтали и вертикали он бьёт четыре клетки. В этом случае ладью можно поставить на 10 клеток (рисунок справа). Всего требуемых расстановок короля и ладьи получается · 12 + 24 · 11 + 36 · 10 = Задачи. (Ломоносов, 2016, 5–8 ) В правильном угольнике ABCDEF G провели диагонали AC, AF , BD, BG, CF , DF и а) Раскрасьте вершины угольника в красный, синий и зелёный цвета так, чтобы любые две вершины, соединённые отрезком, были раскрашены в разные цвета. б) Найдите количество вариантов такой раскраски. б)6 2. (Покори Воробьёвы горы, 2016, 5–6 ) Найдите количество пар натуральных чисел (x, y), 1 6 x, y 6 1000, таких, что x 2 + делится на 5 нацело 3. (Математический праздник, 1998, 6 ) На глобусе проведены 17 параллелей и 24 меридиана. На сколько частей разделена поверхность глобуса Меридиан — это дуга, соединяющая Северный полюс с Южным. Параллель — это окружность, параллельная экватору (экватор тоже является параллелью 4. (Математический праздник, 1996, 6 ) Каких пятизначных чисел больше не делящихся на или тех, у которых ни первая, ни вторая цифра слева — не пятёрка? Поровну 5. (Всеросс., 2014, I этап, 7–9 ) Назовём число зеркальным, если слева направо оно читается также, как справа налево. Например, число 12321 — зеркальное. Сколько существует пятизначных зеркальных чисел, которые делятся на 5? 100 6. (Физтех, 2015, 7 ) Найдите количество четырёхзначных чисел, у которых третья цифра меньше четвёртой на 2. 720 7. (Всеросс., 2015, I этап, 10 ) На числовой прямой закрашивают красными синим цветом точки с целыми координатами последующим правилам а) точки, разность координат которых равна 7, должны быть покрашены одним цветом б) точки с координатами 20 и 14 должны быть покрашены красным, а точки с координатами 71 и 143 — синим. Сколькими способами можно раскрасить все целые числа, соблюдая эти правила 16 8. (Ломоносов, 2012, 7 ) Города A, B, C и D соединены дорогами так, как показано на рисунке. A B C D Сколькими способами можно проделать путь из города A в город D, побывав в каждом городе ровно по одному разу 9. (Ломоносов, 2015, 7 ) Таблицу размера 3 × 3 надо заполнить числами 2014, 2015 итак, чтобы сумма чисел в каждой строке была одинаковой. Сколькими различными способами можно это сделать 10. (Покори Воробьёвы горы, 2016, 7–9 ) Сколькими способами можно разместить числа 1, 2, 3, 4, 5, 6, 7, 8 ив девяти клетках фигуры, изобра- жённой на рисунке, так, чтобы сумма чисел в каждом столбце, начиная со второго, была на 1 больше, чем в предыдущем 11. (Покори Воробьёвы горы, 2015, 7–8 ) Пин-код телефона состоит из 4 цифр (и может начинаться с нуля, например, 0951). Петя называет счастливыми такие пин-коды, у которых сумма крайних цифр равна сумме средних, например 1357: 1 + 7 = 3 + 5. В своём телефоне он использует только счастливые пин-коды. Петя говорит, что даже если забудет одну цифру (но будет помнить её позицию, то он легкое восстановит. А если он забудет две цифры (но будет помнить их позиции, то ему придется перебрать лишь небольшое количество пин-кодов. а) Сколько пин-кодов придется перебрать Пете в худшем случае? б) Сколько существует всего счастливых пин-кодов? а)10; б)670 12. (Высшая проба, 2014, 8 ) Сколько существует способов расставить на шахматной доске × 8 белого слона и чёрного короля так, чтобы слон бил короля, но король не бил слона 13. (Высшая проба, 2014, 9 ) Из множества {1, 2, 3, 4} выбираются три натуральных числа a, b, c (необязательно различных. Сколько существует способов сделать это так, чтобы число a (b делилось на 4? 28 14. (Покори Воробьёвы горы, 2011, 11 ) Сколько существует четырёхзначных чисел, делящихся на 4, в десятичной записи которых нет цифр 4, 5, 6, 8? 180 17 15. (Ломоносов, 2013, 7 ) Сколькими различными способами шахматный король может пройти с поляна поле h5, если ему разрешается ходить только на одну клетку вправо, вверх или по диагонали вправо вверх 16. (Ломоносов, 2013, 8 ) Сколькими различными способами шахматный ферзь может пройти с поляна поле h8, если ему разрешается ходить только вправо, вверх или по диагонали вправо вверх на любое число клеток 17. (Ломоносов, 2013, 8 ) Найдите количество девятизначных чисел, в которых каждая цифра от 1 до 9 встречается ровно один раз, цифры 1, 2, 3, 4, 5 расположены в порядке возрастания, а цифра 6 стоит раньше цифры 1 (например, 916238457). 504 18. (Ломоносов, 2015, 8–9 ) В некоторой стране алфавит состоит из трёх букв МГ и У. Словом называется любая состоящая из этих букв конечная последовательность, в которой две согласные не могут стоять рядом и две гласные не могут стоять рядом. Сколько в этой стране состоящих из 200 букв слов, которые содержат каждую из трёх букв хотя бы по разу 101 −4 19. (Ломоносов, 2013, 9 ) Сколькими различными способами можно выбрать целые числа a, b, c ∈ [1; 100] так, чтобы точки с координатами A(−1, a), B(0, b) и C(1, c) образовывали прямоугольный треугольник 20. (Физтех, 2014, 7–8 ) Сколько различных натуральных делителей у числа 15552? 42 21. (Высшая проба, 2013, 8, 10 ) Сколько различных делителей у числа 999 999 ? 2998000 22. (Физтех, 2014, 9–11 ) Натуральное число имеет ровно два простых делителя. Его квадрат имеет 51 различны натуральных делителей. Какое наибольшее количество различных натуральных делителей может иметь куб этого числа 23. (Ломоносова) Сколько натуральных делителей имеет число N = 1 00 . . . б) Найдите количество натуральных делителей числа N , не являющихся точными квадратами (те. квадратами натуральных чисел). а)10000; б)7500 18 24. (Покори Воробьёвы горы, 2012, 7–9 ) Найдите количество натуральных чисел, которые делятся на 2012 и имеют, не считая единицы и самого этого числа, ровно 2199 различных делителей 25. (Покори Воробьёвы горы, 2015, 9 ) Число 2015 можно представить в виде суммы последовательных целых чисел различным образом, например 2015 = 1007+1008 или 2015 = 401+402+ +403 + 404 + 405. Сколькими способами это можно сделать 26. (Физтех, 2012, 9–11 ) Какое количество натуральных чисел a обладает следующим свойством Наименьшее общее кратное чисел 16, 50 и a равняется 1200»? |