Последовательность Фибоначчи, часть 1

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

Логическая головоломка

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

Не зная, какой сегодня день, вы слышите следующие высказывания.

Единорог, "Вчера был один из тех дней, когда я лгал".

Пегас: «Вчера был и один из тех дней, когда я лгал».

Какой сегодня день?

Последовательность Фибоначчи, часть 1

Позвольте мне начать обсуждение с математической задачи.

Если подбросить честную монету 20 раз, какова вероятность того, что вам никогда не выпадут два орла подряд?

Первый бросок – существует две успешные комбинации и две общие комбинации, поэтому вероятность 2/2 = 100% означает, что мы никогда не увидим двух орлов подряд. Другими словами, невозможно увидеть двух орлов за один бросок.

Второй бросок – существует три успешные комбинации (HT, TH, TT), и всего ^2² = 4 комбинации, что дает вероятность ¾ = 75%. Мы никогда не увидим двух орлов подряд за два броска.

Третий бросок – существует пять успешных комбинаций (HTT, HTH, THT, TTH, TTT), а общее количество комбинаций составляет 2³ = 8, что дает вероятность 5/8 = 62,5%. За три броска мы ни разу не увидели двух орлов подряд.

Однако подсчет успешных комбинаций на этом этапе начинает становиться утомительным. Давайте попробуем другой подход. Если при третьем броске выпадает решка, то все успешные комбинации после двух бросков все равно будут считаться действительными. Другими словами, мы можем просто добавить решку ко всем комбинациям после двух бросков: HTT, THT, TTT.Если при третьем броске выпадает орел, то любая комбинация после первого броска будет успешной, если добавить после него TH: HTH, TTH. Таким образом, общее количество успешных комбинаций составляет 3, если при третьем броске выпадает решка, и 2, если орел, то есть всего 5.

Четвертый бросок – Если выпала решка, мы можем использовать все комбинации из третьего броска, которых было 5, и добавить к каждой по одной букве «Т». Если выпала орел, мы возвращаемся ко второму броску и добавляем к каждой по одной букве «Т». Всего комбинаций 5+3=8.

Вы видите закономерность? Закономерность, начинающаяся с двух единиц, причем каждая последующая единица является суммой двух предыдущих, выглядит так: 1, 1, 2, 3, 5, 8, 13, 21, 34, … и известна как последовательность Фибоначчи. Именно это мы и делаем здесь, возвращаясь на одну единицу назад, если последний бросок был решкой, и на две единицы назад, если это был орел.

В следующей таблице показано количество успешных комбинаций, общее количество комбинаций и вероятность того, что не будет двух орлов подряд при бросках от 1 до 20. Вероятность — это количество успешных комбинаций, деленное на общее количество комбинаций, которое равно 2^n, где n — количество бросков. В нижней строке показана вероятность того, что не будет двух орлов подряд, равная 17711/1048576 ≈ 1,69%.

Это лишь один из примеров практического применения последовательности Фибоначчи. На следующей неделе мы подробнее рассмотрим это на примере отношения двух последовательных членов последовательности.

Ответ на логическую головоломку

Четверг

Решение логической головоломки

Давайте сначала рассмотрим утверждение единорога. Оно согласуется с правдивостью высказывания единорога только по понедельникам и четвергам.

Давайте рассмотрим утверждение Пегаса во-вторых. Оно согласуется с правдивостью слов единорога только в четверг и воскресенье.