Правило сложения

Сколько существует способов выбрать один объект из нескольких групп объектов? На этот вопрос отвечает правило сложения, одно из основных комбинаторных правил.

Мой любимый питомец!

Ваня отправился в зоомагазин. Там продавались 3 ящерицы, 4 попугая, 5 кроликов и 6 рыбок. Сколькими способами Ваня может купить себе одного питомца?

Решение

Все варианты покупки уже разбиты на группы:

  • 3 варианта купить ящерику

  • 4 варианта купить попугая

  • 5 вариантов купить кролика

  • 6 вариантов купить рыбку

Используем правило сложения и находим все возможные варианты покупки:

3+4+5+6=183 + 4 + 5 + 6 = 18
Ответ

18

Во что поиграть?

Петя хочет поиграть в компьютерную игру. В его библиотеке игр есть 10 стрелялок, 5 стратегий и 3 квеста. Сколькими способами Петя может выбрать одну игру?

Решение

По правилу суммы у Пети 10 + 5 + 3 = 18 способов выбрать одну игру.

Ответ

18

Во что поиграть?

Аналог 1

Алиса хочет купить что-нибудь в книжном магазине. Выбор широкий: {{{ class1 }}}, {{{ class2 }}}, {{{ class3 }}} и {{{ class4 }}}. Сколькими способами Алиса может совершить покупку?

Решение

По правилу суммы у Алисы {{{ sum }}} {{{ sumLabel }}} совершить покупку.

Ответ

{{{ answer }}}

Разыграй свою карту!

Вы играете в карточную игру и у вас на руках три пятерки, два валета, два туза, одна девятка и один король. Вам нужно разыграть только одну карту. Сколькими способами это можно сделать?

Решение

Все варианты разыграть карту уже разбиты на группы:

  • 3 варианта разыграть одну пятерку

  • 2 варианта разыграть один валет

  • 2 варианта разыграть один из тузов

  • 1 вариант разыграть одну девятку

  • 1 вариант разыграть одного короля

Используем правило сложения и находим все возможные варианты разыграть карту:

3+2+2+1+1=93 + 2 + 2 + 1 + 1 = 9
Ответ

9

Да будет свет!

В темной комнате есть 3 настольные лампы, 2 лампочки на потолке, связанные с выключателем около двери, камин и 3 зашторенных окна. Сколько существует вариантов осветить эту комнату?

Решение

Для освещения комнаты можно: включить одну из 3 настольных ламп, включить лампочки на потолке с помощью выключателя, разжечь камин, снять шторы с одного из 3 окон. По правилу сложения получается 3 + 1 + 1 + 3 = 8 способов осветить комнату.

Ответ

8

Ведущий на День учителя

Школа планирует провести мероприятие в честь дня учителя. В таблице указаны сводные данные об учениках, которые не против прнять участие в празднике.

КлассМальчикиДевочки
8-й класс1213
9-й класс1115
10-й класс910
11-й класс67

Сколько есть вариантов назначить ведущего на мероприятие, если для этой роли подходят ученики 9-го и 10-го классов?

Указание

Определите, какие группы учеников удовлетворяют требованиям к ведущему праздника.

Решение

Условиям на роль ведущего праздника удовлетворяют 4 непересекающихся группы:

  1. Мальчики 9-го класса — 11 вариантов

  2. Девочки 9-го класса — 15 вариантов

  3. Мальчики 10-го класса — 9 вариантов

  4. Девочки 10-го класса — 10 вариантов

По правилу суммы получаем 11 + 15 + 9 + 10 = 45 способов выбрать ведущего.

Ответ

45

Чай, кофе, потанцуем?

На дискотеке есть 4 парня и 3 девушки. Артем станцевал 10 парных танцев, Василий 3, Петр и Игорь по 4. Света станцевала 2 парных танца, Аня 8. Сколько парных танцев станцевала Ксюша?

Парни танцуют только с девушками и наоборот.

Указание

Танцы каждого парня образуют группу танцев. Эти группы танцев не пересекаются.

Решение

Начнем с парней. Имеем 4 группы танцев, по одной группе на каждого из парней. Группы эти не пересекаются, так как к каждой группе танцев привязан свой парень. По правилу суммы получаем 10 + 3 + 4 + 4 = 21 парный танец.

