Помощь клуба...
Oct. 17th, 2004 10:27 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
timaРебенку задали довольно известную задачу про ящики - 100 ящиков, 100 учеников, сначала все ящики закрыты, каждый ученик меняет "позицию" ящика - если был открыт, то закрывает и наоборот. Первый ученик начинает с первого ящика и "трогает" каждый. Второй - со второго и идет только по четным, третий - с третьего и идет через два (меняет третий, шестой и т.д.) и т.д. до 100.
Вопросы:
- какие останутся открытыми (ответ - квадраты чисел до 10, хотя объяснить ребенку толком не могу)?
- какие ящики будут "тронуты" чаще других и объяснить почему. Все знаю, объяснить результат опять-таки не могу.
Всем спасибо.
Вопросы:
- какие останутся открытыми (ответ - квадраты чисел до 10, хотя объяснить ребенку толком не могу)?
- какие ящики будут "тронуты" чаще других и объяснить почему. Все знаю, объяснить результат опять-таки не могу.
Всем спасибо.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2004-10-18 08:07 am (UTC)- Если у номера ящика четное число делителей, то останется закрытым, а если нечетное - открытым. Только у квадратов нечетное число делителей (потому что одна из пар делителей X, X).
- Опять же, чем больше делителей, тем чаще тронут ящик.
Задачка очень хорошая. Мне ее в свое время на интервью задавали.
no subject
Date: 2004-10-18 08:10 am (UTC)1. Любой делитель имеет пару, кроме квадрата. То есть, ящик за номером 8=4*2 тронут на втором и четвертом проходе (и еще на первом и восьмом), а ящик за номером девять тронут на первом-девятом, и еще на третьем ТОЛЬКО, потому что квадрат. Значит, все ящики с "неквадратными" номерами тронут четное число раз, а с квадратными - нечетное.
2. А больше других ящики с максимальным числом множителей.
no subject
Date: 2004-10-18 08:21 am (UTC)Немного неверно. Чем больше РАЗНЫХ делителей. А вот как узнать у которых чисел их больше, этих разных... Опять же - где та формула? ДО 100 можно сделать и "руками", но если не 100, а больше?
no subject
Date: 2004-10-18 08:23 am (UTC)и на второй вопрос слегка неверно. Нужны РАЗНЫЕ множители.
no subject
Date: 2004-10-18 08:24 am (UTC)no subject
Date: 2004-10-18 08:29 am (UTC)После рассуждений о квадратах понятно, что разные. И еще - не только простые.
no subject
Date: 2004-10-18 08:36 am (UTC)Просто в квадратах столько же множителей, но два их них - одни и те же, а значит это один и тот же человек!
На второй вопрос все же непонятно как без ручной проверки "вычислить" эти самые "частые" номера. Можно конечно пойти от обратного - сделать 2 * 2 * 3 * 5 (это дает 2, 3, 4, 5, 6, 10, 12, 15, 20...) то есть 60. Потом так же 2 * 2 * 3 * 7... Но неохота делать "вручную"...
no subject
Date: 2004-10-18 08:36 am (UTC)no subject
Date: 2004-10-18 08:48 am (UTC)Второй вопрос - важна разница между множителями и делителями (это к сравнению 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) то все равно не ясно как из этого найти число делителей - это комбинаторная выборка из простых множителей, да еще и без повторения. Если найдете формулу, интересно будет посмотреть.
no subject
Date: 2004-10-18 08:50 am (UTC)no subject
Date: 2004-10-18 08:52 am (UTC)Спасибо за помощь! По крайней мере знаю как объяснить на пальцах первый вопрос.
no subject
Date: 2004-10-18 08:53 am (UTC)no subject
Date: 2004-10-18 10:48 am (UTC)Но задача 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.
no subject
Date: 2004-10-18 10:53 am (UTC)48 -> 10
72 -> 12
12>10 as you say.
no subject
Date: 2004-10-18 11:02 am (UTC)no subject
Date: 2004-10-18 11:05 am (UTC)no subject
Date: 2004-10-18 11:39 am (UTC)I would count the number of different prime divisors and their "redundancy". Then the number of different (not necessarily prime) divisors is as in my formula above (and as expected is greater for 72 than for 48).
no subject
Date: 2004-10-18 11:50 am (UTC)Thanks!
no subject
Date: 2004-10-18 12:46 pm (UTC)Про разложение на множители - что-то я теперь начинаю припоминать, что определили про не NP-completeness, но при этом public key encryption все равно работает, так как разложение (для очень больших чисел) сложно найти.