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

[Don-Don]

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

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

$F_{100}=F_{98}+F_{99}$

Если обобщить, то можно сказать, что сделали $n-2$ шага $F_{n-2}$ способами, следующий $n-1$ шаг можно сделать $F_{n-1}$ способами, а $n$-ый шаг можно сделать $F_{n-2}+F_{n-1}=F_n$ способами, но разве это можно считать доказательством?

[ИСН]

Философский вопрос. А что вообще можно считать доказательством? Допустим, Вы посчитали вручную число способов для каких-то небольших чисел (не 100, конечно), и убедились, что вот да, для $n-1$ и $n-2$ выходят соответственно $F_{n-1}$ и $F_{n-2}$. Теперь сколько выйдет для $n$? Их сумма. Может ли она как-то отличаться от $F_n$?

[Don-Don]

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

Философский вопрос. А что вообще можно считать доказательством? Допустим, Вы посчитали вручную число способов для каких-то небольших чисел (не 100, конечно), и убедились, что вот да, для $n-1$ и $n-2$ выходят соответственно $F_{n-1}$ и $F_{n-2}$. Теперь сколько выйдет для $n$? Их сумма. Может ли она как-то отличаться от $F_n$?

Не может отличаться! Спасибо большое, понятно

[provincialka]

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

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

Вычесть эту самую семерку из числа и подумать, каким свойством обладает разность.

[Don-Don]

provincialka в сообщении #926357 писал(а):

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

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

Вычесть эту самую семерку из числа и подумать, каким свойством обладает разность.

Спасибо!
Разность $a-7$ должна делиться нацело делится на не менее чем 20 чисел из 1,2,...,101, тогда нужно составлять комбинации из этих чисел, теперь ясно, почему ответ $2^63^35^1+7$.
Вот эти более 20 чисел (только я к ним еще 7 забыл добавить, это комбинации, составленные из $2^63^35^1$):

$2,4,8,16,32,64,6,12,24,48,96,18,36,72,54,15,45,3,9,27,10,20,40,80$

А как со второй задачей быть, за что зацепиться?

[provincialka]

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

А как со второй задачей быть, за что зацепиться?

Примерно так, как вы и начали, только правильно. Вы делаете слишком скоропалительные выводы. Например, если существуют 100 необщительных, то не факт, что они попарно не знакомы между собой. По-крайней мере, вы это не доказали.

Кстати, если удастся довести до конца п. а), то п. б) уже не понадобится.

-- 04.11.2014, 12:37 --

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

Вот эти более 20 чисел (только я к ним еще 7 забыл добавить, это комбинации, составленные из $2^63^35^1$):
$2,4,8,16,32,64,6,12,24,48,96,18,36,72,54,15,45,3,9,27,10,20,40,80$

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

Остаток 7 может выйти при делении на 8,9,10,11,12,13....,101.

Сравните!

[Don-Don]

provincialka в сообщении #926391 писал(а):

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

А как со второй задачей быть, за что зацепиться?

Примерно так, как вы и начали, только правильно. Вы делаете слишком скоропалительные выводы. Например, если существуют 100 необщительных, то не факт, что они попарно не знакомы между собой. По-крайней мере, вы это не доказали.

Кстати, если удастся довести до конца п. а), то п. б) уже не понадобится.

Возьмем одного такого необщительного. Он знаком менее, чем с 100 людьми (из определения необщительности). Ну пусть он знаком со всеми, кроме Васи Петрова. Но Вася Петров тогда тоже не знаком с ним. Получается, что нашлась пара незнакомых. Верно?

-- 04.11.2014, 12:51 --

provincialka в сообщении #926391 писал(а):

-- 04.11.2014, 12:37 --

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

Вот эти более 20 чисел (только я к ним еще 7 забыл добавить, это комбинации, составленные из $2^63^35^1$):
$2,4,8,16,32,64,6,12,24,48,96,18,36,72,54,15,45,3,9,27,10,20,40,80$

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

Остаток 7 может выйти при делении на 8,9,10,11,12,13....,101.

Сравните!

Ой, да!
$2^63^35^1+7$ при делении на следующий список чисел будет давать остаток 7:

$8,16,32,64,6,12,24,48,96,18,36,72,54,15,45,3,9,27,10,20,40,80$ (22 числа)

Верно?

[provincialka]

Насчет п. б) я, пожалуй, поторопилась - что-то сказать надо.
Кстати, Вася Петров какой? Общительный или нет? Почетче надо сказать.

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

Пусть нашелся один общительный, попробуем предположить, что ему не нашлось пары -- нет больше общительных.

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

[Don-Don]

provincialka в сообщении #926401 писал(а):

Насчет п. б) я, пожалуй, поторопилась - что-то сказать надо.
Кстати, Вася Петров какой? Общительный или нет? Почетче надо сказать.

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

Пусть нашелся один общительный, попробуем предположить, что ему не нашлось пары -- нет больше общительных.

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

Вася Петров -- необщительный, хотелось бы, чтобы было так, но ведь не факт же. Что-то очень много вариантво получается тут, запутался(

[provincialka]

Да нет, не много. Просто надо четко их описать.

1. Пусть общительные есть, но нет двух, знакомых между собой. Значит, любой из них (например, Петя) знаком ... с кем? И сколько их?

[Don-Don]

provincialka в сообщении #926423 писал(а):

Да нет, не много. Просто надо четко их описать.

1. Пусть общительные есть, но нет двух, знакомых между собой. Значит, любой из них (например, Петя) знаком ... с кем? И сколько их?

1) Не нашлись два общительных, знакомых между собой. Возьмем одного из них -- Петю. Петя будет знаком с более чем ста необщительных (коли с общительными не знаком). Среди ста необщительных найдется Толя, который знаком менее, чем со ста людьми, то есть существует такой житель необщительный Владимир, которого он не знает. Значит нашлись два необщительных.
2) Нашлись два общительных, значит требования задачи выполнены.
Верно?

[provincialka]

1. А почему существует Владимир? Среди кого? И зачем мы Петю поминали?
2. Нет, не так. То есть это п. 0, очевидный. п. 2 - не нашлось ни одного общительного.

[Don-Don]

provincialka в сообщении #926456 писал(а):

1. А почему существует Владимир? Среди кого? И зачем мы Петю поминали?
2. Нет, не так. То есть это п. 0, очевидный. п. 2 - не нашлось ни одного общительного.

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

Если не нашлось ни одного общительного, то нашлись Толя и Владимир (так как необщительных более ста). Так?

[provincialka]

Вроде верно.

[Don-Don]

provincialka в сообщении #926519 писал(а):

Вроде верно.

Спасибо большое!