Олимпиадные задачи по комбинаторике. Задача о беспорядках

• Название: Задача о беспорядках
• Анкор: Олимпиадные задачи по комбинаторике
• Дата: 12.04.2022
• Размер: 0.5 Mb.
• Имя файла: kombinatorika.pdf
• Тип: Задача; #468020
• страница: 6 из 6

1. Сколько существует четырёхзначных чисел, в записи которых есть хотя бы одна чётная цифра?
8375 2. Сколько существует шестизначных чисел, в записи которых есть хотя бы две одинаковых цифры?
763920 44

3. Сколько существует пятизначных чисел, в записи которых есть хотя бы две единицы?
7623 4. («Высшая проба», 2013, 11 ) В стране шесть городов: А, Б, В, Г, Д и Е. Их хотят связать пятью авиалиниями так, чтобы из каждого города можно было (возможно, с пересадками)

долететь до любого другого. Сколькими различными способами это можно сделать?
1296 5. (Московская математическая олимпиада, 2006, 6, окружной этап) В саду у Ани и Вити росло 2006 розовых кустов. Витя полил половину всех кустов, и Аня полила половину всех кустов. При этом оказалось, что ровно три куста, самые красивые, были политы и Аней, и

Витей. Сколько розовых кустов остались не политыми?
3 6. (Московская математическая олимпиада, 2008, 7, окружной этап) По данным опроса,
проведённого в 7 «Е» классе, выяснилось, что 20% учеников, интересующихся математикой,
интересуются ещё и физикой, а 25% учеников, интересующихся физикой, интересуются также и математикой. И только Пете с Васей не интересен ни один из этих предметов. Сколько человек в 7 «Е», если известно, что их больше 20, но меньше 30?
26 7. Пусть A — множество букв слова «абракадабра», B — множество букв слова «бриганти- на», C — множество букв слова «каракатица». Выпишите множества A, B и C, найдите их всевозможные пересечения и проверьте формулу включений и исключений для трёх множеств.
8. (Московская математическая олимпиада, 1938 ) Сколько существует натуральных чисел,

меньших тысячи, которые не делятся ни на 5, ни на 7?
686 9. («Ломоносов», 2012, 7 ) Сколько чисел из набора 1, 2, . . . , 2010, 2011 не делятся ни на 3, ни на 7?
1149 10. («Физтех», 2014, 7, 8, 10 ) На столе рубашкой вверх была разложена колода из 36 иг- ральных карт. Лёша перевернул 30 карт, затем Макс перевернул 19 карт, а после этого Боря —

21 карту. В результате вся колода оказалась рубашкой вниз. Сколько карт было перевёрнуто трижды?
17 11. («Физтех», 2013, 8–9 ) Трое ребят принялись красить лист ватмана, каждый — в свой цвет.
Один закрасил красным 75% листа, второй закрасил зелёным 70% листа, а третий закрасил синим 65% листа. Сколько процентов листа будет заведомо закрашено всеми тремя цветами?
10%
45

12. («Ломоносов», 2013, 9 ) Найдите количество натуральных делителей числа N = 1 00 . . . 0
|
{z
}
40
,
а) не являющихся ни точными квадратами (т. е. квадратами натуральных чисел), ни точными кубами; б) не представимых в виде m n
, где m и n — натуральные числа, причём n > 1.
а)1093;
б)981 13. («Высшая проба», 2014, 10 ) В группе 17 человек знают английский язык, 14 человек знают китайский язык, 20 человек знают арабский язык и 19 человек знают польский язык. При этом
34 человека в группе знают ровно один язык из перечисленных, а остальные — ровно два языка из перечисленных. Сколько человек в группе?
52 14. («Высшая проба», 2014, 11 ) В группе 15 человек знают английский язык, 16 человек знают китайский язык, 20 человек знают арабский язык и 21 человек знает польский язык. В группе нет людей, знающих три языка, и 23 человека в группе знают ровно два языка из перечислен- ных. Сколько человек в группе знают ровно один язык из перечисленных?
26 15. («Физтех», 2014, 11 ) Прямоугольный параллелепипед 35 × 40 × 56, разбитый на 78400

единичных кубиков, проткнули иглой по его диагонали. Сколько единичных кубиков протыкает игла?
112 46

