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

[tima]

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

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

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

Comments

[yyi.livejournal.com]

Разложение на множители (factoring) не NP-complete (т.к both factoring and primality are in NP - из чего следует что вряд ли один из них может быть NP-complete; принадлежность primality к NP - относительно новый результат).
Но задача factoring действительно сложна, тем не менее (по крайней мере если брать произведения очень больших простых чисел), и действительно на ней основывается большая часть современной криптографии (public key crypto).
A комбинаторная формула довольно проста - каждый простой делитель увеличивает количество делителей в количество раз на 1 большее его степени (т.е. количество вариантов учитывания этого делителя от 0 до степени - учитывание 0 и дает увеличение на 1)
Напр. 48=2^4 *3; кол-во делителей= 5*2=10 (где 5=4+1 от 2 и 2=1+1 от 3).
А 72=2^3 *3^2; кол-во делителей= 4*3=12.

[tima.livejournal.com]

спасибо за формулу! таки сходится - 60, 72, 96...

[inostranka.livejournal.com]

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

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