В парных танцах парни танцуют с девушками. Вся описаная логика с группами и правилом суммы работает и на них тоже. Раз парни станцевали 21 танец, то и девшуки в сумме тоже станцевали 21 танец.

2Света+8Аня+xКсюша=21\underbrace{2}_{\substack{\text{Света}}} + \underbrace{8}_{\substack{\text{Аня}}} + \underbrace{x}_{\substack{\text{Ксюша}}} = 21

Решив простейшее уравнение получаем, что Ксюша станцевала 11 парных танцев.

Ответ

11

Большое путешествие

Сколько существует способов попасть из Математино в Химино?
Двигаться по дорогам можно только в правую сторону.

Указание

Разбейте все маршруты на классы, например «М-Х» (Математино - Химино) и другие.

Решение

Разобьем все возможные маршруты на классы:

  • В классе «М-Х», то есть напрямую от Математино до Химино, есть 2 маршрута.

  • В классе «М-Ф-1-Х», то есть до Физино по первой дороге и потом в Химино, есть 3 маршрута.

  • В классе «М-Ф-2-Х», то есть до Физино по второй дороге и потом в Химино, также 3 маршрута.

По правилу суммы получаем 2 + 3 + 3 = 8 маршрутов из Математино в Химино.

Ответ

8

Невероятные восьмерки

Сколько трехзначных чисел в своей записи содержат ровно две восьмерки?

Указание

Разбейте все трехзначные числа с двумя восьмерками на классы. Посчитайте, сколько чисел в каждом классе и используйте правило сложения.

Решение

Разобьем все возможные трехзначные числа ровно с двумя восьмерками на 3 класса: класс 88x88x, класс 8x88x8 и класс x88x88. В классах 88x88x и 8x88x8 вместо x могут быть любые цифры, кроме 8, то есть 0, 1, 2, 3, 4, 5, 6, 7, 9 (всего 9 вариантов). Получается, в этих двух классах у нас по 9 чисел. В классе x88x88 всего 8 чисел, потому что 0 не может быть в начале трехзначного числа.

По правилу сложения имеем 26 трехзначных чисел, в записи которых есть только две восьмерки:

988x+98x8+8x88=26\underbrace{9}_{\substack{\\ \normalsize 88x}} + \underbrace{9}_{\substack{\\ \normalsize 8x8}} + \underbrace{8}_{\substack{\\ \normalsize x88}} = 26
Ответ

26

Машина мечты!

Екатерина хочет купить себе машину. Ее интересуют только красные машины или джипы. В автосалоне продаются 10 красных и 7 синих джипов разных моделей, а также 16 моделей легковушек, из которых 5 красных.

Из скольких машин Екатерина будет выбирать при покупке автомобиля?

Указание

Разделим все подходящие машины на две группы: «Джипы» и «Красные». Не забывайте про пересечения!

Решение

Разделим все подходящие машины на две группы: «Джипы» и «Красные».

В группе «Джипы» находится 10 + 7 = 17 машин. В группе «Красные» находится 10 + 5 = 15 машин.

По правилу сложения мы должны сложить количества машин в этих группах. Но не забывайте про пересечения! Если мы просто сложим группы, то дважды учтем 10 красных джипов, которые находятся одновременно как в группе «Джипы», так и в группе «Красные»!

Поэтому, надо не забыть вычесть дубликаты:

17+1510=2217 + 15 - 10 = 22
Ответ

22

Сначала была буква

Максим хочет выбрать из предложения «А зори здесь тихие» одну букву. Ему подойдет либо гласная, либо такая, которая стоит на четном месте в предложении без учета знаков препинания.

Сколькими способами он может выбрать букву, считая, что ее положение в предложении имеет значение? А сколькими способами он может выбрать букву безотносительно ее положения?

Указание

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

Решение

Разделим все варианты выбрать букву на две группы.

В группе A будут варианты выбрать гласную букву. Всего в предложении 7 гласных, а значит 7 способов выбрать одну из них.

В группе B варианты выбрать буквы, порядковый номер которых четный. Выпишем все четные буквы:

з, р, з, е, ь, и, из, \ р, \ з, \ е, \ ь, \ и, \ и

То есть в группе B у нас так же 7 способов совершить выбор.

