Задача о лестницах

[bayak]

Условие:

Представьте себе человечка, способного шагать вверх по ступенькам приставной лестницы. Пусть нашему человечку по его требованию подставляют и оставляют стоять на месте бесконечно длинные лестницы, шаг которых (т. е., расстояние между соседними ступеньками) кратен его шагу. С земли человечек запрыгивает на первую ступеньку лестницы, с шагом равным двум его шагам, однако далее при подъеме он каждый раз делает только по одному шагу, и при этом ставит ногу либо на первую ступеньку новой (т. е., затребованной им) лестницы, либо на уже не первую ступеньку старой (т. е., поставленной ранее) лестницы. Спрашивается, сколько потребуется человечку лестниц, чтобы подняться на высоту $N$ его шагов, если $N$ достаточно велико.

Решение:

Прежде всего заметим, что шаг, затребованных человечком лестниц, всегда равен простому числу. Действительно, измеряемая числом шагов высота ступеньки установленной лестницы, на которую человечек может поставить ногу, кратна шагу одной из уже поставленных лестниц, а следовательно высота ступеньки, на которую он не может поставить ногу из-за отсутствия лестницы, не кратна шагу ни одной из поставленных лестниц, и поэтому не делится на высоту ни одной из нижележащих ступенек.

Пусть человечек стоит на высоте $N$. Тогда вероятность того, что он не поставит ногу на уже установленную лестницу с простым шагом $p$, где $p<\sqrt{N+1}$, равна $1-1/p$, а вероятность того, что он не поставит ногу ни на одну из уже установленных лестниц, равна

$$\prod_{p<\sqrt{N+1}}(1-1/p).$$

Cледовательно, вероятность того, что число $N+1$ простое, равна этой же величине:

$$P(N+1)=\prod_{p<\sqrt{N+1}}(1-1/p).$$

Воспользуемся теперь разложением

$$ \left(1-\frac{1}{p}\right)^{-1}= 1+\frac{1}{p}+ \frac{1}{p^{2}}+ \ldots,$$

чтобы преобразовать произведение в величину обратную сумме:

$$ \prod_{p<\sqrt{N+1}}(1-1/p)= \frac{1}{\sum_{n\leq N}\frac{1}{n}+ \sum_{m>N}\frac{1}{m}},$$

где $n$ и $m$ составлены из произведений простых чисел меньших $\sqrt{N+1}$, в силу чего $n$ пробегает от единицы до $N$ все числа натурального ряда за исключением простых чисел больших $\sqrt{N}$, а $m$ пробегает от $N+1$ до бесконечности только малую часть натурального ряда. Поскольку выполняется неравенство:

$$ \sum_{m>N}\frac{1}{m}<\sum_{2}^{\infty}\frac{N}{(\sqrt{N})^{k}},$$

то сумма $\sum_{m>N}\frac{1}{m}$ ограничена и при достаточно большом $N$ ей можно пренебречь. Таким образом, при достаточно большом $N$, мы имеем приблизительное равенство:

$$ P(N+1)\approx \frac{1}{\ln N}.$$

В том случае, когда человечек стоит на высоте $N$ и делает оттуда $\Delta N$ шагов, вероятность того, что на этом отрезке пути нет ступеньки с простым числом ее высоты, или иначе говоря, что он не наступит ни на одну из поставленных ранее лестниц, равна:

$$ P(N,N+\Delta N)\approx \frac{\Delta N}{\ln N}.$$

А суммарная вероятность того, что на пути со ступеньки высоты 2 на ступеньку высоты $N$ ему будут встречаться ступеньки с простыми числами их высот, равна:

$$ P(2,N)\approx\int_{2}^{N}\frac{dt}{\ln t}.$$

Нам осталось только заметить, что суммарная вероятность $P(2,N)$ случайных событий, заключающихся в попадании на отрезке пути $[2,N]$ на простые числа, округлено равна накопленной достоверности этих событий, т. е., количеству простых чисел $\pi(N)$, попадающих в отрезок $[2,N]$, и поэтому окончательно мы имеем формулу:

$$ \pi(N)=\left[\int_{2}^{N}\frac{dt}{\ln t}\right].$$