6
Разные комбинаторные приёмы
В данном разделе рассмотрены два приёма решения комбинаторных задач — подсчёт двумя способами и составление рекуррентных соотношений.
6.1
Подсчёт двумя способами
В некоторых задачах можно получить нужное уравнение, если вычислить двумя способами одну и ту же величину. Трудность состоит в том, чтобы додуматься — какую именно величину подсчитывать двумя способами.
Задача. Тридцать школьников — семиклассников и восьмиклассников — обменялись рукопо- жатиями. При этом оказалось, что каждый семиклассник пожал руку восьми восьмиклассни- кам, а каждый восьмиклассник пожал руку семи семиклассникам. Сколько было семиклассни- ков и сколько восьмиклассников?
Решение. Пусть x — число семиклассников, y — число восьмиклассников; тогда x + y = 30.
Второе уравнение мы получим, если подсчитаем двумя способами общее количество рукопо- жатий. С одной стороны, число рукопожатий равно 8x, поскольку от каждого семиклассника
«исходит» 8 рукопожатий. С другой стороны, число рукопожатий равно 7y, так как от каж- дого восьмиклассника «исходит» 7 рукопожатий. Следовательно, 8x = 7y. Решая полученную систему уравнений, находим: x = 14, y = 16.
Задача. (Турнир Ломоносова, 1985 ) Было 7 пустых ящиков. В некоторые из них положили еще по 7 пустых ящиков и т. д. В итоге стало 10 непустых ящиков. Сколько всего стало ящиков?
Решение. Если ящик A лежит непосредственно в ящике B, то будем говорить, что из ящика
A в ящик B идёт стрелка. Пусть всего стало x ящиков. Подсчитаем двумя способами общее количество стрелок. С одной стороны, оно равно x − 7, поскольку из каждого ящика, кроме начальных семи, выходит ровно одна стрелка. С другой стороны, число стрелок равно 10·7 = 70,
поскольку в каждый из 10 непустых ящиков входит ровно 7 стрелок (а ни в какой пустой ящик стрелка не входит). Следовательно, x − 7 = 70, откуда x = 77.
Данную задачу можно решить и по-другому. На каждом шаге процесса заполняется ровно один ящик — в него кладутся 7 ящиков. Поскольку вначале все ящики пусты, сделано 10 шагов,
то есть добавлено 70 ящиков. Плюс семь начальных — итого 77 ящиков.
6.2
Рекуррентные соотношения
Говорят, что последовательность a
1
, a
2
, . . . , a n
, . . . задана рекуррентно, если существует фор- мула, выражающая 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 n
Решение. Начнём выписывать члены нашей последовательности:
a
1
= 3,
a
2
= 9,
a
3
= 6,
a
4
= −3,
a
5
= −9,
a
6
= −6,
a
7
= 3,
a
8
= 9,
Как видим, последовательность «зацикливается» — она периодична с периодом 6 (то есть a
n+6
= a n
). Иными словами, равны все члены последовательности, номера которых дают при делении на 6 одинаковые остатки. Номер 200 имеет остаток 2 от деления на 6. Значит,
a
200
= a
2
= 9.
47

Некоторые задачи комбинаторики можно решить, если составить для искомой величины рекуррентное соотношение, после чего вычислить эту величину вплоть до нужного значения n.
Посмотрим, как это делается.

Задача. Сколько существует строк длины 10, состоящих из нулей и единиц, таких, что никакие два нуля не стоят рядом?
Решение. Говоря в решении этой задачи о строках, мы имеем в виду строки, описанные в условии, то есть составленные из нулей и единиц так, что никакие два нуля не стоят рядом.
Обозначим через x n
число строк длины n. Ясно, что x
1
= 2 (это строки 0 и 1), x
2
= 3 (это строки 01, 10 и 11). Будем искать рекуррентное соотношение, задающее последовательность x n
Предположим, что n
> 3. Пусть N
1
— число строк длины n, которые начинаются с единицы.
Вторым числом такой строки может быть либо 0, либо 1; иными словами, к первой цифре 1
«пристыковывается» любая строка длины n − 1. Поэтому строк, начинающихся с единицы,
столько же, сколько существует строк длины n − 1, то есть N
1
= x n−1
Пусть теперь N
0
— число строк длины n, которые начинаются с нуля. Вторым числом такой строки обязательно служит единица, а к этой единице уже «пристыковывается» любая строка длины n − 2. Поэтому N
0
= x n−2
В результате получаем:
x n
= N
1
+ N
0
= x n−1
+ x n−2
(n > 3).
Теперь с учётом начальных условий x
1
= 2, x
2
= 3 находим:
x
3
= x
2
+ x
1
= 5;
x
4
= x
3
+ x
2
= 8;
x
5
= x
4
+ x
3
= 13,
и так далее вплоть до интересующего нас значения x
10
= 144. Таким образом, строк длины 10
получается 144.
Заметим, что полученная последовательность 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . . . — это знаменитые числа Фибоначчи.