Обратите внимание, что группы пересекаются! В группе B есть 3 гласные («е», и две «и»), которые так же есть и в группе A! Сложив по правилу суммы эти способы в этих двух группах мы лишний раз учтем эти три буквы, поэтому нужно вычесть эти дубликаты:

7+73=117 + 7 - 3 = 11

Если положение выбираемой буквы не имеет значение, то количество способов в группе A, то есть количество уникальных гласных, уменьшается до 4. В группе B останется 5 букв «з, р, е, ь, и», причем с 2-мя пересечениями («е» и «и»).

4+52=74 + 5 - 2 = 7
Ответ

11 способов выбрать буквы, если их положение в предложении имеет знаение и 7, если не имеет.

Сначала была буква

Аналог 1

Решите ту же задачу, но для предложения: «Я лучше умру от старости, чем от скуки»

Ответ

Положение буквы имеет значение:

13Гласные+15Четные7=21\underbrace{13}_{Гласные} + \underbrace{15}_{Четные} - 7 = 21

Положение буквы не имеет значение:

6+104=126 + 10 - 4 = 12

Сначала была буква

Аналог 2

Решите ту же задачу, но для предложения: «Ваше время ограничено, не тратьте его, живя чужой жизнью»

Ответ

Положение буквы имеет значение:

20Гласные+46Четные7=59\underbrace{20}_{Гласные} + \underbrace{46}_{Четные} - 7 = 59

Положение буквы не имеет значение:

6+155=166 + 15 - 5 = 16

Лишние отличники

Экзамен по математике на «5» сдали 9 учеников. Экзамен по русскому языку на «5» сдали 7 учеников. 3 ученика получили отлично на обоих экзаменах. Сколько человек имеет пятерку по математике или по русскому языку?

Указание

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

Решение

У нас есть две группы учеников: отличники по математике и отличники по русскому языку. В первой группе 9 человек, во второй 7. Но эти группы пересекаются, потому что и там и там есть одни и те же 3 ученика, которые получили «5» по обоим предметам.

Если мы просто сложим 9 и 7, то с добавлением 7 мы повторно учтем 3-х отличников, которые и так есть среди 9 человек первой группы. По правилу суммы получается всего 9 + 7 - 3 = 13 отличников.

Ответ

13

Меньше знаешь, крепче спишь

В группе 40 человек. Из них 20 знают комбинаторику, 30 знакомы с теорией вероятностей. 15 человек обе темы. Сколько человек не знает ни комбинаторику, ни теорию вероятностей?

Указание

Задача решается так же, как и «Лишние отличники», только в конце надо выполнить еще одно действие.

Решение

В задаче есть два пересекающихся класса. Поэтому мы можем использовать правило суммы и не забыть вычесть количество повторящихся объектов.

20+3015=3520 + 30 - 15 = 35

Значит, «комбинаторику или теорию вероятности» знают 35 человек. Но нас просят найти тех, кто ничего не знает. Для этого вычитаем 35 человек, которые хоть что-то знают из общего количества человек: 40 - 35 = 5.

5 человек не знают ни комбинаторику, ни теорию вероятности.

Ответ

5

Работа не волк, в лес не убежит

Местная газета опросила 200 молодых людей. 170 из них учатся в университете. 45 человек работают. 27 не работают и не учатся.

  • Сколько молодых людей учатся и работают?

  • Сколько человек только учатся?

  • Сколько человек только работают?

Указание

Задача является развитием идей задач «Меньше знаешь, крепче спишь» и «Лишние отличники». Во всех трех задачах по сути выполняются одни и те же вычисления, просто с разными неизвестными.

Сначала найдите, сколько человек занимаются хоть чем-то. Потом используйте правило суммы.

Решение

Сначала определим, сколько человек заняты хоть чем-то: работой, учебой или и тем и другим сразу. Для этого из общего количества человек вычтем тех, кто ничем не занят:

20027=173200 - 27 = 173

Учащиеся и работащие образуют два класса. По правилу суммы получается 170 + 45 = 215 человек. Но нам уже точно известно, что чем-то занимаются только 173 человека. Значит наши классы пересекаются и есть 215 - 173 = 42 человека, которые одновременно работают и учатся.

