Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

задачка

Во-первых, решение задачи про светофоры, если оно кому-то интересно, есть в журнале flaass'а: вот тут (если оно непонятно из записи - загляните в комментарии, я там немного разжевал).

Во-вторых, вот новая задачка (далеко не такая сложная :)), из внутренней рассылки на работе. Странно, мне казалось, что я ее когда-то уже решал, но как ни силился, не вспомнил решения и не нашел упоминания в ЖЖ или другом месте. Может, ложная память; так или иначе, решил заново, с удовольствием (хотя, возможно, не самым экономным путем).

На лугу у фермера пасутся овцы, сбившись в группы. Фермер заметил, что ровно раз в час происходит следующее: от каждой группы отходит одна овца, и все эти отошедшие овцы вместе сбиваются в новую группу. Кроме этой операции, состав групп остается неизменен.

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

1) Каким должно быть общее число овец, чтобы это было возможно?

2) Верно ли, что если число овец такое, как в ответе на первый вопрос, т.е. стабилизация возможна, то она обязательно произойдет?

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

Небольшое пояснение. Первый вопрос совсем легкий (и в комментариях есть уже несколько верных ответов, и один с доказательством). Второй посложнее.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 52 comments
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →