Задача 7.
На окружности расположены 1024 белых домика. Тридцать два гнома красят дома в синий цвет (изначально гномики могут стоять у любого дома, но не красят его). За один ход первый гном перемещается по окружности вправо или влево, второй — на два дома вправо или влево, третий — на 3 и так далее, тридцать второй — на 32. И одновременно красят дом, рядом с которым оказались. Если несколько гномов оказалось около одного дома, то они вместе его красят. В некоторый момент оказалось, что все дома синие. Докажите, что хотя бы один гном за это время красил уже покрашенный дом.
Ответ на Задачу 7.
Заметим, что за ход все гномики красят суммарно не более 32 домиков (могут меньше, если несколько красят одновременно один). Таким образом, для покраски всех домов понадобится не менее 1024 : 32 = 32 ходов. С другой стороны, если никто не красил уже покрашенный дом, то после второго хода каждый гномик не мог пойти в обратном направлении. То есть, как минимум со второго хода каждый гном своим ходом сохраняет своё направление. Тогда посмотрим на того гномика, который шагает на 32 хода. Если он совершит 33 хода, то пройдёт больше круга и наткнется на свой домик, который уже красил. Таким образом, он не может ходить больше 32 раз. Объединяя с оценкой, написанной выше, получим, что у нас всего произошло 32 хода. Тогда посмотрим теперь на гномика, шагающего на один дом. За 32 хода он покрасит 32 подряд идущих домика. А из 32 домиков один был покрашен гномиком с самым длинным ходом. Но тогда либо кто-то из них красил уже крашеный дом, либо же они один дом красили одновременно. Но если они дом красили одновременно, то в этот ход было закрашено не больше 31 дома, то есть понадобится 33 ход. А в 33 ход гномик с самым длинным ходом наткнется на дом, который он уже красил. Таким образом, хотя бы один гном будет красить уже покрашенный дом.