Итак, 42 человека учатся и работают. Тогда 170 - 42 = 128 человек только учатся, а 45 - 42 = 3 человека только работают.

Ответ

42 человека учатся и работают. 128 человек только учатся. 3 человека только работают.

Не только лишь все карты

Сколько карт из полной колоды (52 карты без джокеров) отвечают условию «четные или красные или туз»?

Указание

Разделите искомые карты на три группы: четные, красные, и тузы. Сначала посчитайте карты, отвечающие укороченному условию — «четные или красные». Потом на основе полученного результата добавьте условие с тузами.

Не забывайте про пересечения!

Решение

Разделим искомые карты на три группы: четные, красные, и тузы.

Сначала разберемся с четными картами. 4 двойки, 4 четверки и так далее до 4 десяток. Всего 45=204\cdot 5 = 20 карт в группе четных.

Теперь красные карты. Их ровно половина от всей колоды — 26 штук. Но тут возникает пересечение, ведь некоторые красые карты одновременно являются и четными! Это двойки бубны и черви (2 карты), четверки бубны и черви (2 карты) и вплоть до десяток бубны и черви. Всего 25=102 \cdot 5 = 10 пересечений.

Итак, по правилу суммы с учетом дубликатов условию «четные или красные» отвечают 20 + 26 - 10 = 36 карт.

Тузов всего 4. Но тут возникает еще пересечения, ведь из четырех тузов два красные! Поэтому, условию «(четные или красные) или туз» отвечают 36 + 4 - 2 = 38 карт!

Ответ

38

Не только лишь все карты

Аналог 1

Сколько карт из той же колоды отвечают условию «черные с лицами или красные или нечетные»?

Решение

«Нечетных или красных» столько же, сколько и «четных или красных», а их мы уже посчитали — 36.

«Лиц» всего три (валет, король, дама), причем в каждой масти, то есть всего 34=123 \cdot 4 = 12 карт с лицами. Из них половина черных — 6 карт.

Пересечений с «четными или карсными» тут нет, поэтому по правилу суммы находим 36 + 6 = 42 подходящие карты.

Ответ

42

Решений мало не бывает

Сколько положительных целых решений имеет следующее выражение?

7<x5  или  4<x<100-7 < x \leq 5 \ \text{ или } \ 4 < x < 100
Указание

Положительные целые числа это числа вида 1,2,3,1, 2, 3, \ldots.

Обращайте внимние на строгость знаков неравенства.

Решения первого неравества это первый класс, второго — второй. Не забудьте проверить их на пересечение.

Решение

У нас есть два класса, каждый из которых связан со своим неравенством. Решениями первого неравенства являются целые числа от 1 до 5 включительно, то есть 6 чисел. У второго неравенства решения это все целые числа от 5 до 99, то есть 95 чисел.

Классы у нас пересекаются. Число 5 одновременно является решением как первого, так и второго неравенства, поэтому по правилу суммы всего имеем 6 + 95 - 1 = 100 положительных решений.

Ответ

100

Точечное путешествие v2.0

ЕГЭ Информатика

На рисунке — схема дорог, связывающих города. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город K?

Указание

Принцип решения точно такой же, как и рассмотренного в теории примера.

Решение

Решение «от конца к началу»

Общие рассуждения и пояснения насчет хода решения можно найти в разборе примера из теории. Здесь же мы просто применим полученные знания.

В город K можно напрямую попасть только из городов G, E и D. Обозначим за SKS_K количество способов попасть в город K. Тогда:

SK=SG+SE+SDS_K = S_G + S_E + S_D

Рассмотрим каждое слагаемое отдельно. Начнем с SGS_G:

SG=SF+SI+SHSG=SISF+SI+SCSHSG=SI+SI+SI+SBSCSG=3SI+SB S_G = S_F + S_I + S_H \\ S_G = \underbrace{S_I}_{S_F} + S_I + \underbrace{S_C}_{S_H} \\ S_G = S_I + S_I + \underbrace{S_I + S_B}_{S_C} \\ S_G = 3 S_I + S_B

Из A попасть в I можно только двумя способами, так что SI=2S_I = 2, а в B только одним — SB=1S_B = 1:

SG=32+1=7S_G = 3 \cdot 2 + 1 = 7

Остальные слагаемые (SES_E и SDS_D) точно так же сводим к SIS_I и SBS_B:

