Подсчёт двумя способами
В некоторых задачах можно получить нужное уравнение, если вычислить двумя способами одну и ту же величину. Трудность состоит в том, чтобы додуматься — какую именно величину подсчитывать двумя способами.
Задача. Тридцать школьников — семиклассников и восьмиклассников — обменялись рукопожатиями. При этом оказалось, что каждый семиклассник пожал руку восьми восьмиклассникам, а каждый восьмиклассник пожал руку семи семиклассникам. Сколько было семиклассников и сколько восьмиклассников?
Решение. Пусть x — число семиклассников, y — число восьмиклассников; тогда x + y = 30. Второе уравнение мы получим, если подсчитаем двумя способами общее количество рукопожатий. С одной стороны, число рукопожатий равно 8x, поскольку от каждого семиклассника «исходит» 8 рукопожатий. С другой стороны, число рукопожатий равно 7y, так как от каждого восьмиклассника «исходит» 7 рукопожатий. Следовательно, 8x = 7y. Решая полученную систему уравнений, находим: x = 14, y = 16.
Задача. Было 7 пустых ящиков. В некоторые из них положили еще по 7 пустых ящиков и т. д. В итоге стало 10 непустых ящиков. Сколько всего стало ящиков?
Решение. Если ящик A лежит непосредственно в ящике B, то будем говорить, что из ящика A в ящик B идёт стрелка. Пусть всего стало x ящиков. Подсчитаем двумя способами общее количество стрелок. С одной стороны, оно равно x − 7, поскольку из каждого ящика, кроме начальных семи, выходит ровно одна стрелка. С другой стороны, число стрелок равно 10·7 = 70, поскольку в каждый из 10 непустых ящиков входит ровно 7 стрелок (а ни в какой пустой ящик стрелка не входит). Следовательно, x − 7 = 70, откуда x = 77.
Данную задачу можно решить и по-другому. На каждом шаге процесса заполняется ровно один ящик — в него кладутся 7 ящиков. Поскольку вначале все ящики пусты, сделано 10 шагов, то есть добавлено 70 ящиков. Плюс семь начальных — итого 77 ящиков.
Рекуррентные соотношения
Говорят, что последовательность a1, a2, . . . , an, . . . задана рекуррентно, если существует формула, выражающая n-й член этой последовательности через один или несколько предыдущих членов; такая формула называется рекуррентным соотношением.
Например, рекуррентное соотношение an+1 = an + 3 с начальным условием a1 = 2 задаёт арифметическую прогрессию 2, 5, 8, 11, . . .
Задача. На доску выписаны числа a1, a2, . . . , a200. Известно, что a1 = 3, a2 = 9. Найдите a200, если для любого натурального n справедливо равенство an+2 = an+1 − an.
Решение. Начнём выписывать члены нашей последовательности: a1 = 3, a2 = 9, a3 = 6, a4 = −3, a5 = −9, a6 = −6, a7 = 3, a8 = 9, . . . Как видим, последовательность «зацикливается» — она периодична с периодом 6 (то есть an+6 = an). Иными словами, равны все члены последовательности, номера которых дают при делении на 6 одинаковые остатки. Номер 200 имеет остаток 2 от деления на 6. Значит, a200 = a2 = 9.
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
1. В большую коробку положили 10 коробок поменьше. В некоторые из них положили 10 коробок ещё поменьше. В некоторые из этих последних коробок положили 10 коробок ещё меньшего размера и так далее. В результате оказалось, что имеется ровно 2000 коробок, в которых что-то лежит. Какое наибольшее число коробок могут при этом быть пустыми?
18001
2. В классе каждый мальчик дружит ровно с двумя девочками, а каждая девочка — ровно с тремя мальчиками. Еще известно, что в классе 31 пионер и 19 парт. Сколько человек в этом классе?
35
3. По кругу расставлены цифры 1, 2, 3, . . . , 9 в произвольном порядке. Каждые три цифры, стоящие подряд по часовой стрелке, образуют трёхзначное число. Найдите сумму всех девяти таких чисел. Зависит ли она от порядка, в котором записаны цифры?
4995; не зависит
4. Футбольный мяч сшит из 32 лоскутков: белых шестиугольников и чёрных пятиугольников. Каждый чёрный лоскут граничит только с белыми, а каждый белый — с тремя чёрными и тремя белыми. Сколько лоскутков белого цвета?
20
5. В банановой республике прошли выборы в парламент, в котором участвовали все жители. Все голосовавшие за партию «Мандарин» любят мандарины. Среди голосовавших за другие партии 90% не любят мандарины. Сколько процентов голосов набрала партия «Мандарин» на выборах, если ровно 46% жителей любят мандарины?
40%
6. Олег с папой пошли в тир. Они договорились, что Олег делает шесть выстрелов и за каждое попадание в цель получает право сделать ещё два выстрела. Всего Олег сделал 20 выстрелов. Сколько раз он попал в цель?
7
7. У Царя Гороха было четверо сыновей, а дочерей не было. Его потомки тоже не имели дочерей, среди них 25 имели каждый по три сына, а у остальных вообще не было детей. Сколько потомков было у царя Гороха?
79
8. Про группу из пяти человек известно, что: Алёша на 1 год старше Алексеева, Боря на 2 года старше Борисова, Вася на 3 года старше Васильева, Гриша на 4 года старше Григорьева, а ещё в этой группе есть Дима и Дмитриев. Кто старше и на сколько: Дима или Дмитриев?
Дмитриев старше Димы на 10 лет
9. Туристическая фирма провела акцию: «Купи путёвку в Египет, приведи четырёх друзей, которые также купят путёвку, и получи стоимость путёвки обратно». За время действия акции 13 покупателей пришли сами, остальных привели друзья. Некоторые из них привели ровно по 4 новых клиента, а остальные 100 не привели никого. Сколько туристов отправились в Страну Пирамид бесплатно?
29
10. Последовательность an такова, что a1 = 4, a2 = 25. Найдите a200, если для любого натурального n справедливо равенство an+1 = an · an+2.
25
11. Сколько семибуквенных слов можно составить из букв a и b так, чтобы после буквы a стояла хотя бы одна буква b? (Букве a разрешается быть последней.)
34
12. Сколько имеется разбиений отрезка длины 8 на отрезки длины 1, 2 и 3? (Разбиения, отличающиеся порядком следования отрезков, считаются различными.)
81
13. Первоклассница Маша, заходя в школу, каждый раз поднимается на школьное крыльцо по лестнице, имеющей 9 ступенек. Находясь внизу лестницы или на очередной её ступеньке, она может либо подняться на следующую ступеньку, либо перепрыгнуть через одну ступеньку вверх (перепрыгнуть через две или более ступенек Маша пока не может). Какое минимальное количество раз Маше нужно зайти в школу, чтобы подняться на крыльцо всеми возможными способами?
55
14. Мария Ивановна — строгая учительница по алгебре. Она ставит в журнал только двойки, тройки и четвёрки, причём никогда не ставит одному ученику две двойки подряд. Известно, что она поставила Вовочке 6 оценок за четверть. Сколькими различными способами она могла это сделать?
448
15. Кузнечик прыгает по вершинам правильного треугольника ABC, прыгая каждый раз в одну из соседних вершин. Сколькими способами он может попасть из вершины A обратно в вершину A за 9 прыжков?
170
16. Имеются 12 карандашей попарно различной длины. Сколькими способами можно уложить их в коробку в два слоя по шесть карандашей так, чтобы в каждом слое карандаши были упорядочены по возрастанию длины (слева направо), а каждый карандаш верхнего слоя лежал строго над карандашом нижнего слоя и был короче его?
132
17. На клетчатой доске размером 2 × n клеток некоторые клетки закрашиваются в чёрный цвет. Раскраска называется правильной, если среди закрашенных нет двух соседних клеток (соседними называются клетки, имеющие общую сторону). Раскраска, в которой ни одна клетка не закрашена, тоже считается правильной. Пусть An — количество правильных раскрасок с чётным числом закрашенных клеток, Bn — количество правильных раскрасок с нечётным числом закрашенных клеток. Найдите все возможные значения An − Bn.
± 1
Разные комбинаторные приёмы
