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

[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)$ ?