Вероятность остатков.

[dreamkiller]

Вот какие у меня значения получились для некоторых чисел( запрограммировал).
2000 0,55776475
4000 0,557351125
6000 0,557200888888889
8000 0,557121859375
10000 0,55707488
12000 0,557041548611111
14000 0,557017433673469
16000 0,55699865234375
18000 0,556984734567901
20000 0,55697231
22000 0,556962710743802
24000 0,556954185763889
26000 0,556947659763314
28000 0,556941461734694
30000 0,556936157777778
32000 0,556931244140625
34000 0,556927155709343
36000 0,556923611111111
38000 0,556920047783934
40000 0,556916910625

Что-то слишком медленно оно стремится к 1/2.

[Sonic86]

Странно... Значит не $1/2$
...
Хорошо, вот точная формула числа благоприятных исходов:

$$n+\left[\frac{n}{2}\right]+\sum\limits_{k=3}^n\left(\left[\frac{n+k-1}{k}\right]+...+\left[\frac{n+k-[(k-1)/2]}{k}\right]+\left[\frac{n}{k}\right]\right)$$

[Sonic86]

Ну вот, теперь у меня получается $\frac{1}{4}+\frac{\pi^2}{36}\approx 0,52416$ (я преобразовал сумму, часть оценил точно, а часть снова так же - геометрически). Новое значение ближе к истине, но все равно до нее не дотягивает.

dreamkiller, откуда задача? Она стандартная или нет? А то у меня уже появилось сильное ощущение, что я делаю слишком сложно и неправильно.
Если есть какие-то идеи - скажите, а то я не знаю, как ее можно считать

[atlakatl]

Есть два равновероятных случая:
1. a>b. r в этом случае равновероятно принимает значения от 1 до b. Тогда вероятность, что r<b/2 равна ½.
2. a<b Тогда a=r и принимает также все значения от 1 до b равновероятно. Опять же вероятность, что r<b/2 равна ½.
Итого общая вероятность равна ½.

[gris]

atlakatl, это неверные рассуждения. В неограниченном случае нет смысла говорить о равновероятности. При ограничении квадратом вероятности в нечётных строках не будут равны 0.5.

По житейской интуиции кажется, что остатков меньше половины и должно быть чуть больше половины, так как для чётного делителя, например, 4 их поровну: 0 1 и 2 3. Для нечётного делителя, например, 5, имеем 0 1 2 и 3 4, то есть меньших остатков больше. При больших значениях делителя всё должно вроде бы сглаживаться, но вот не сглаживается.

[Sonic86]

Ха! Я решил!
Пусть $N_n$ - число пар $a,b\leqslant n$, удовлетворяющих условию $a\bmod b<\frac{b}{2}$. Составляем рекуррентное уравнение, явно вычисляя $N_n-N_{n-1}$. Оцениваем суммы простейшим образом, а потом решаем рекуррентное уравнение.
Получаем $\frac{5}{4}-\ln 2\approx 0,55685$.
Скорость сходимости $O\left(\frac{1}{\sqrt{n}}\right)$.
dreamkiller, я думаю, что Вы сами сможете, потому подробно не расписываю Хотя, если затруднитесь...

(Оффтоп)

суммы по столбцам дают нечто теоретико-числовое, а суммы по строкам - обычный матанализ

(atlakatl)

atlakatl в сообщении #622262 писал(а):

Есть два равновероятных случая:
1. a>b. r в этом случае равновероятно принимает значения от 1 до b. Тогда вероятность, что r<b/2 равна ½.
2. a<b Тогда a=r и принимает также все значения от 1 до b равновероятно. Опять же вероятность, что r<b/2 равна ½.
Итого общая вероятность равна ½.

А вот и неправильно, бе-бе-бе

[atlakatl]

Sonic86 в сообщении #622312 писал(а):

А вот и неправильно, бе-бе-бе

Абсолютно согласен. У меня ума хватило только на численный эксперимент. Результат совпадает с вашим.

[Sonic86]

(Оффтоп)

atlakatl в сообщении #622316 писал(а):