SE=SF=SI=2SD=SJ+SH==2SI+SB=22+1=5 S_E = S_F = S_I = 2 \\ S_D = S_J + S_H = \cdots = 2 S_I + S_B = 2 \cdot 2 + 1 = 5

Наконец можем получить финальный ответ:

SK=SG+SE+SD=7+2+5=14S_K = S_G + S_E + S_D = 7 + 2 + 5 = 14

Решение «от начала к концу»

Количество способов попасть в очередную точку равно сумме количеств способов попасть в предыдущие точки. Просто двигаемся слева направо и проставляем рядом с каждой точкой количество способов в нее попасть:

Ответ

14

Послушный робот

Надежда создала робота, который умеет делать три арифметических действия:

  1. Прибавить 1

  2. Прибавить 3

  3. Умножить на 2

Сколько различных цепочек из номеров действий можно дать роботу, чтобы он из числа 5 получил число 17?

Указание

Принцип решения почти такой же, как и рассмотренного в теории примера.

Решение

Общие рассуждения и пояснения насчет хода решения можно найти в разборе похоже примера из теории. Здесь же мы просто применим полученные знания.

Обозначим за RnR_n количество цепочек действий, которые дают в результате число n. Если число n нечетное, то получить его можно только из числа n1n-1 с помощью действия (1) или из числа n3n-3 с помощью действия (2). Действие (3) не поможет, так как любое число при умножении на 2 становится четным, а мы рассматриваем нечетное n.

Rn=Rn1+Rn3(n нечетное)R_n = R_{n-1} + R_{n-3} \quad (n \ \text{нечетное})

Если же число n четное, то получить его можно так же, но еще и из числа n2\frac{n}{2} с помощью умножения на 2, то есть действия (3):

Rn=Rn1+Rn3+Rn2(n четное)R_n = R_{n-1} + R_{n-3} + R_{\frac{n}{2}} \quad (n \ \text{четное})

Получить число 5 можно единственным способом — если не дать роботу никаких команд. Поэтому R5=1R_5 = 1. Получить 6 можно только одним способом — единожды применив действие (1). Поэтому R6=1R_6 = 1. Получить 7 можно только из 6 и снова только одним способом, так что R7=1R_7 = 1. Такая же история и с числом 8R8=1R_8 = 1. Дальше уже используем формулы:

R9=R8+R6=1+1=2R10=R9+R7+R5=2+1+1=4R11=R10+R8=4+1=5R12=R11+R9+R6=5+2+1=8R13=R12+R10=8+4=12R14=R13+R11+R7=12+5+1=18R15=R14+R12=18+8=26R16=R15+R13+R8=26+12+1=39R17=R16+R14=39+18=57R_9 = R_8 + R_6 = 1 + 1 = 2 \\ R_{10} = R_9 + R_7 + R_5 = 2 + 1 + 1 = 4 \\ R_{11} = R_{10} + R_8 = 4 + 1 = 5 \\ R_{12} = R_{11} + R_9 + R_6 = 5 + 2 + 1 = 8 \\ R_{13} = R_{12} + R_{10} = 8 + 4 = 12 \\ R_{14} = R_{13} + R_{11} + R_7 = 12 + 5 + 1 = 18 \\ R_{15} = R_{14} + R_{12} = 18 + 8 = 26 \\ R_{16} = R_{15} + R_{13} + R_8 = 26 + 12 + 1 = 39 \\ R_{17} = R_{16} + R_{14} = 39 + 18 = 57

Итак, всего 57 разных последовательностей действий можно дать роботу, чтобы он из числа 5 получил число 17.

Ответ

57

Дай... пять!?

Сложная

В сказочной стране живут невероятные жители. У них целых 3 руки: левая, средняя и правая! На каждой руке есть как минимум один палец, а в сумме их всего 17. Сколько комплектов перчаток должно быть в продаже, чтобы каждый житель смог выбрать себе подходящий?

Указание

Разбейте всех комплекты перчаток на классы, зафиксировав минимальное количество пальцев для каждого класса на одной перчатке и перебирая возможные варианты для двух оставшихся.

