2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Комбинаторика, числа Фиббоначи
Сообщение03.11.2014, 16:54 
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$-е число Фибоначчи.

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

 
 
 
 Re: Комбинаторика, числа Фиббоначи
Сообщение03.11.2014, 17:00 
3) Составьте рекуррентное соотношение для числа способов.

 
 
 
 Re: Комбинаторика, числа Фиббоначи
Сообщение03.11.2014, 18:10 
nnosipov в сообщении #925924 писал(а):
3) Составьте рекуррентное соотношение для числа способов.

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

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

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

 
 
 
 Re: Комбинаторика, числа Фиббоначи
Сообщение03.11.2014, 18:25 
Аватара пользователя
У семи нянек, they say...

 
 
 
 Re: Комбинаторика, числа Фиббоначи
Сообщение03.11.2014, 18:30 
Кстати, что там с первой? У меня получается, что нельзя, слишком большое наименьшее общее кратное получается.

 
 
 
 Re: Комбинаторика, числа Фиббоначи
Сообщение03.11.2014, 18:35 
Аватара пользователя
Нет, почему, можно. Куча их.

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

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

 
 
 
 Re: Комбинаторика, числа Фиббоначи
Сообщение03.11.2014, 18:43 
Да, Вы правы, я почему-то остановился на $2^63^4+7$, а надо было взять $2^63^35^1+7$.

 
 
 
 Re: Комбинаторика, числа Фиббоначи
Сообщение03.11.2014, 18:48 
Аватара пользователя
Верите ли, Ваш кандидат даже не в первой двадцатке. Хотя тоже годится, кнчн, там же не просили минимальное.

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

 
 
 
 Re: Комбинаторика, числа Фиббоначи
Сообщение04.11.2014, 02:10 
ИСН в сообщении #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$.

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

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

 
 
 
 Re: Комбинаторика, числа Фиббоначи
Сообщение04.11.2014, 02:40 
ИСН в сообщении #926301 писал(а):
Попробуем ещё раз. Положим, мы уже нашли количество способов для любых $n<100$, теперь ищем для 100. Первый шаг - это либо на одну клеточку, либо на две, других вариантов тупо нет.
Если мы шагнули на одну клеточку, то сколько клеточек осталось пройти и сколькими способами это можно сделать?
Если мы шагнули на две клеточки, то сколько клеточек осталось пройти и сколькими способами это можно сделать?

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

 
 
 
 Re: Комбинаторика, числа Фиббоначи
Сообщение04.11.2014, 03:09 
Аватара пользователя
Вот! Вот оно! Ну а всего вместе, значит, сколько способов?

 
 
 [ Сообщений: 30 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group