Чистая математика, физика, логика (braingames.ru): задачки для мозгов, не связанные с торговлей - страница 58

Новый комментарий
 
DmitriyN:
Отсюда: У всех лестниц четко определен низ и верх.
Там не имеется в виду, что у лестниц всегда есть верхняя и нижняя ступенька.  Там сказано, что у лестниц есть верх и низ, т.е. их нельзя переворачивать. Т.е. зеркально симметричные относительно верха/низа лесенки - неодинаковы.
 
Mathemat:

80 мегамозгов встали в виде прямоугольника 10×8. В каждом продольном ряду нашли самого высокого, среди них самым низким оказался мегамозг с собакой. Затем нашли в каждом поперечном ряду самого низкого, среди них самым высоким оказался мегамозг в шляпе. Спрашивается, кто выше: мегамозг с собакой или в шляпе?

На 4ке вроде похожая была.

X >= Y >= Z --> X >= Z

 
Mathemat:

(5)

Мегамозг хочет забраться на крышу своего дома по приставной лестнице. В кладовке лежит много лестниц, но, к сожалению, у большинства из них не хватает ступенек. По лестницам, у которых отсутствуют две ступеньки подряд, Мегамозг забраться не может. Все его лестницы изначально были с N ступеньками. У всех лестниц четко определен низ и верх. Сколько существует вариантов лестниц, по которым Мегамозг мог бы забраться?

Текс, всё проще.  Нарисовалась последовательность кроликов Фибоначчи.

F(1) = 2

F(2) = 3

F(N) = F(N-1)+F(N-2)

// Не знаю, есть ли нерекуррентная формула.  У меня пока не сложилась.

 
TheXpert:

Уверен?

F(1) = 1

F(2) = 2

F(3) = 4

F(4) = 7

F(5) = 12

F(6) = 19

F(7) = 33 (???)

Уверен.

При одной ступеньке 2 варианта (есть/нет)

При двух = три варианта (обе есть, без первой, без второй)

и т.д.

Моя формула правильная.


Ъ

 
MetaDriver:

Моя формула правильная.

Да, наверное. Я целую лестницу не считал и где-то для 6 недосчитал.
 

Рекуррентная формула е, но не такая простая у меня. Но следствие и само решение - действительно числа Фибоначчи F(N+2). Осталось только привести корректное доказательство. MD, откуда ты свою формулу выкопал? Просто подсчетом вариантов для небольших чисел?

У меня есть полный вывод формулы. Пока подожду.

 
TheXpert:

На 4ке вроде похожая была.

X >= Y >= Z --> X >= Z

А пояснить можешь, что за букафки такие?
 
Mathemat:

Рекуррентная формула е, но не такая простая у меня. Но следствие и само решение - действительно числа Фибоначчи F(N+2). Осталось только привести корректное доказательство. MD, откуда ты свою формулу выкопал? Просто подсчетом вариантов для небольших чисел?

У меня есть полный вывод формулы. Пока подожду.

Пусть c(n) - число лестниц  с n  ступеньками, на которые ММ не может залезть. Рассмотрим следующие варианты:

    1   0 

1  0   0

Здесь приведены нижние ступени трех серий лестниц, 1 - есть ступенька,  0 - нет. Очевидно, что, при n >= 2

c(n) = c(n-1) + c(n-2) + 2^(n-2), понятно, что c(0) = 0, c(1) = 0          (1)

Общее число лестниц, на которые можно влезть выражается формулой:  2^n  - c(n) =? F(n+2)

Докажем это. Определим функцию

f(n+2) =  2^n  - c(n); вычислим f(2) = 1, f(3) = 2 совпадает с соответствующими числами Фибоначчи. (2)

Для n > 1 подставляем значение c(n) из (2) в (1), получаем

2^n - f(n+2) = 2^(n-1) - f(n+1) + 2^(n-2) - f(n) + 2^(n-2), степени двоек сокращаются, получаем:

f(n+2) = f(n+1) + f(n), С учетом вычисленных значений  f(2) = F(2) = 1, f(3) = F(3) = 2, очевидно, что f(n+2) = F(n+2)

 

У меня, кстати, другое решение (степеней двойки нет):

Считаем, что N >= 2. Разрежем лестницу между 1-й и 2-й перекладинами (точнее, между местами для них). Наверху будет маленькая лестница c N-1 местами для ступенек, внизу - с одним местом. Обе будут гарантированно правильными, но некоторых ступенек обычно будет не хватать.

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

Для удобства введем такие обозначения: число правильных лестниц порядка n и с отсутствующей нижней ступенькой обозначим как q(n; false), а с присутствующей нижней ступенькой - как q(n; true). При этом число всех правильных лестниц порядка n обозначим как q(n).

Есть два случая:

1. Верхняя лестница имеет нижнюю ступеньку. Тогда общее число "составных" лестниц порядка N равно q(N-1; true) * 2, т.к. число правильных лестниц порядка 1 равно 2.

С другой стороны, очевидно, q(N-1; true) = q(N-2). Поэтому общее число правильных вариантов для этого случая будет равно 2*q(N-2).

2. У верхней лестницы нижней ступени нет. Общее число составных лестниц порядка N равно q(N-1; false) * 1, т.к. нижняя лестница порядка 1 обязана иметь ступень, чтобы составная лестница была правильной.

С другой стороны, q(N-1; false) = q(N-2; true) = q(N-3). Поэтому общее число правильных вариантов равно q(N-3).

Следовательно, имеем рекуррентное соотношение:

q(N) = 2*q(N-2) + q(N-3).

Оно линейно, и хар. уравнение для него следующее:

z^3 - 2*z - 1 = 0

Оно, очевидно, раскладывается на множители:

(z + 1) * (z^2 - z - 1) = 0.

Отсюда корни равны z_1 = ( 1 + sqrt(5) ) / 2 = fi, z_2 = 1 - fi, z_3 = -1.

Общее решение уравнения - это линейная комбинация

q(n) = C_1*z_1^n + C_2*z_2^n + C_3*z_3^n (***).

Подсчет вручную для нескольких первых вариантов дает следующие числа вариантов - числа Фибоначчи(F_0 = 0, F_1 = 1):

q(1) = 2 = F_3,
q(2) = 3 = F_4,
q(3) = 5 = F_5,
q(4) = 8 = F_6,
q(5) = 13 = F_7, и т.п.

Закономерность очевидна. Подставляем в (***):

F_3 = C_1*z_1 + C_2*z_2 - C_3 (***).

F_4 = C_1*z_1^2 + C_2*z_2^2 + C_3 (***).

F_5 = C_1*z_1^3 + C_2*z_2^3 - C_3 (***).

Вначале заметим, что из этих трех уравнений к-ты C_i определяются однозначно (главный определитель системы - это почти определитель Вандермонда, который не равен нулю). С другой стороны, получаются буквально числа Фибоначчи, если C_1 = 1/sqrt(5) = -C_2, а C_3 = 0.

Отсюда и ответ: число правильных лестниц порядка N равно F_{N+2}.
 
Mathemat:

У меня, кстати, другое решение (степеней двойки нет):

Для Фибоначчи верно такое же рекуррентное соотношение: q(N) = 2*q(N-2) + q(N-3).

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

1...515253545556575859606162636465...229
Новый комментарий