flaass'а: вот тут (если оно непонятно из записи - загляните в комментарии, я там немного разжевал).Во-вторых, вот новая задачка (далеко не такая сложная :)), из внутренней рассылки на работе. Странно, мне казалось, что я ее когда-то уже решал, но как ни силился, не вспомнил решения и не нашел упоминания в ЖЖ или другом месте. Может, ложная память; так или иначе, решил заново, с удовольствием (хотя, возможно, не самым экономным путем).
На лугу у фермера пасутся овцы, сбившись в группы. Фермер заметил, что ровно раз в час происходит следующее: от каждой группы отходит одна овца, и все эти отошедшие овцы вместе сбиваются в новую группу. Кроме этой операции, состав групп остается неизменен.
Через какое-то время фермер замечает, что количество и размер групп стабилизировались, т.е. после каждой операции, описанной выше, ничего не меняется.
1) Каким должно быть общее число овец, чтобы это было возможно?
2) Верно ли, что если число овец такое, как в ответе на первый вопрос, т.е. стабилизация возможна, то она обязательно произойдет?
Комментарии скрывать не буду, так что не заглядывайте, если хотите решить сами.
Небольшое пояснение. Первый вопрос совсем легкий (и в комментариях есть уже несколько верных ответов, и один с доказательством). Второй посложнее.
← Ctrl ← Alt
Ctrl → Alt →
← Ctrl ← Alt
Ctrl → Alt →