Задача. Сколько слов длины 5 можно составить из букв a, b и c так, чтобы буквы a и b не стояли рядом?
Решение. Пусть x n
— число слов длины n (описанных в условии). Ясно, что x
1
= 3 (это слова a, b и c). Если n = 2, то все возможные слова суть aa, ac, bb, bc, ca, cb, cc; таким образом, x
2
= 7.
Обозначим a n
, b n
и c n
число слов длины n, начинающихся с буквы a, b и c соответственно.
Тогда, очевидно,
x n
= a n
+ b n
+ c n
(10)
Предположим, что n
> 3. Пусть слово длины n начинается с буквы a. Поскольку на втором месте не может быть b, к букве a «пристыковывается» любое слово длины n − 1, начинающееся с a или c. Поэтому a
n
= a n−1
+ c n−1
(11)
Аналогично:
b n
= b n−1
+ c n−1
,
(12)
c n
= a n−1
+ b n−1
+ c n−1
= x n−1
(13)
Сложим (
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 n−2
Подставляем это в (
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 48

Итак, имеем рекуррентное соотношение:
x n
= 2x n−1
+ x n−2
(n > 3; x
1
= 3, x
2
= 7).
Последовательно вычисляем: x
3
= 17, x
4
= 41 и, наконец, x
5
= 99. Итак, слов длины 5
получается 99.
Задача. Шеренга солдат называется неправильной, если никакие три подряд стоящих солдата не стоят по росту (ни в порядке возрастания, ни в порядке убывания). Сколько неправильных шеренг можно построить из n солдат разного роста?
Решение. Случаи n = 4 и n = 5 предлагались в качестве задачи к разделу 1 (её можно решить перебором вариантов). Сейчас мы рассмотрим данную задачу в общем виде.
Пусть x n
— число неправильных шеренг длины n. Как и в предыдущих задачах, ищем рекуррентное соотношение для x n
Рассмотрим неправильную шеренгу длины n + 1 (n
> 1). Пусть Z — самый высокий солдат шеренги. Он может стоять на любом месте от 1 до n + 1 (перечисляем солдат слева направо).
Предположим, что Z стоит на (k + 1)-м месте (k = 0, 1, . . . , n); то есть, слева от Z стоят k солдат
(которых можно выбрать C
k n
способами), а справа от Z стоят оставшиеся n − k солдат.
Заметим, что слева от Z стоит неправильная шеренга длины k, но не произвольная, а такая,
у которой предпоследний солдат X выше последнего солдата Y (в противном случае солдаты
X, Y и Z окажутся стоящими по росту). Ясно, что таких шеренг вдвое меньше общего числа неправильных шеренг длины k; стало быть, слева от Z можно выстроить x k
/2 шеренг. Чтобы это было справедливо при k = 0 и k = 1 (одна шеренга в обоих случаях), мы полагаем x
0
= x
1
= 2.
Аналогично, справа от Z стоит неправильная шеренга длины n − k, но не произвольная, а такая, у которой второй солдат выше первого. Таких шеренг будет x n−k
/2.
Остаётся заметить, что k солдат слева от Z можно выбрать C
k n
способами (и при каждом таком способе однозначно выбраны n − k солдат справа от Z). Таким образом, если Z стоит на k-м месте, то число неправильных шеренг будет равно
C
k n
·
x k
2
·
x n−k
2
=
1 4
C
k n
x k
x n−k
Суммируя по 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
= 2).
Читатель может самостоятельно убедиться, что выполнены равенства x
4
= 10 и x
5
= 32 —
это результат задачи 10 раздела 1.
6.3
Задачи
1. (Математический праздник, 1996, 7 ) Футбольный мяч сшит из 32 лоскутков: белых шести- угольников и чёрных пятиугольников. Каждый чёрный лоскут граничит только с белыми, а каждый белый — с тремя чёрными и тремя белыми. Сколько лоскутков белого цвета?
20 2. («Физтех», 2014, 7–8 ) Про группу из пяти человек известно, что: Андрей на 5 лет старше
Андреева, Борис на 3 года старше Борисова, Василий на 2 года старше Васильева, Григорий на 1
год старше Григорьева. Ещё в этой группе есть Дмитрий и Дмитриев. Кто старше и на сколько:
Дмитрий или Дмитриев? В ответе укажите возраст Дмитрия минус возраст Дмитриева.
−11 49

3. («Физтех», 2014, 7–8 ) Олег с папой пошли в тир. Они договорились, что Олег делает шесть выстрелов и за каждое попадание в цель получает право сделать ещё два выстрела. Всего Олег сделал 20 выстрелов. Сколько раз он попал в цель?
7 4. («Физтех», 2014, 7–8 ) У Царя Гороха было четверо сыновей, а дочерей не было. Его потомки тоже не имели дочерей, среди них 25 имели каждый по три сына, а у остальных вообще не было детей. Сколько потомков было у царя Гороха?
79 5. («Физтех», 2013, 8–11 ) В большую коробку положили 10 коробок поменьше. В некоторые из них положили 10 коробок ещё поменьше. В некоторые из этих последних коробок положили
10 коробок ещё меньшего размера и так далее. В результате оказалось, что имеется ровно

2000 коробок, в которых что-то лежит. Какое наибольшее число коробок могут при этом быть пустыми?
18001 6. (Всероссийская олимпиада по математике, 2012, 11 класс, II этап) Туристическая фир- ма провела акцию: «Купи путёвку в Египет, приведи четырёх друзей, которые также купят путёвку, и получи стоимость путёвки обратно». За время действия акции 13 покупателей при- шли сами, остальных привели друзья. Некоторые из них привели ровно по 4 новых клиента, а остальные 100 не привели никого. Сколько туристов отправились в Страну Пирамид бесплатно?
29 7. («Физтех», 2014, 10–11 ) Последовательность a n
такова, что a
1
= 4, a
2
= 25. Найдите a
200
,
если для любого натурального n справедливо равенство a n+1
= a n
· a n+2 25 8. Сколько семибуквенных слов можно составить из букв a и b так, чтобы после буквы a стояла хотя бы одна буква b? (Букве a разрешается быть последней.)
34 9. Сколько имеется разбиений отрезка длины 8 на отрезки длины 1, 2 и 3? (Разбиения, отли- чающиеся порядком следования отрезков, считаются различными.)
81 10. («Ломоносов», 2014, 10–11 ) Первоклассница Маша, заходя в школу, каждый раз поднима- ется на школьное крыльцо по лестнице, имеющей 9 ступенек. Находясь внизу лестницы или на очередной её ступеньке, она может либо подняться на следующую ступеньку, либо перепрыг- нуть через одну ступеньку вверх (перепрыгнуть через две или более ступенек Маша пока не может). Какое минимальное количество раз Маше нужно зайти в школу, чтобы подняться на крыльцо всеми возможными способами?
55 50

11. («Покори Воробьёвы горы!», 2012, 7–8 ) Мария Ивановна — строгая учительница по алгебре.
Она ставит в журнал только двойки, тройки и четвёрки, причём никогда не ставит одному уче- нику две двойки подряд. Известно, что она поставила Вовочке 6 оценок за четверть. Сколькими различными способами она могла это сделать?
448 12. («Физтех», 2014, 11 ) Кузнечик прыгает по вершинам правильного треугольника ABC,

прыгая каждый раз в одну из соседних вершин. Сколькими способами он может попасть из вершины A обратно в вершину A за 9 прыжков?
170 13. («Покори Воробьёвы горы!», 2011, 9–11 ) Имеются 12 карандашей попарно различной длины.
Сколькими способами можно уложить их в коробку в два слоя по шесть карандашей так, чтобы в каждом слое карандаши были упорядочены по возрастанию длины (слева направо), а каждый карандаш верхнего слоя лежал строго над карандашом нижнего слоя и был короче его?
132 14. («Высшая проба», 2014, 11 ) На клетчатой доске размером 2 × n клеток некоторые клетки закрашиваются в чёрный цвет. Раскраска называется правильной, если среди закрашенных нет двух соседних клеток (соседними называются клетки, имеющие общую сторону). Раскраска, в которой ни одна клетка не закрашена, тоже считается правильной.
Пусть A
n
— количество правильных раскрасок с чётным числом закрашенных клеток, B
n
—
количество правильных раскрасок с нечётным числом закрашенных клеток. Найдите все воз- можные значения A
n
− B
n
±1 51