⏩️ 10 лампочек ⏪️
Решение вчерашней задачи основано на простой, но важной мысли: каждая лампочка переключается столько раз, сколько у её номера делителей.
Например, лампочка под номером 6 переключается при проходах 1-го, 2-го, 3-го и 6-го человека, то есть всего 4 раза. Так как это число чётное, в итоге (после выхода 100-го человека) лампочка будет выключена.
А лампочка под номером 9 — при 1-м, 3-м и 9-м, то есть 3 раза. Число нечётное, значит, в итоге лампочка останется включённой.
Тем самым ключевое наблюдение: если у числа чётное число делителей, лампочка выключится, а если нечётное — останется включённой.
Обычно делители числа разбиваются на пары: если d — делитель числа n, то n/d — тоже делитель.
Например, вот 3 пары для всех 6 делителей числа 12: (1, 12), (2, 6), (3, 4). Понятно, что если все делители разбились на пары, значит, их число чётное.
Но когда же у числа нечётное число делителей❓
Есть только одно исключение из общего правила — это полные квадраты.
Рассмотрим, например, число 36. Его пары делителей — это (1, 36), (2, 18), (3, 12), (4, 9), (6, 6). Но, как мы видим, последняя пара на самом деле состоит из одного и того же числа. Всё дело в том, что если число n — полный квадрат, то для делителя d = √n значение n/d также равно √n.
Таким образом, он не образует пару с другим числом, а остаётся «одиночкой». Так и получается, что у полных квадратов, и только у них, нечётное количество делителей.
Следовательно, включёнными останутся именно те лампочки, номера которых являются полными квадратами, а это 10 лампочек с номерами 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.
*️⃣Отдельное спасибо говорим нашему подписчику @kevlarius. Он предложил решение с помощью программирования. Получилось очень наглядно: звездочка — горящая лампочка, точка — выключенная, на исходном шаге — все звездочки, а на финальном — только 10 штук.
class Lamp:
def __init__(self, state=False):
self.state = state
def switch_state(self):
self.state = not self.state
if __name__ == '__main__':
lamps = [Lamp() for _ in range(100)]
step = 1
for p in range(100):
index = (step - 1)
while index < len(lamps):
lamps[index].switch_state()
index = index + step
step += 1
lamps_str = "".join(("*" if lamp.state else ".") for lamp in lamps)
print(f"{p + 1:3}: {lamps_str}")
#задача