задачка

[avva]

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

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

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

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

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

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

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

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

Comments

[arhi-ebi-scop.livejournal.com]

час t : существует группа с кол. овец n = равному кол. групп в t-1.
час (t+1) : новообразованная группа равна (n+1-m) - где m=кол. исчезнувших групп при переходе от t-1 к t. Также существует группа n-1 (бывшая n).
Таким образом, если m=1, то образованные группы упорядоченны и останутся таковыми и на "следующем круге", востав из пепла в том же порядке.
на отрезках m=0 шаг становиться +2,+2,+2 вместо +1, но уже на следующем круге они начинают "сходиться" к +1, +1, +2 и. т.д.
для m>=3 следующий оборот превращается в m=2.
Тут должно быть, что то эллегантное, доказывающие, что n(n+1)/2 - оно само построится, но уже поздно и у меня нет места на полях.

[sedoi-wolk.livejournal.com]

а можно спросить, если всего овец у фермера 2 и они являются 2 группами овец - разве это не та же самая усточивая система, описанная в задаче?

То есть и 2 и 4 и 5 являются решениями задачи,е сли они изначально были разбиты в группы овец по одной штуке:) Если выполнять условия задачи- система стабильна.

[arhi-ebi-scop.livejournal.com]

В данном случае стабилизация определена (условиями задачи), как не изменение при любом переходе от t к t+1/
В Вашем случае этого не происходит. Вы назвали стабилизацией процесс при котором при шаге k возвращается в исходное положение, то есть положение в (t+k) такое же, как в t. При двух овцах, например, k равно 2, а по условиям задачи должно быть всегда k=1.

[sedoi-wolk.livejournal.com]

для себя объяснил в чем я неправ... по условиям задачи все новые овцы объединяются в одну группу. значит на следующем шаге получится одна новая большая группа:)