Например, K1K_1 будет означать класс вариантов комплектов, где у одной перчатки ровно 1 палец, на остальных не меньше 1 пальца, а в сумме на двух оставшихся перчатках должно быть 16 пальцев. Потом рассмотрите классы K2K_2, K3K_3 и так далее.

Решение

Описать комплект перчаток можно следующим образом: {1,2,14}\set{1,2,14}. Это означает, что в комплекте три перчатки на 1, 2 и 14 пальцев, в сумме 17. Причем совершенно не имеет значения порядок этих чисел: комплекты {1,2,14}\set{1,2,14} и {14,1,2}\set{14,1,2} одинаковые.

Теперь разобьем все варианты комплектов на классы. В класс K1K_1 поместим варианты комплектов, в которых есть рука с 1 пальцем и меньше 1 пальца на руках быть не может. Тогда в сумме на двух оставшихся руках должно быть 16 пальцев. Математически это можно описать так:

{1,x,y} причем x,y1, x+y=16\set{1, x, y} \ \text{причем} \ x,y \geq 1, \ x + y = 16

Все возможные варианты можно перебрать вручную, их тут мало. Получаем 8 комплектов перчаток:

{1,1,15}, {1,2,14}, ,{1,7,9}, {1,8,8}\set{1, 1, 15}, \ \set{1, 2, 14}, \ \ldots, \set{1,7, 9}, \ \set{1, 8, 8}

Напоминаю, что комплект {1,7,9}\set{1, 7, 9} это точно такой же комплект, что и {1,9,7}\set{1, 9, 7}, поэтому последний мы не считаем. Идем только по возрастанию количества пальцев на второй руке и уменьшению на третьей. Так мы точно не пропустим ни один комплект в классе.

Теперь рассмотрим класс K2K_2 в котором на одной руке есть 2 пальца и меньше 2 пальцев на других руках нет. Если мы допустим, что на какой-то руке будет меньше 2 пальцев (то есть 1 палец), то мы повторно учтем комплекты перчаток, которые уже есть в классе K1K_1. В сумме на двух оставшихся руках должно быть 15 пальцев:

{1,x,y} причем x,y2, x+y=15\set{1, x, y} \ \text{причем} \ x,y \geq 2, \ x + y = 15

Получаем 5 комплектов перчаток:

{2,2,13}, {2,3,12}, , {2,7,8}\set{2, 2, 13}, \ \set{2, 3, 12}, \ \ldots, \ \set{2, 7, 8}

Аналогичным образом строим класс K3K_3 и находим еще 5 возможных вариантов комплектов перчаток:

{3,3,11}, {3,4,10}, ,{3,7,7}\set{3, 3, 11}, \ \set{3, 4, 10}, \ \ldots, \set{3, 7, 7}

В классе P4P_4 будет уже 3 вида комплектов, в классе P5P_52. А в классе P6P_6 и дальше никаких комплектов нет. Ведь уже для P6P_6 в сумме на две оставшиеся руки нужно получить 11 пальцев. Но минимальная сумма, которая дает 11 это 6 + 5, а перчатки с 5 пальцами в классе P6P_6 быть не может.

Обратите внимание, что классы P1,,P5P_1, \ldots, P_5 не пересекаются. В P1P_1 у всех комплектов есть перчатка с одним пальцем и в то же время во всех остальных классах перчаток с одним пальцем нет. С другими классами точно так же. Раз классы не пересекаются, мы можем спокойно использовать правило суммы:

8P1+5P2+5P3+3P4+2P5=23\underbrace{8}_{\small P_1} + \underbrace{5}_{\small P_2} + \underbrace{5}_{\small P_3} + \underbrace{3}_{\small P_4} + \underbrace{2}_{\small P_5} = 23

Итак, в продаже должно быть 23 комплекта перчаток.

Ответ

23

Радиоактивные трехрукие

Задача с трехрукими но теперь после радиоционной катастрофы у них не ровно 17 пальцев, а не больше 15. Решать придется графически через нанесение точек на оси координат.

Чертова лестница

Нестандартная
Красивая

Лестница состоит из 9 ступенек. Алексей может подниматься ступенька за ступенькой, а может перешагивать через одну. Сколько существует способов подняться по лестнице? А если в лестнице 11 ступенек?

Указание

Адаптируйте решение примера про путешествия из теории. Например, попасть на ступень 9 можно только со ступенек 8 или 7.

