Сумма обратных чисел делителей
Я написал такую математическую задачу:
Алиса записывает все целые числа от 1 до $n$на доске. В каждом раунде, если на доске все еще есть числа, Алиса случайным образом выбирает число на доске и стирает это число и все его кратные. Каково ожидаемое количество раундов, пока на доске не останется чисел.
У меня было несколько закрытое решение:
Мы проводим классический аргумент двойного счета, мы вычисляем вероятность того, что любое целое число $k$выбран. Вероятность того, что$k$ выбран $\frac{1}{d(k)}$ где $d(k)$ это количество делителей $k$. Это правда, потому что с равной вероятностью$k$или выбирается любой из его делителей. По линейности математического ожидания мы можем взять сумму ожидаемых значений, которые выбраны для каждого отдельного целого числа. Это оценивается как$\sum_{k=1}^{n} \frac{1}{d(k)}$
Мне любопытно, есть ли способ еще больше сократить / ограничить эту окончательную сумму. Мы можем использовать HM-AM, чтобы ограничить его, поскольку сумма делителей из$1$ к $n$ хорошо известно, однако я запустил программу, и соотношение между HM и AM составляет ~$1.9$ для $n=100,000$.
Любая помощь приветствуется.
Спасибо !
Ответы
Этот ответ никоим образом не может быть истолкован как ответ. Он размещен как таковой, просто для удобства чтения.
Вероятность выбора k равна $\frac{1}{d(k)}$ где $d(k)$ - количество делителей k.
Если под « выбранным» вы имеете в виду «стерто» в первом раунде, тогда я не согласен. В первом раунде, чем больше делителей$k$имеет, тем больше вероятность того, что$k$ стирается.
На мой взгляд, спрашивая, есть ли конкретный номер $k$ будут удалены в конкретном раунде $r$, где $r > 1$это очень сложный вопрос. Конечно, для этого потребуется, чтобы число$k$ не стираться ни в одном из предыдущих раундов. И, конечно же, шанс$k$стирание в одном из предыдущих раундов будет как-то увеличиваться, поскольку$d(k)$увеличивается. Под « каким-то образом » я подразумеваю выражение вероятности в виде формулы, включающей$d(k)$ может быть непросто.
Далее, в предположении, что $k$ не был удален до раунда $r$, вычисляя вероятность того, что $k$ будет стираться по раунду $r$может быть кошмаром. На$r$-го раунда вы должны спросить, сколько еще чисел ожидается, которые не являются делителями$k$.
Фактический вопрос, который вы задаете:
сколько раундов потребуется, пока все числа не будут стерты.
Предположим, вы начинаете с набора вроде $\{1, 2, \cdots, 100\}$ и вы оцениваете каждое число $k$ по его стоимости $d(k)$. Чем тяжелее набор, тем большее количество чисел будет удалено за один раунд.
Однако, если вы утверждаете, что набор $\{1,2, \cdots, 100\}$ ожидается, что потребует $\left[\sum_{k=1}^{100} ~\frac{1}{d(k)}\right]~$ раундов, хотелось бы увидеть тому подтверждение.
Начало редактирования
Это просто пришло мне в голову. Возможно, то, что OP имел в виду
Вероятность выбора k равна $\frac{1}{d(k)}$ где $d(k)$ - количество делителей k.
это когда число$k$ стирается, вероятность того, что стирание произошло, потому что номер $k$ был выбран сам, а не один из его меньших делителей
$$\frac{1}{d(k)}.$$
Это, конечно, правда. Кроме того, возможно, у меня здесь слепое пятно. Однако мне сложно понять, как можно использовать этот факт для прямого вычисления ожидаемого количества раундов, которые потребуются для стирания всех чисел.
Мне также пришло в голову, что вопрос о том, сколько раундов потребуется, эквивалентен вопросу о том, какое ожидаемое количество раундов потребуется, прежде чем будет выбран номер 1 . Стирание завершается тогда и только тогда, когда выбрана цифра 1.
Проблема в том, что эта выборка не только без замены , но и в том, что выборка стирает переменное количество чисел в каждом раунде.
То есть, если число $k$ выбирается в раунде, затем
$$\left\lfloor \frac{n}{k} \right\rfloor$$
- максимальное количество чисел, которое можно стереть за раунд. Причина, по которой это максимальное значение, заключается в том, что некоторые из кратных$k$ могло быть уже стерто.
Даже с этим новым пониманием я все еще считаю эту проблему чрезвычайно сложной.
Конец редактирования
Предполагая, что вы согласны с тем, что не существует очевидной формулы для ожидаемого количества требуемых раундов, один из подходов к ответу на этот вопрос - начать с моделирования на компьютере. Позволять$n$ отличаться от $10$ через $100$. Для каждого значения$n$, предположим, что вы начинаете с набора $\{1,2,\cdots, n\}.$ Для каждого значения $n$, запустите моделирование 1000 раз. Это должно быть безопасно , так как одно моделирование не может занять больше, чем$n$раундов. Естественно, вам понадобится какой-то генератор случайных чисел, чтобы случайным образом выбрать одно число из группы чисел.
Попросите компьютер предоставить как среднее количество раундов для 1000 симуляций, так и какой-то вид отображения распределения количества раундов, необходимых для каждой симуляции.
Затем вы можете искать шаблоны и пытаться реконструировать формулы на основе этих шаблонов.
Очевидно, даже здесь вы все равно можете столкнуться с кошмаром.