Две задачи из Севастьянова (вероятность)

[rwanda]

Неприлично долго уже сижу именно над этими двумя задачами из сборника. Помогите решить, пожалуйста.


1) По схеме случайного выбора с возвращением из множества целых чисел {1, 2, ..., N} выбираются числа $a $ и $b$. Найти вероятность, что $ a$ и $b$ взаимно просты.

Что делал: Пытался подобраться к задаче путем выявления закономерностей в чередовании делителей у чисел {1, 2, ..., N}, считать/учитывать обычные простые числа (тоже искать закономерности, чтобы написать потом формулу для "успехов"). Но пока безрезультатно, кажется, я вообще не в ту сторону думаю.



2) По схеме случайного выбора с возвращением из множества целых чисел {$1, 2, ..., 10^n-1$} выбираются числа $ a $ и $b$. Обозначим $P_m$ вероятность того, что сумма $a+b$ будет $m$-значным натуральным числом в десятичной записи. Найти вероятности $P_{n-k+1} $ для $k=0,1,2,...,n$.

Что делал: просто покажу, как решил похожую задачу из того же Севастьянова. С ответами не сошлось, но проверку мой вариант проходит. Гордо в чистовик выписал свое решение, так как самостоятельно выстраданная формула все же милее :) Также прошу взглянуть на этот мой ответ, подсказать, насколько он адекватен (к вышеуказанной задаче с такой логикой уже не получилось подступиться).



Целое число $a$ случайно выбирается из множества {$1, 2, ...,10^{n}-1$}. Найти вероятность того, что в десятичной записи это число $k$-значно, т.е. представимо в виде: $a=a_k\cdot10^{k-1}+a_{k-1}\cdot10^{k-2}+ ... + a_2\cdot10 + a_1$, где $0\leqslanta_i\leqslant9$ при всех$ i=1,...,k и a_k>0 (k\geqslant1)$.

Мой ответ: $P=\frac{(10^k-1)-(9_{k-1}\cdot10^{k-2}+9_{k-2}\cdot10^{k-3}+ ... +9_1)}{10^n-1}$.

[provincialka]

Ответ можно сразу в раздел юмора переносить. $9_{k-1}$ -- это круто!

[gris]

Попробуйте нарисовать это дело в квадратной матрице $N\times N$. Каждый элемент матрицы это упорядоченная пара $(a,b)$. Отметьте элементы, в которых сумма чисел пары равна некоторому числу (для второй задачи), или числа пары взаимно просты (для первой). Обратите внимание, что при увеличении размеров матрицы её "старая" часть не изменяется.
Ну а к Вашему ответу на более простую задачу: Вы, наверное, хотели рассмотреть равенство $9999=9\cdot1000+9\cdot100+9\cdot10+9=9\cdot10^3+9\cdot10^2+9\cdot10^1+9\cdot10^0$.
Оно верное. Хотя можно, например, и так: $9999=10^4-1$. В ответах часто бывают тождественные выражения. Это не ошибка.

[rwanda]

gris в сообщении #1232932 писал(а):

Попробуйте нарисовать это дело в квадратной матрице $N\times N$. Каждый элемент матрицы это упорядоченная пара $(a,b)$. Отметьте элементы, в которых сумма чисел пары равна некоторому числу (для второй задачи), или числа пары взаимно просты (для первой).

gris, спасибо за идею! Попытка решить через геометрию. Наглядно на картинке:



Область всех возможных пар - большой треугольник. Успехи отмечены. Считается ("вырезается") площадь получившейся фигуры и делится на плошадь большого треугольника.

Ответ вышел: $P_n=\frac{1}{2}-\frac{10^{2n-2}}{2\cdot(10^n-1)^2}$

[gris]

А где же тут $k$?
Кстати, по первой задаче: вот упрощение: найти вероятность, что у двух чисел, не больших $N$, не будет некоторого общего делителя. Например, двойки или тройки.

[rwanda]

gris
$k$ равен единице.

[gris]

То есть это вероятность того, что, например, при $n=2$ сумма двух чисел, меньших ста, будет двузначна. В формуле есть даже части, отвечающие вероятностям того, что сумма однозначна или трёхзначна. Ну да. Прикинем. Из $9801$ пар сумма однозначна у $36$, двузначна у $815$ и трёхзначна у $4950$. Сходится? Нет ли шероховатостей, связанных с тем, куда относить диагонали? Впрочем, это мелочь. Ну вот, Вы теперь при желании можете располосовать этот треугольник для самых разных $k$.
Конечно, правильнее полосовать квадрат, но в силу симметрии пойдёт.

[12d3]

rwanda
В первой задаче красивого ответа не будет, зато есть красивая асимптотика.
Обозначим через $f(n)$ количество упорядоченных взаимно простых пар натуральных чисел, не превосходящих $n$. Чему равно $f(n+1)-f(n)$ ?

[apuzikov]

всем привет,


тоже решаю задачу 1.14 из Севостьянова, которую автор поста обозначил как 1я
с подсказки @12d3 прихожу к выводу, что при выборе второго числа нужно, чтобы в его разложении на простые множители, обозначим его P_{2}, не было простых чисел из разложения на простые множители первого, обозначим его P_{1}=$\left\lbrace p_{1},p_{2},...\right\rbrace$. Количество таких чисел в $\left\lbrace 1,2,3,...N \right\rbrace$ можно посчитать для

