Question

Алексей Вильнюсов наугад выбирает два натуральных числа p и q. Найдите вероятность, что дробь p/q окажется несократимой.

Answer 1

Ответ:

$\frac{6}{\pi^2}$

Пошаговое объяснение:

Ясно, что дробь является сократимой, если у p и q есть общий простой делитель. Вероятность того, что произвольное число делится на простое  число $a$ есть очевидно $\frac{1}{a}$, а что не делится $(1 - \frac{1}{a})$. Также ясно, что делимость на разные простые числа - события независимые. Из вышесказанного следует, что вероятность того, что дробь не сокращается на простое число

$P=(1-\frac{1}{2^2})(1-\frac{1}{3^2})(1-\frac{1}{5^2})\dots$

Вспомним формулу суммы геометрической прогрессии:

$1+q+q^2+\dots=\frac{1}{1-q}=(1-q)^{-1}$

Отсюда

$1-q=(1+q+q^2+\dots)^{-1}$

Сделаем такое с каждой скобкой в нашем выражении для $P$:

$P=(1+\frac{1}{2^2}+\frac{1}{2^4}+\dots)^{-1}(1+\frac{1}{3^2}+\frac{1}{3^4}+\dots)^{-1}(1+\frac{1}{5^2}+\frac{1}{5^4}+\dots)^{-1}\dots$

Тогда

$P^{-1}=(1+\frac{1}{2^2}+\frac{1}{2^4}+\dots)(1+\frac{1}{3^2}+\frac{1}{3^4}+\dots)(1+\frac{1}{5^2}+\frac{1}{5^4}+\dots)\dots$

Легко увидеть, что это равно

$P^{-1}=1+\frac{1}{2^2}+\frac{1}{3^2}+\frac{1}{4^2}+\dots$

т. е. сумме ряда обратных квадратов. Его значение можно легко получить например разложив $f(x)=x^2$ в ряд Фурье и посмотрев значение в точке $x=\pi$. Итак, сумма этого ряда есть

$P^{-1}=\frac{\pi^2}{6}$

Откуда получаем ответ.

Answer 2

Чтобы найти вероятность того, что дробь p/q окажется несократимой, нужно выяснить, какие пары натуральных чисел p и q являются сократимыми и сколько всего существует пар натуральных чисел.

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

Существует бесконечно много пар натуральных чисел p и q. Однако, если мы рассмотрим фиксированное число n, то количество пар натуральных чисел (p, q), где p и q находятся в диапазоне от 1 до n, будет равно n^2.

Теперь давайте рассмотрим, сколько из этих пар чисел являются сократимыми. Если p и q являются сократимыми числами, то у них будет общий делитель, отличный от единицы. Для каждой пары чисел (p, q) существует конечное количество общих делителей, и если мы переберем все возможные значения p и q, мы сможем подсчитать количество сократимых пар.

Таким образом, вероятность того, что случайно выбранная пара натуральных чисел (p, q) будет сократимой, будет равна отношению количества сократимых пар к общему количеству пар:

Вероятность = (количество сократимых пар) / (общее количество пар)

Итак, чтобы рассчитать эту вероятность, нам нужно подсчитать количество сократимых пар и общее количество пар чисел.

Подсчет всех сократимых пар может быть сложной задачей, поскольку требует проверки всех возможных значений p и q. Однако, мы можем применить математическое свойство, что вероятность взаимной простоты двух случайно выбранных чисел p и q при их увеличении до бесконечности стремится к 6/π^2.

Таким образом, в пределе, вероятность несократимой дроби равна 1 - 6/π^2 или приближенно 0.36 (или 36%).