Олимпиадные задачи по комбинаторике. Задача о беспорядках
 Скачать 0.5 Mb.
|
|
И. В. Яковлев | Материалы по математике | MathUs.ru Комбинаторика — олимпиаднику Содержание 1 Перебор вариантов 3 1.1 Задачи 5 2 Цепочки и множества 7 2.1 Упорядоченные наборы 7 2.2 Неупорядоченные наборы 7 2.3 Операции над множествами 8 2.4 Задачи 9 3 Правила суммы и произведения 11 3.1 Правило суммы 11 3.2 Правило произведения 11 3.3 Задачи 15 4 Размещения, перестановки и сочетания 19 4.1 Размещения 19 4.2 Перестановки 19 4.3 Сочетания 20 4.4 Перестановки с повторениями 24 4.5 Сочетания с повторениями 25 4.6 Маршруты 27 4.7 Бином Ньютона 27 4.8 Три задачи о функциях 29 4.9 Задачи 30 5 Формула включений и исключений 37 5.1 Переход к дополнению 37 5.2 Формула включений и исключений 38 5.3 Задача о беспорядках 41 5.4 Функция Эйлера 42 5.5 Числа Стирлинга второго рода 43 5.6 Задачи 44 6 Разные комбинаторные приёмы 47 6.1 Подсчёт двумя способами 47 6.2 Рекуррентные соотношения 47 6.3 Задачи 49 1 Предисловие Настоящее пособие предназначено для школьников 8–11 классов, желающих научиться комби- наторике. В отличие от имеющейся литературы (например, [ 1 ]–[ 7 ]) данное пособие нацелено в первую очередь на подготовку к текущим олимпиадам; оно, в частности, содержит почти все 1 задачи по комбинаторике, предлагавшиеся на олимпиадах «Физтех», «Высшая проба», «Покори Воро- бьёвы горы!» и «Ломоносов» в 2011–2014 годах (больше всего комбинаторных задач встречается именно на этих олимпиадах, в особенности на их дистанционных этапах). Олимпиадные задачи публикуются с указанием названия олимпиады, года её проведения и классов, в которых задача предлагалась. В каждой задаче, где требуется получить число, приведён численный ответ без комбинаторной формулы (содержащей в себе подсказку); поэто- му, размышляя над задачами, читатель оказывается в условиях, максимально приближенных к олимпиадным (в частности, к условиям отборочных онлайн-туров, где в поле ответа нужно вписать число). Никаких предварительных знаний по комбинаторике у читателя не предполагается. Матери- ал изложен с нуля и достаточен для решения приведённых олимпиадных задач. Мы, однако, не ограничились необходимым минимумом и включили в пособие некоторые вопросы, выходящие за рамки традиционной олимпиадной тематики. Сюда относятся красивые приложения фор- мулы включений и исключений — задача о беспорядках, функция Эйлера и числа Стирлинга второго рода; эти разделы адресованы заинтересованному школьнику, стремящемуся расши- рить свой кругозор. Список литературы [1] Н. Я. Виленкин и др. Комбинаторика. М.: МЦНМО, 2013. [2] С. А. Генкин, И. В. Итенберг, Д. В. Фомин. Ленинградские математические кружки. Киров: «АСА», 1994. Главы «Комбинаторика-1» и «Комбинаторика-2». [3] Н. Б. Алфутова, А. В. Устинов. Алгебра и теория чисел. Сборник задач для математиче- ских школ. М.: МЦНМО, 2002. Глава 2. Комбинаторика. В свободном доступе: http://www.mccme.ru/free-books/pdf/alfutova.pdf [4] В. В. Прасолов. Задачи по алгебре, арифметике и анализу. М.: МЦНМО, 2007. Глава 14. Комбинаторика. В свободном доступе: ftp://ftp.mccme.ru/users/prasolov/algebra/algebra.pdf [5] В. В. Прасолов. Задачи по планиметрии. М.: МЦНМО, 2006. Глава 27, § 2. Комбинаторика. В свободном доступе: http://ilib.mccme.ru/pdf/planim5.pdf [6] В. В. Прасолов. Задачи по стереометрии. М.: МЦНМО, 2010. Глава 19, § 3. Комбинаторика. В свободном доступе: ftp://ftp.mccme.ru/users/prasolov/stereo/stereo.pdf [7] Сайт problems.ru , раздел « Комбинаторика ». 1 Исключены задачи параллельных вариантов, несущественно отличающиеся от данной задачи. 2 1 Перебор вариантов Основной вопрос комбинаторики — «сколько?», основная задача — подсчёт числа элементов конечного множества. В комбинаторных задачах нас обычно интересует, сколько комбинаций, удовлетворяющих тем или иным условиям, можно составить из заданного конечного набора объектов. В простейших случаях мы можем выписать все нужные нам комбинации и непосредственно подсчитать их. Однако при бессистемном выписывании легко упустить какую-то комбинацию или, наоборот, посчитать некоторую комбинацию дважды. Поэтому при переборе вариантов желательно придерживаться двух правил. 1. Обозначаем наши комбинации буквами или цифрами так, что каждая комбинация будет обозначена своей уникальной последовательностью букв или цифр. 2. Выписываем комбинации в алфавитном порядке (при обозначении буквами) или по воз- растанию чисел (при обозначении цифрами). При таком переборе ни один вариант не ускользнёт от нас и, с другой стороны, будет ис- ключена возможность повторения вариантов. Задача. Маша собирается съесть яблоко, сливу и мандарин, но пока не решила, в какой по- следовательности. Сколькими способами Маша может выбрать эту последовательность? Решение. Обозначаем буквами: Я — яблоко, С — слива, М — мандарин. Тогда, например, СМЯ — это вариант, когда Маша сначала съест сливу, потом — мандарин, потом — яблоко. Выпишем варианты в алфавитном порядке: МСЯ, МЯС, СМЯ, СЯМ, ЯМС, ЯСМ. Получилось 6 вариантов. Задача. Сколько существует четырёхзначных чисел, сумма цифр которых меньше 4? Решение. Здесь обозначать нечего — мы и так имеем дело с числами. Остаётся лишь выписать по возрастанию все четырёхзначные числа, сумма цифр которых равна 1, 2 или 3: 1000, 1001, 1002, 1010, 1011, 1020, 1100, 1101, 1110, 1200, 2000, 2001, 2010, 2100, 3000. Всего получилось 15 чисел. Задача. (Леонард Эйлер) Четыре гостя при входе в ресторан отдали швейцару свои шляпы, а при выходе получили их обратно. Невнимательный швейцар раздал шляпы случайным образом. Сколько существует вариантов, при которых каждый гость получил чужую шляпу? Решение. Занумеруем гостей цифрами 1, 2, 3, 4 и так же занумеруем их шляпы. Считаем, что шляпа с данным номером принадлежит гостю с этим же номером (то есть, например, шляпа 2 принадлежит гостю 2). Тогда каждый вариант получения шляп обозначается четырёхзначным числом, составлен- ным из цифр 1, 2, 3 и 4, в котором номер позиции цифры есть номер гостя, а сама цифра есть номер полученной им шляпы (номера позиций будем считать слева направо). Например, комбинация 4132 означает, что первый гость получил четвёртую шляпу, вто- рой — первую, третий — третью, а четвёртый — вторую. Такой вариант не годится по условию, поскольку третий получил свою шляпу. Теперь понятно, что нужно сделать — выписать по возрастанию все четырёхначные числа, содержащие по одной цифре 1, 2, 3 и 4, такие, что никакая цифра не стоит на позиции со своим номером. Эти числа выписаны ниже под чертой. Красные цифры над чертой — номер позиции (номер гостя), с которым не должна совпадать цифра в соответствующем столбце (номер шляпы). 3 1 2 3 4 2 1 4 3 2 3 4 1 2 4 1 3 3 1 4 2 3 4 1 2 3 4 2 1 4 1 2 3 4 3 1 2 4 3 2 1 Как видим, всего имеется 9 вариантов нужной раздачи шляп. Вариантов может быть довольно много, но в некоторых случаях, тем не менее, самый быст- рый способ решения задачи — разумно организованный перебор. Задача. («Высшая проба», 2013, 8 ) Сколько одночленов окажется в многочлене (1 + t 3 + t 6 + . . . + t 30 )(1 + t 5 + t 10 + . . . + t 30 ) после раскрытия скобок и приведения подобных членов? Решение. Раскроем скобки и (не приводя подобные члены) выпишем в таблицу все получа- ющиеся степени одночленов. Первая строка таблицы — это степени, получающиеся при умно- жении первого многочлена-сомножителя на первое слагаемое второго многочлена (равное 1); вторая строка — это степени, получающиеся при умножении первого многочлена на второе слагаемое второго многочлена (равное t 5 ), и т. д. 0 3 6 9 12 15 18 21 24 27 30 5 8 11 14 17 20 23 26 29 32 35 10 13 16 19 22 25 28 31 34 37 40 15 18 21 24 27 30 33 36 39 42 45 20 23 26 29 32 35 38 41 44 47 50 25 28 31 34 37 40 43 46 49 52 55 30 33 36 39 42 45 48 51 54 57 60 Всего в таблице 77 чисел, из них 24 входят в таблицу более одного раза (блоки повторяю- щихся чисел обведены рамкой). Следовательно, после приведения подобных членов получится 77 − 24 = 53 одночлена. В некоторых ситуациях не представляется возможным непосредственно выписать все вари- анты, но тем не менее очевидно, сколько их на самом деле. Задача. («Физтех», 2013, 8 ) Сколько пар натуральных чисел удовлетворяет равенству 2x + 5y = 90000 ? Решение. Переписав данное равенство в виде 2x = 90000 − 5y, мы видим, что правая часть делится на 5. Тогда 2x делится на 5, а значит, и x делится на 5; то есть x = 5n для некоторого натурального n. Аналогично заключаем, что y = 2k для некоторого натурального k. 4 Теперь исходное равенство принимает вид: 10n + 10k = 90000, то есть n + k = 9000. Спра- шивается: сколько пар (n, k) удовлетворяют полученному равенству? Понятно, что n может принимать значения от 1 до 8999. Число k однозначно определяется выбором n (поскольку k = 9000 − n). Следовательно, имеется 8999 пар чисел (n, k). Но число x однозначно определяется по n, а число y однозначно определяется по x (или по k). Значит, искомое количество пар (x, y) также равно 8999. 1.1 Задачи 1. («Высшая проба», 2013, 9–10 ) На шахматной доске 7 × 7 посчитайте количество всех квад- ратов, границы которых проходят по границам клеток. 140 2. («Высшая проба», 2014, 11 ) Найдите количество натуральных чисел n 6 10 12 таких, что НОК(16, n) = 16n. 5· 10 11 3. (Математический праздник, 1997, 7 ) Каких прямоугольников с целыми сторонами больше: с периметром 1996 или с периметром 1998? (Прямоугольники a × b и b × a считаются одинако- выми.) Поровну 4. («Покори Воробьёвы горы!», 2014, 8 ) Найдите количество натуральных чисел от 1 до 100, имеющих ровно четыре натуральных делителя, не менее чем три из которых не превосходят 10. 8 5. («Высшая проба», 2014, 9 ) Из множества {1, 2, 3, 4} выбираются три различных натураль- ных числа a, b, c. Сколько существует способов сделать это так, чтобы число a (b c ) делилось на 4? 10 6. («Высшая проба», 2013, 9 ) Сколько одночленов окажется в многочлене (1 + t 4 + t 8 + . . . + t 40 )(1 + t 5 + t 10 + . . . + t 40 ) после раскрытия скобок и приведения подобных членов? 69 7. («Высшая проба», 2011, 9 ) На клетчатой бумаге нарисован квадрат размером 3 × 3 клеточ- ки. Требуется закрасить в этом квадрате три клеточки так, чтобы никакие две закрашенные клеточки не имели общей стороны. Сколькими способами это можно сделать? Два способа рас- краски считаются одинаковыми, если один можно получить из другого поворотом квадрата. 6 5 8. («Высшая проба», 2013, 9 ) В стране четыре города: А, Б, В и Г. Их хотят связать тремя авиалиниями так, чтобы из каждого города можно было (возможно, с пересадками) долететь до любого другого. Сколькими различными способами это можно сделать? 16 9. («Высшая проба», 2014, 9, 11 ) Сколькими способами цифры от 1 до 9 можно разбить на несколько (больше одной) групп так, чтобы суммы цифр во всех группах были равны друг другу? (Разбиения, отличающиеся только перестановкой групп, считаются одинаковыми.) 10 10. (Турнир Ломоносова, 1991 ) Шеренга солдат называется неправильной, если никакие три подряд стоящих солдата не стоят по росту (ни в порядке возрастания, ни в порядке убывания). Сколько неправильных шеренг можно построить а) из четырёх; б) из пяти солдат разного роста? а)10; б)32 11. (ОММО, 2014 ) Скуперфильд хочет выплатить наложенный на него штраф в 1000 фер- тингов монетами в 7 и 13 фертингов. Сколькими способами он может это сделать? 2 Каким наименьшим количеством монет он может обойтись? 11способов; минимум82 монеты 12. («Покори Воробьёвы горы!», 2012, 8–9 ) Сколькими способами можно поставить цифры от 1 до 9 вместо букв так, чтобы все неравенства выполнялись? a b c d e f g h i > > > > > > ∨ ∨ ∨ ∨ ∨ ∨ 42 13. («Покори Воробьёвы горы!», 2012, 9 ) Сколькими способами можно выписать в ряд числа 1, 2, 3, 4, 5, 6 так, чтобы для любых трёх подряд идущих чисел a, b, c величина ac − b 2 была кратна 7? 12 2 На олимпиаде этого вопроса не было. 6 2 Цепочки и множества Исчерпывающий перебор конечного числа вариантов является совершенно законным способом решения задач. Однако в задачах с большим числом вариантов следует искать другие подходы. Ниже мы подробно рассмотрим наиболее распространённые комбинаторные схемы — размеще- ния и сочетания. Однако прежде нам нужно обсудить понятия цепочки и множества (то есть упорядоченных и неупорядоченных наборов), которые лежат в основе этих схем. 2.1 Упорядоченные наборы В некоторых ситуациях порядок следования объектов важен для нас, а в некоторых — не важен. Пусть, например, нужно решить систему уравнений ( x + y = 3, x − y = 1. Легко находим решение: x = 2, y = 1 и пишем ответ в виде пары: (2, 1). По общепринятому соглашению, первым числом нашей пары является значение x, а вторым числом — значение y. Такую пару называют упорядоченной, поскольку порядок следования чисел важен; записывая ответ, мы не можем поменять числа местами! Запись (1, 2) означала бы, что x = 1 и y = 2; эта пара, заметим, не является решением данной системы. Пары (2, 1) и (1, 2) — это две разные упорядоченные пары. Упорядоченный набор объектов мы называем цепочкой 3 , а сами объекты — элементами цепочки. Цепочка, составленная по порядку из элементов a 1 , a 2 , . . ., a k , записывается a 1 a 2 . . . a k или (a 1 , a 2 , . . . , a k ); число k называется длиной цепочки. При изменении порядка следования элементов мы, вообще говоря, получим другую цепочку (той же длины). Рассмотрим некоторые примеры цепочек. • Пусть точка на координатной плоскости имеет абсциссу x = 0 и ординату y = 1. В таком случае мы записываем координаты точки в виде упорядоченной пары (0, 1). Это — цепочка длины 2, составленная из чисел 0 и 1 в указанном порядке. Порядок следования чисел важен: ведь (1, 0) — это уже другая точка плоскости (то есть другая упорядоченная пара или другая цепочка). • Аналогично, пусть точка координатного пространства имеет координаты x = 0, y = 1 и z = 2. Мы записываем её координаты в виде (0, 1, 2). Это — цепочка длины 3, составленная из чисел 0, 1 и 2; она называется также упорядоченной тройкой чисел 0, 1 и 2. Порядок следования чисел важен: при изменении порядка мы получим другую точку координат- ного пространства (другую упорядоченную тройку, другую цепочку). • Слово автор является цепочкой длины 5, составленной из букв а, в, т, о, р. Порядок следования букв важен: например, слово отвар, составленное из тех же букв, — это уже другое слово (другая цепочка). 2.2 Неупорядоченные наборы Допустим теперь, что требуется решить квадратное уравнение x 2 − 3x + 2 = 0. 3 Другое название упорядоченного набора — кортеж. 7 Его корнями служат числа 1 и 2. Мы записываем пару этих корней в виде {1, 2}. Такую пару называют неупорядоченной, поскольку порядок следования чисел в данной записи не играет роли; в самом деле, мы можем записать ответ и в виде {2, 1}, перечислив те же корни в другом порядке. Пары {1, 2} и {2, 1} — это одна и та же неупорядоченная пара. Всякий неупорядоченный набор объектов есть не что иное, как множество; сами объекты являются элементами множества. Множество, состоящее из элементов a 1 , a 2 , . . ., a k , записы- вается {a 1 , a 2 , . . . , a k }. Порядок следования элементов не важен; при изменении порядка мы получим то же множество. Например, как мы видели выше, {1, 2} = {2, 1}. Рассмотрим неко- торые примеры множеств. • Множество корней уравнения x(x−1)(x−2) = 0 есть A = {0, 1, 2}. Это — неупорядоченная тройка чисел 0, 1 и 2, которые являются элементами множества A. Множество A можно записать и в любом другом порядке, например: A = {2, 0, 1}. • Множество букв русского алфавита состоит из 33 элементов: {а, б, в, . . . , ю, я}. • Множество букв слова «математика» есть M = {м, а, т, е, и, к}. Множество букв слова «физика» есть F = {ф, и, з, к, а}. Запись a ∈ A означает, что объект a является элементом множества A, и читается «a при- надлежит множеству A». Если a не является элементом множества A (a не принадлежит A), то это записывается так: a / ∈ A. Множество A называется подмножеством множества B (обозначается A ⊂ B), если любой элемент множества A является элементом множества B. Например, {1, 2, 3} ⊂ {1, 2, 3, 4, 5}. Ясно, что для любого множества A выполнено A ⊂ A. Два множества называются равными, если они состоят из одних и тех же элементов. Иными словами, множество A равно множеству B в том и только в том случае, если A ⊂ B и B ⊂ A. Например, {1, 2, 3} = {3, 2, 1}. Имеется множество, которое не содержит элементов: это пустое множество, которое обо- значается ∅. Например, множество действительных корней уравнения x 2 + 1 = 0 пусто. Любопытно, что пустое множество является подмножеством любого множества. Дока- жем данное утверждение от противного. Предположим, что это не так, то есть пустое множество не является подмножеством некоторого множества A. Тогда найдётся элемент пустого множе- ства, который не принадлежит множеству A. Но пустое множество не содержит элементов. Противоречие. 2.3 Операции над множествами Наиболее важные для нас операции над множествами — объединение, пересечение и разность множеств. Объединение множеств A и B есть множество A ∪ B, которое состоит из всех элементов, принадлежащих хотя бы одному из множеств A или B. Так, для множеств M и F из рас- смотренного выше примера имеем: M ∪ F = {м, а, т, е, и, к, ф, з}. Аналогично определяется объединение трёх и большего числа множеств. Пересечение множеств A и B есть множество A ∩ B, которое состоит из всех элементов, принадлежащих как множеству A, так и множеству B. Например, для тех же множеств M и F имеем: M ∩ F = {а, и, к}. Множества, у которых нет общих элементов (то есть пересечение которых пусто), называются непересекающимися. Разность множеств A и B есть множество A \ B, которое состоит из всех элементов мно- жества A, не принадлежащих множеству B. Например, M \ F = {м, т, е}. Задача. («Высшая проба», 2014, 9 ) В детский сад завезли карточки для обучения чтению: на некоторых написано «МА», на остальных — «НЯ». Каждый ребёнок взял три карточки и 8 стал составлять из них слова. Оказалось, что слово «МАМА» могут сложить из своих карточек |