Лягушка прыгает по кувшинкам через речку (кувшинки выстроены в линию от берега до берега). За один раз она может прыгнуть на одну или две кувшинки вперед. Сколько у нее возможных способов переправиться если на реке 10 кувшинок?
Лягушка прыгает по кувшинкам через речку (кувшинки выстроены в линию от берега до берега). За один раз она может прыгнуть на одну или две кувшинки вперед. Сколько у нее возможных способов переправиться если на реке 10 кувшинок?
примерно столько, сколько потомства принесет пара кроликов в десятом поколении
Не меньше. Числа Фибоначчи в чистом виде.
Обозначим через F(n) количество путей ведущих на n-ю кувшинку. Тогда по условию F(n+1) = F(n-1) + F(n). Ну и, очевидно, F(0) = F(1) = 1.
Лягушка прыгает по кувшинкам через речку (кувшинки выстроены в линию от берега до берега). За один раз она может прыгнуть на одну или две кувшинки вперед. Сколько у нее возможных способов переправиться если на реке 10 кувшинок?
Видел эту задачу в другом виде:
Сколько способов есть подняться на лестницу из, скажем, 100 ступенек, если каждый раз можно ступать на следующую, или пeрепрыгивать через одну, ступеньку.
Имеется число, десятичная запись которого состоит только лишь из нулей и единиц. Еще про эту десятичную запись известно:
1. она начинается с 11000, а заканчивается 00011
2. всего единиц 33, а нулей 99
3. последовательность 111000111 встречается не более 3 раз
Доказать, что это число не является полным квадратом.
Пусть у нас есть N камешков, которые разделены на несколько групп; конфигурация - это последовательность количеств камешков в группах в убывающем порядке. Например, если N=10, и камешки разделены на 4 группы из 5, 3, 1, 1 камешков, то текущая конфигурация=(5,3,1,1).
Теперь на каждом ходу игры будем делать следующее: из каждой группы возьмем по 1 камешку, и сформируем из них новую группу. Т.е., например, конфигурация (5,3,1,1) перейдет в (4,4,2) (если была группа с одним камешком, то на следующем ходу она исчезает). Ну и так далее, в данном случае
(4,4,2) - (3,3,3,1) - (4,2,2,2) - (4,3,1,1,1) - (5,3,2) - (4,3,2,1), ну а последняя конфигурация уже всегда переходит в себя.
Теперь предположим, что N - так называмое треугольное число, т.е. N=1+2+3+...+k для некоторого k.
(а) доказать, что единственная стабильная (т.е., которая переходит в себя) конфигурация - это (k,k-1,...,3,2,1)
(б) доказать, что, начав из любой конфигурации, мы обязательно достигнем конфигурации из пункта (а)
(в) доказать, что максимальное количество шагов в пункте (б) равно k(k-1), и привести пример конфигурации, для которой нужно в точности столько шагов
bonus pack:
пусть теперь N - не треугольное число, т.е., N=1+2+3+...+(k-1)+m, где 0mk. Доказать что
(г) не существует ни одной стабильной конфигурации
(д) начиная из любой конфигурации, игра в конце концов придет в цикл, и длина этого цикла не больше k
Это мне один американец сказал, когда я у него спросил, почему lieutenant-colonel (подполковник)
в Канаде/Англии произносится лефтенант-кёрнел, а в Америке лютенант-кёрнел.
Пусть у нас есть N камешков, которые разделены на несколько групп; конфигурация - это последовательность количеств камешков в группах в убывающем порядке. Например, если N=10, и камешки разделены на 4 группы из 5, 3, 1, 1 камешков, то текущая конфигурация=(5,3,1,1).
Теперь на каждом ходу игры будем делать следующее: из каждой группы возьмем по 1 камешку, и сформируем из них новую группу. Т.е., например, конфигурация (5,3,1,1) перейдет в (4,4,2) (если была группа с одним камешком, то на следующем ходу она исчезает). Ну и так далее, в данном случае
(4,4,2) - (3,3,3,1) - (4,2,2,2) - (4,3,1,1,1) - (5,3,2) - (4,3,2,1), ну а последняя конфигурация уже всегда переходит в себя.
Теперь предположим, что N - так называмое треугольное число, т.е. N=1+2+3+...+k для некоторого k.
(а) доказать, что единственная стабильная (т.е., которая переходит в себя) конфигурация - это (k,k-1,...,3,2,1)
(б) доказать, что, начав из любой конфигурации, мы обязательно достигнем конфигурации из пункта (а)
(в) доказать, что максимальное количество шагов в пункте (б) равно k(k-1), и привести пример конфигурации, для которой нужно в точности столько шагов
тогда каждый ход игры будет представлен так:
- сначала (циклически) сдвинем каждый ряд (строку) на одну позицию вправо
- потом шарики падают вниз, если могут.
Здесь показаны два хода: (7,2,1,1) - (6,4,1) - (5,3,3)
заметим теперь, что если N - треугольное число, то конфигурация из пункта (а) имеет такой вид:
(в данном случае k=5)
теперь довольно легко получить (а), (б), (г), (д) (ясно, что если шарикам есть куда падать, то они рано или поздно упадут, посколько ряды таблицы вращаются не совсем синхронно)
что касается пункта (в) - то тут все-таки надо еще немного подумать; скажу только, что пример конфигурации которая дальше всего от стабильной - (k-1,k-1,k-2,...,2,1,1) (т.е, изменилось положение только одного шарика!)