1. к примеру p_{1} = 2
C = N-$\left\lfloor\frac{N}{2}\right\rfloor$ где квадтратные скобки $\left\lfloor\right\rfloor$это ближайшее целое
2. или p_{1} = 3
C=N-$\left\lfloor\frac{N}{3}\right\rfloor$
3. или p_{1} = 2,p_{2} = 3
C=N-$\left\lfloor\frac{N}{2}\right\rfloor$-$\left\lfloor\frac{N}{3}\right\rfloor$+$\left\lfloor\frac{N}{2\cdot3}\right\rfloor$
и так далее... для всех простых, встретившихся в первом числе. В пределе там может появиться (-1)^{k} где k-количество простых чисел в разложенииP_{1} .

В итоге мощность множ-во всех событий $|Omega| = N^{2}$ . Так как выбираем с возвращением. А вероятность q_{N} = $\frac{C}{N^2}$ только для настощего С

Получается, что для красивой аналитической записи мне нужно знать точное количество простых множителей из k = |P_{1}| , а это уже явно не тривиально, и не записывается формулой, я куда-то не туда думаю? В ответе это k судя по всему присутствует, но откуда оно берётся?

[Евгений Машеров]

Чтобы два числа были взаимно просты, нужно, чтобы для всякого простого числа либо первое на него делилось, а второе нет, либо второе делилось, а первое нет, либо оба не делились. Для достаточно большого N доля чисел, которые делятся на простое $p_i$, стремится к $\frac 1 {p_i}$. Далее считаем вероятность того, что выполняется условие взаимной простоты по $p_i$, и перемножаем вероятности для всех $p_i$. Получается бесконечное произведение, задающее вероятность при стремлении N к бесконечности. А дальше узнать про Эйлера и сумму обратных квадратов.

[nnosipov]

Евгений Машеров
Это все очень нестрогие рассуждения, их аккуратная формализация себе дороже выйдет. Проще сразу написать сумму $\sum_{n=1}^N\varphi(n)$ и получить ее асимптотику при $N \to \infty$. (Здесь $\varphi(n)$ --- функция Эйлера.)

[Евгений Машеров]

nnosipov
Это верное соображение, но предполагающее определённый уровень знаний, в частности, курс теории чисел прослушан и асимптотические рассуждения не вызывают затруднений.
Об уровне топикстартера я не знаю ничего, кроме того, что он не мог решить не только данную, но и вторую задачу, и уровень задачника Севастьянова мне тоже не знаком. Но сама формулировка первой задачи выглядит не чрезмерно строгой (хотя, может, требовалось дать не предел вероятности при росте N до бесконечности, а громоздкую формулу в виде произведения с использованием целой части от деления N на $p_i$)

[nnosipov]

rwanda в сообщении #1232890 писал(а):

1) По схеме случайного выбора с возвращением из множества целых чисел {1, 2, ..., N} выбираются числа $a $ и $b$. Найти вероятность, что $ a$ и $b$ взаимно просты.

Если задача стоит именно так, то мы просто сразу пишем ответ в виде

$$P_N=\frac{Q(N)}{N^2}, \quad Q(N)=2\sum_{n=1}^N\varphi(n)-1.$$

Здесь $Q(N)$ --- это число пар $(a,b) \in \{1,2,\dots,N\}^2$, для которых $\gcd{(a,b)}=1$. Тут даже непонятно, над чем думать (функция Эйлера прямо по определению считает количество взаимно простых чисел). Ну а дальше можно изучать поведение $P_N$ при $N \to \infty$, если хочется. И там действительно придется попользоваться чем-то вроде

$$\varphi(n)=n\sum_{d \mid n}\frac{\mu(d)}{d}=n\left(1-\frac{1}{p_1}\right)\ldots\left(1-\frac{1}{p_k}\right),$$

где $p_1,\dots,p_k$ --- все простые делители $n$.

[мат-ламер]

Евгений Машеров в сообщении #1649271 писал(а):

А дальше узнать про Эйлера и сумму обратных квадратов.

Так какие сложности возникают на этом пути? Интуитивно понятно, что ответ равен $\Pi (1-p_n^2)=[\zeta(2)]^{-1}=6/\pi ^2$ (где $p_n$ - $n$-е простое число). Думаю, что обоснованию подлежит сходимость бесконечного произведения. Ведь каждый её член тоже является пределом. Задачник, наверное, рассчитан на широкий круг читателей. И по идее знание основ теории чисел не требуется.

-- Вс авг 11, 2024 11:24:04 --

мат-ламер в сообщении #1649367 писал(а):

Задачник, наверное, рассчитан на широкий круг читателей.

В предисловии к задачнику написано, что большинство задач доступно студентам технических ВУЗов. Лишь некоторые задачи (они перечислены в предисловии и помечены звёздочкой) рассчитаны на студентов университетов. Задача 1.14 к ним не относится.

[nnosipov]

мат-ламер в сообщении #1649367 писал(а):

Задача 1.14 к ним не относится.

Ну да, конечно. Это задача, для решения которой требуется приличная математическая культура. Недаром к задаче есть только указание, и если ему следовать, то придется изрядно попотеть, формулы там довольно громоздкие. Возможно, в те времена такие задачи можно было предлагать студентам технических вузов, но сейчас я бы не рискнул. Тут задачу про крокодила решить не могут, какие там суммы произведений по простым числам.

-- Вс авг 11, 2024 15:58:01 --

Евгений Машеров в сообщении #1649353 писал(а):

уровень задачника Севастьянова мне тоже не знаком

Когда я был студентом, это был один из задачников в нашем курсе ТВ. То есть, уровень университетский.