Комбинаторика, числа Фиббоначи

[Don-Don]

1) Костя задумал четырехзначное число и написал остатки от деления этого числа на 2, на 3, . . . , на 101 (всего 100 остатков). Могло ли среди выписанных чисел оказаться не менее 20 семерок?
Остаток 7 может выйти при делении на 8,9,10,11,12,13....,101.
Таких чисел не более 94, но насчет не менее -- тут сложнее. С чего начать?


2) В селе Ивановском живут более 100 человек. Житель села называется общительным, если у него не менее 100 знакомых среди односельчан. Докажите, что в Ивановском найдутся либо два знакомых между собой общительных жителя, либо два незнакомых между собой необщительных жителя.
Можно попробовать от противного? Попробуем доказать, что не найдутся таких двое знакомых.
а) Пусть нашелся один общительный, попробуем предположить, что ему не нашлось пары -- нет больше общительных. Значит не менее 100 необщительных. Значит среди них можно найти двух необщительных. Противоречие.
б) Пусть нашелся один необщительный, проверим -- есть ли для него пара. Если нет, то найдутся два общительных, противоречие.
Ч.т.д. Верно ли это?


3) Соня нарисовала на бумаге полоску $1\times n$ клеточек и поставила в крайнюю левую клеточку фишку. Катя хочет передвинуть фишку в крайнюю правую клеточку, двигая ее каждым ходом на одну или две клеточки вправо. Докажите, что она может это сделать ровно $F_n$ способами, где $F_n$ — $n$-е число Фибоначчи.

Что такое числа Фиббоначи -- знаю, но не пойму -- причем тут они?

[nnosipov]

3) Составьте рекуррентное соотношение для числа способов.

[Don-Don]

nnosipov в сообщении #925924 писал(а):

3) Составьте рекуррентное соотношение для числа способов.

А как его составить, просто исходя из закономерности? Или как? По индукции его обосновывать?

[ИСН]

Положим, мы уже нашли количество способов для любых $n<100$, теперь ищем для 100. Первый шаг - это либо на одну клеточку, либо на две, других вариантов тупо нет.
Если мы шагнули на одну клеточку, то какие дальше варианты? (Или - чёрт с ними, какие; сколько их?)
Если мы шагнули на две, то...

[nnosipov]

Don-Don в сообщении #925921 писал(а):

Катя хочет передвинуть фишку в крайнюю правую клеточку, двигая ее каждым ходом на одну или две клеточки вправо.

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

[ИСН]

У семи нянек, they say...

[nnosipov]

Кстати, что там с первой? У меня получается, что нельзя, слишком большое наименьшее общее кратное получается.

[ИСН]

Нет, почему, можно. Куча их.

-- менее минуты назад --

Исходя из чисел, у которых много делителей вообще, а в частности - много небольших делителей...

[nnosipov]

Да, Вы правы, я почему-то остановился на $2^63^4+7$, а надо было взять $2^63^35^1+7$.

[ИСН]

Верите ли, Ваш кандидат даже не в первой двадцатке. Хотя тоже годится, кнчн, там же не просили минимальное.

[nnosipov]

Да верю, в общем, задачка вполне себе нормальная, без особых выкрутасов. Может, ТС её уже и сам решил? Хотелось бы.

[Don-Don]

ИСН в сообщении #925977 писал(а):

Положим, мы уже нашли количество способов для любых $n<100$, теперь ищем для 100. Первый шаг - это либо на одну клеточку, либо на две, других вариантов тупо нет.
Если мы шагнули на одну клеточку, то какие дальше варианты? (Или - чёрт с ними, какие; сколько их?)
Если мы шагнули на две, то...

Последний ход можно сделать 2 способами, предпоследний 3 способами, предпредпоследний 5 способами итп, все сходится. Вижу уже Фибоначчи. Но можно ли это считать доказательством? Или это только база индукции? Если делать индукционный переход, то пока что не очевидно -- как. Будем считать ходы с конца. Предположим, что для $n=k$ ходов существует $F_{k+2}$ способов. Нужно показать, что для $n=k+1$ существует $F_{k+3}$ способов. $F_{k+2}=F_{k}+F_{k+1}$ Но как это сделать?

-- 04.11.2014, 03:13 --

nnosipov в сообщении #926002 писал(а):

Да, Вы правы, я почему-то остановился на $2^63^4+7$, а надо было взять $2^63^35^1+7$.

А с каких чисел вы начали рассмотрение, чтобы такими закончить?

[ИСН]

Попробуем ещё раз. Положим, мы уже нашли количество способов для любых $n<100$, теперь ищем для 100. Первый шаг - это либо на одну клеточку, либо на две, других вариантов тупо нет.
Если мы шагнули на одну клеточку, то сколько клеточек осталось пройти и сколькими способами это можно сделать?
Если мы шагнули на две клеточки, то сколько клеточек осталось пройти и сколькими способами это можно сделать?

[Don-Don]

ИСН в сообщении #926301 писал(а):

Попробуем ещё раз. Положим, мы уже нашли количество способов для любых $n<100$, теперь ищем для 100. Первый шаг - это либо на одну клеточку, либо на две, других вариантов тупо нет.
Если мы шагнули на одну клеточку, то сколько клеточек осталось пройти и сколькими способами это можно сделать?
Если мы шагнули на две клеточки, то сколько клеточек осталось пройти и сколькими способами это можно сделать?

Если шагнули на одну, то осталось пройти 99 клеточек, а число способов это сделать мы знаем. ($F_{99}$?)
Если шагнули на две, то осталось пройти 98, а число способов это сделать мы знаем ($F_{98}$?)

[ИСН]

Вот! Вот оно! Ну а всего вместе, значит, сколько способов?