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

[tima]

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

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

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

Comments

[inostranka.livejournal.com]

Формула для первого вопроса - корень из числа ящиков.
Второй вопрос - важна разница между множителями и делителями (это к сравнению 48-и и 72-ух, ниже).
48 = 10 делителей: 1-48, 2-24, 3-16, 4-12, 6-8, но 5 множителей простых (2^4 * 3)
72 = 12 делителей: 1-72, 2-36, 3-24, 4-18, 6-12, 8-9, но тоже 5 простых множителей (2^3 * 3^2)

Кстати, я не знаю, есть ли формула для количества делителей у числа. Насколько я помню, нахождение разложения на простые множители NP-complete, и на этом даже криптография строится, если я не ошибаюсь. Но даже если найти это самое разложение (то есть, 48 = 2 * 2 * 2 * 2 * 3) то все равно не ясно как из этого найти число делителей - это комбинаторная выборка из простых множителей, да еще и без повторения. Если найдете формулу, интересно будет посмотреть.

[tima.livejournal.com]

вряд ли буду искать формулу. Французик не откликнулся, а я на него расчитывал... некогда, особенно сразу по приезду с отстутствие дома 9 дней... Навалились изверги со всех сторон!

Спасибо за помощь! По крайней мере знаю как объяснить на пальцах первый вопрос.

[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 все равно работает, так как разложение (для очень больших чисел) сложно найти.