Абсолютно согласен. У меня ума хватило только на численный эксперимент. Результат совпадает с вашим.

Не обижайтесь, меня просто эмоции переполняют

[Sonic86]

Мне еще интересно, почему не сработало геометрическое доказательство? Доля закрашенной площади $\frac{1}{2}$. Но это же неверно. Почему? Я думал, при замене дискретной картинки ее непрерывным аналогом погрешность будет $o(1)$. Да и оценили погрешность как $O(\frac{\ln n}{n})$. А тут почему-то не так

[gris]

Раскрашивать же не площадь надо, а отдельные квадратики. Я пробовал. Там не получается 1/2. А у Вас красивый результат получился.

[ИСН]

Есть такие неинтуитивные штуки, да. Из той же оперы, кажется - асимптотика $\sum\limits_{i=1}^n(n\mod i)$

[Sonic86]

ИСН в сообщении #622503 писал(а):

Есть такие неинтуитивные штуки, да. Из той же оперы, кажется - асимптотика $\sum\limits_{i=1}^n(n\mod i)$

и соотношение, из которого оно следует, тоже не особо интуитивно понятно:

$$\sum\limits_{k=1}^n n\bmod k+\sum\limits_{k=1}^n \sigma(k) = n^2$$

$\sigma$ - сумма делителей числа.

[gris]

ТС на самом деле убил мой сон. Снится мне, как я в лесу с белочкой собираю грибы. Короче, в самый прекрасный момент приходит dreamkiller и говорит: "Результат не намного больше половинки!" Я пытаюсь предположить, что преподаватель сказал "немного", но... Бензопила, кровь.

Если внимательно посмотреть на раскраску раздуваемого квадрата, и сравнить количество благоприятствующих точек в разных его частях, то мы увидим их преобладание в области квадрата с маленькими числами и наоборот в области с большими числами. Если в координатной плоскости, то соответственно в левой нижней и правой верхней четвертушке квадрата.
То есть, если мы будем раздувать круг из начала координат или треугольник, то получим большее значение предельной вероятности. Больше 0.6.
А почему мы раздуваем квадрат с его торчащим углом? Логичнее раздувать четвертушку круга.
Можно даже сделать такую фигуру раздувания, что она будет постепенно покрывать всю плоскость, но наша вероятность будет стремиться к единице. И препод возрадуется.

[dreamkiller]

Sonic86 в сообщении #622312 писал(а):

Ха! Я решил!
Пусть $N_n$ - число пар $a,b\leqslant n$, удовлетворяющих условию $a\bmod b<\frac{b}{2}$. Составляем рекуррентное уравнение, явно вычисляя $N_n-N_{n-1}$. Оцениваем суммы простейшим образом, а потом решаем рекуррентное уравнение.
Получаем $\frac{5}{4}-\ln 2\approx 0,55685$.
Скорость сходимости $O\left(\frac{1}{\sqrt{n}}\right)$.
dreamkiller, я думаю, что Вы сами сможете, потому подробно не расписываю Хотя, если затруднитесь...

(Оффтоп)

суммы по столбцам дают нечто теоретико-числовое, а суммы по строкам - обычный матанализ

Что-то я не совсем понимаю, как можно задать разность, точнее оценить количество b, что $n\bmod b < r/2$

[Sonic86]

dreamkiller в сообщении #622982 писал(а):

$n\bmod b < r/2$

только не $r/2$, а $b/2$

dreamkiller в сообщении #622982 писал(а):

Что-то я не совсем понимаю, как можно задать разность

Напишите, пожалуйста, попытки решения явно, я Вам подскажу. Задача очень хорошая А кратко я Вам написал уже: сначала выпишите формулу для $N_n-N_{n-1}$ явно, а потом делайте тривиальные оценки.
Или колитесь, откуда задача тогда кусок решения выпишу.

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

Раскрашивать же не площадь надо, а отдельные квадратики. Я пробовал. Там не получается 1/2

Я пока понял так: если число фигур конечно и клеточная сетка просто "масштабируется" по рисунку, то пределы должны совпадать. А у нас $n$ фигур с длиной границы $O(n)$, отсюда лезет ошибка.