Розселення кроликів на цілочисельній прямій
Умова задачі
Підземна нора складається з нескінченної послідовності кімнат, занумерованих цілими числами . Спочатку деякі з кімнат зайняті одним або кількома кроликами.
Кожен кролик хоче бути сам. Тому, якщо в одній кімнаті (скажімо, в кімнаті ) є двоє або більше кроликів, то половина кроликів (з округленням униз) втече до кімнати , а половина (також з округленням униз) — до кімнати . Раз на хвилину це відбувається одночасно в усіх кімнатах, де є двоє або більше кроликів. Наприклад, якщо спочатку всі кімнати порожні, крім 5 кроликів у кімнаті №12 і 2 кроликів у кімнаті №13, то через хвилину в кімнатах №11–№14 буде відповідно 2, 2, 2 і 1 кролики, а всі інші кімнати будуть порожні.
Тепер припустимо, що спочатку в кімнаті є кроликів для кожного , а всі інші кімнати порожні.
a. Доведіть, що зрештою кролики перестануть рухатися.
b. Визначте, які кімнати будуть зайняті, коли це станеться.