Решение

Построение модели

Сходу слона съесть не выйдет, поэтому будем есть по кусочкам. В данном случае рассмотрим какую-нибудь одну ступеньку. Возьмем для примера девятую ступень. Попасть на нее можно только с восьмой ступени (поднявшись на одну ступеньку) или с седьмой ступени (переступив через одну). Других вариантов нет.

Представим теперь, что на восьмую ступеньку можно попасть 5 способами. Значит и на девятую ступеньку с восьмой можно попасть тоже только 5способами — совершив один шаг.

Теперь представим, что на седьмую ступеньку можно попасть 7 способами. Тогда, повторяя рассуждения как с восьмой ступенькой, с седьмой на девятую ступень тоже можно попасть только 7 способами.

Получается, способов попасть на девятую ступеньку столько же, как и способов попасть на «восьмую или седьмую» ступеньки. Причем классы способов попасть на ступеньку 8 и на ступеньку 7 не пересекаются! Одинаковых путей нет, ведь любой путь из класса «Ступень 8» содержит в себе восьмую ступеньку, которой нет ни в одном пути из класса «Ступень 7».

Итак, у нас есть два непересекающихся класса, а значит мы можем использовать правило суммы: 5 + 7 = 13 способов попасть на девятую ступеньку.

Математическая модель

Фишка в том, что подобные рассуждения можно провести для любой ступеньки. Тогда количество способов попасть на ступеньку n равно сумме количества способов попасть на ступеньки n1n-1 и n2n-2. Если обозначить количество способов попасть на ступень n за SnS_n, то получаем формулу:

Sn=Sn1+Sn2S_n = S_{n-1} + S_{n-2}

Решение задачи

Попасть на первую ступеньку можно только одним способом S1=1S_1 = 1. На вторую уже есть два способа S2=2S_2 = 2: с первой ступеньки и сразу с пола переступив через первую. Для третьей ступеньки уже можно воспользоваться выведенной формулой:

S3=S2+S1=2+1=3S_3 = S_2 + S_1 = 2 + 1 = 3

Ну и продолжаем дальше считать с помощью нашей формулы до победного:

S1S_1S2S_2S3S_3S4S_4S5S_5S6S_6S7S_7S8S_8S9\green{S_9}S10S_{10}S11\green{S_{11}}
1235813213455\green{55}89144\green{144}
Ответ

На лестницу из 9 ступенек можно подняться 55 разными способами. А на лестницу из 11 ступенек — 144.

Примечание

Обратите внимение на полученные формулу и последовательность чисел:

Fn=Fn1+Fn21, 2, 3, 5, 8, 12, F_n = F_{n-1} + F_{n-2} \qquad 1,\ 2,\ 3,\ 5,\ 8,\ 12,\ \ldots

Каждый следующий элемент последовательности получается через сложение двух предыдущих элементов. Это широко известные «Числа Фибоначчи». Они всплывают в самых разных областях, причем не только в математике, но даже и в природе. Только что мы выяснили, что они связаны и с подъемом на самую обыкновенную лестницу.

Вот уж и правда нельзя и шага сделать, чтобы не затронуть какую-нибудь красивую математическую формулу... Удивительно!

Задачи с шахматной доской

Дана шахматная клетка (координаты). Сколько существует клеток, из которых конь может попасть в данную клетку за два хода? Можно усложнить условие, убрав строгое ограничение на количичество ходов: не «за два хода», а «не более чем за три хода». Тогда могут появиться интересные циклы: конь может отойти назад от конечной клетки, а потом вернуться обратно. Интересный факт, конь может начинать прямо из конечной клетки! Это могут забыть посчитать!

Даны фигура в начальной клетке и конечная клетка. Фигура может походить вверх, вправо и по диагонали. Причем она не может дважды походить одинаково. Сколькими способами фигура может попасть в конечную клетку?

Задачи на пошаговый бой

Можно попробовать развить подход с тем, что некоторые действия можно использовать не всегда. Например, есть монстр с 50 единицами здоровья. А герой может совершать разные типы атаки, которые отнимают разное количество здоровья босса. Но особые атаки имеют «время отката» и после их использования они недоступны какое-то количество ходов. Найти, сколько есть способов убить монстра.

Превью