Помощь клуба...

[tima]

Ребенку задали довольно известную задачу про ящики - 100 ящиков, 100 учеников, сначала все ящики закрыты, каждый ученик меняет "позицию" ящика - если был открыт, то закрывает и наоборот. Первый ученик начинает с первого ящика и "трогает" каждый. Второй - со второго и идет только по четным, третий - с третьего и идет через два (меняет третий, шестой и т.д.) и т.д. до 100.

Вопросы:
- какие останутся открытыми (ответ - квадраты чисел до 10, хотя объяснить ребенку толком не могу)?
- какие ящики будут "тронуты" чаще других и объяснить почему. Все знаю, объяснить результат опять-таки не могу.

Всем спасибо.

Comments

[inostranka.livejournal.com]

Да, спасибо, чего-то я протормозила с комбинаторной формулой.

Про разложение на множители - что-то я теперь начинаю припоминать, что определили про не NP-completeness, но при этом public key encryption все равно работает, так как разложение (для очень больших чисел) сложно найти.