Задачи на комбинаторику

      Числа Фибоначчи находят широкое применение при решении задач по комбинаторике.

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

Задача №1:

Леша поднимается по лестнице из 10 ступенек. За один раз он прыгает вверх либо на одну ступеньку, либо на две ступеньки. Сколькими способами Леша может подняться по лестнице?

Решение:

Число способов, которыми Леша может подняться на лестницу из n ступенек, обозначим а_n. Отсюда следует, что a₁ = 1, a₂ = 2 (ведь Леша прыгает либо на одну, либо через две ступеньки).

Оговорено также, что Леша прыгает по лестнице из n > 2 ступенек. Предположим, с первого раза он прыгнул на две ступеньки. Значит, по условию задачи, ему нужно запрыгнуть еще на n – 2 ступеньки. Тогда количество способов закончить подъем описывается как a_n–2. А если считать, что в первый раз Леша прыгнул только на одну ступеньку, тогда количество способов закончить подъем опишем как a_n–1.

Отсюда получаем такое равенство: a_n = a_n–1 + a_n–2 (выглядит знакомо, не правда ли?).

Раз мы знаем a₁ и a₂ и помним, что ступенек по условию задачи 10, вычисли по порядку все а_n: a₃ = 3, a₄ = 5, a₅ = 8, a₆ = 13, a₇ = 21, a₈ = 34, a₉ = 55, a₁₀ = 89.

Ответ: 89 способов.

Задача №2:

Требуется найти количество слов длиной в 10 букв, которые состоят только из букв «а» и «б» и не должны содержать две буквы «б» подряд.

Решение:

Обозначим за a_n количество слов длиной в n букв, которые состоят только из букв «а» и «б» и не содержат двух букв «б» подряд. Значит, a₁ = 2, a₂ = 3.

В последовательности a₁, a₂, <…>, a_n мы выразим каждый следующий ее член через предыдущие. Следовательно, количество слов длиной в n букв, которые к тому же не содержат удвоенной буквы «б» и начинаются с буквы «а», это a_n–1. А если слово длиной в n букв начинается с буквы «б», логично, что следующая буква в таком слове – «а» (ведь двух «б» быть не может по условию задачи). Следовательно, количество слов длиной в n букв в этом случае обозначим как a_n–2 . И в первом, и во втором случае далее может следовать любое слово (длиной в n – 1 и n – 2 букв соответственно) без удвоенных «б».

Мы смогли обосновать, почему a_n = a_n–1 + a_n–2.

Вычислим теперь a₃ = a₂ + a₁ = 3 + 2 = 5, a₄ = a₃ + a₂ = 5 + 3 = 8, <…>, a₁₀ = a₉ + a₈ = 144. И получим знакомую нам последовательность Фибоначчи.

Ответ: 144.

                                      1.6 ЗОЛОТОЕ СЕЧЕНИЕ

    Золотое сечение – деление целого (например, отрезка) на такие части, которые соотносятся по следующему принципу: большая часть относится к меньшей так же, как и вся величина (например, сумма двух отрезков) к большей части. Первое упоминание о золотом сечении можно встретить у Евклида в его трактате «Начала» (примерно 300 лет до н.э.). В контексте построения правильного прямоугольника. Привычный нам термин в 1835 году ввел в оборот немецкий математик Мартин Ом. Если описывать золотое сечение приблизительно, оно представляет собой пропорциональное деление на две неравных части: примерно 62% и 38% (Рис.3). В числовом выражении золотое сечение представляет собой число 1,6180339887. Золотое сечение находит практическое применение в изобразительном искусстве (картины Леонардо да Винчи и других живописцев Ренессанса), архитектуре, кинематографе («Броненосец «Потемкин» С. Эзенштейна) и других областях. Долгое время считалось, что золотое сечение – наиболее эстетичная пропорция. Такое мнение популярно и сегодня. Хотя по результатам исследований визуально большинство людей не воспринимают такую пропорцию наиболее удачным вариантом и считают слишком вытянутой (непропорциональной).