Счастливые узники

[fortpost]

Некий тюремщик, осуществляя частичную амнистию, поступил следующим образом. Сначала он открыл все камеры. Затем запер каждую вторую камеру (в этой тюрьме все камеры были расположены в один ряд). На третьем этапе он повернул ключ в каждой третьей камере (при очередном повороте ключа открытая камера запирается, а закрытая отпирается). Продолжая действовать подобным образом, тюремщик на n-м этапе поворачивал ключ в каждой n-й камере. Закончив на этом, он выпустил всех заключенных, которые оказались в открытых камерах. Укажите номера камер, в которых сидели эти счастливчики.

[Tim]

1, 4, 9, 16 и т.д. полные квадраты ИМХО

[fortpost]

1, 4, 9, 16 и т.д. полные квадраты ИМХО

Верно, Tim0512! А вот как доказать?

[Tim]

Ну я так думал: чтобы были свободны нужны номера камер, где количество поворотов ключей будет нечетно. Чтобы оно было нечетно количество делителей должно быть нечетно у номера соответствущей мамеры. А это выполняется только для чисел, являющихся точными квадратами (это доказательство я не помню, давно в школе было). Если надо помучаю

[moonlight]

каждый  квадрат представляется в виде p₁^2k₁p₂^2k₂...p_n^2k_n.

всего делителей (2k₁+1)(2k₂+1)...(2k_n+1).

[fortpost]

Ну я так думал: чтобы были свободны нужны номера камер, где количество поворотов ключей будет нечетно. Чтобы оно было нечетно количество делителей должно быть нечетно у номера соответствущей мамеры. А это выполняется только для чисел, являющихся точными квадратами (это доказательство я не помню, давно в школе было). Если надо помучаю

Ну да, в принципе оно так.

[General]

Да-да. Или проще (на уровне 4-го класса):
Каждому делителю числа соответствует парный ему, равный частному от деления. И только для квадрата корню пары не будет.