Две задачи по терверу с неожиданными ответами

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3773
3	Radewoosh	3646
4	ecnerwala	3624
5	jqdai0815	3620
5	Benq	3620
7	orzdevinwang	3612
8	Geothermal	3569
8	cnnfls_csy	3569
10	Um_nik	3396

№	Пользователь	Вклад
1	Um_nik	163
2	cry	161
3	maomao90	160
4	-is-this-fft-	159
5	awoo	158
6	atcoder_official	157
7	adamant	155
8	nor	154
9	maroonrk	152
10	Dominater069	148

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

1. Представьте себе, что мы хотим сгенерировать случайный бит следующим странным способом. Возьмем очень-очень большое натуральное n и случайный двудольный граф, в каждой доле которого по n вершин. Посчитаем в нем количество совершенных паросочетаний (наборов из n ребер, которые не имеют общих концов). Четность этого количества и будет нашим битом. Какова вероятность, что этот бит будет равен нулю?

2. Представьте себе, что у нас есть n корзинок, в которые мы случайно бросаем шары. Мы продолжаем процесс, пока в каждой корзинке не будет по крайней мере m шаров. Сколько в среднем шаров мы бросим? Интересует ответ с точностью до константы. Например, хорошо известно, что если m = 1, то в среднем мы бросим $\text{[math]}$ шаров.

Комментарии (29)

Показать архивные | Написать комментарий?

MBabin

13 лет назад, # |

← Rev. 2 →

1. Четность числа паросоч. в случайном двудольном графе будет равна определителю случайной матрицы над $\text{[math]}$ поэтому ответ будет 0 с вероятностью того, что n случайных n-мерных векторов над $\text{[math]}$ линейно зависимы. ~~А эта вероятность < 2n· 1 / 2ⁿ. Так что при оч. большом n ответ почти 0.~~

→ Ответить

ilyaraz

13 лет назад, # ^ |

А откуда такая оценка взялась?

Вектора зависимы если все попали в (n - 1)-мерное подпр-во. Вероятность, что случайный вектор попадет в задданное (n - 1)-мерное подпр-во = 1 / 2. Всего 2n (n - 1)-мерных подпр-в.

Подпространств коразмерности один гораздо больше, их вроде бы 2ⁿ - 1.

Да ошибся(

Rei	13 лет назад, # ^ \| +10 Ну раз уж такое дело, ничто не мешает точную формулу написать: PS. А что случилось с командой \frac{}{} ? → Ответить

Ага, у этого выражения есть предел при n → ∞, который, вероятно, иррационален. По-моему, забавно, что ответ не 0, не 1 и не 0.5.

blazerer

а можно как-то выразить произведение элементов вида (2^i -1) от 1 до n ?

Urbanowicz

С ростом n это произведение будет иметь все больше и больше простых делителей. Не уверен, но по-моему это значит, что формулы с фиксированным числом множителей не существует.

mmaxio

В первой задаче вероятность получилась примерно 0,711211. А есть точная формула для ответа?

Есть точный предел при n → ∞.

Walrus

+10

Очень интересно было бы узнать решение задачи, получаемой из второй заменой "пока в каждой" на "пока хотя бы в одной". Например, для m=2 ответ пропорционален sqrt(n) (парадокс дней рождения).

А типа задачу из поста вы уже решили? :)

← Rev. 3 →

Мне кажется, что ответ на вашу задачу $\text{[math]}$ , если m фиксированное. Тут-то как раз нету ничего неожиданного.

Ну если в вашей задаче зафиксировать m, то ответ будет всегда одинаков, и он указан в условии. Нет разве? :)

Кстати, да. Надо подумать еще.

zeliboba

Первую задачу иногда дают в яндексе на собеседовании, в целом она довольно известная.
Во второй задаче (в исходном варианте) у меня получилось \Theta(n\cdot (\log n + m\log m))

Как нижняя оценка доказывается?

оценкой вероятности, что вероятность того, что событие еще не произошло <= 1/2

Я умею доказывать верхнюю оценку, которая меньше твоей нижней. Не знаю уж, у кого ошибка.

у меня довольно много вычислений, поэтому могу написать только план:

ответ (обозначим его k) больше n\log n, это из m = 1 легко извлечь
ответ больше nm\log m, т.к. вероятность того, что в первой ячейке меньше m должна быть меньше 1/2, т.е. C_{k}^{m-1}(n-1)^{k-m+1}/n^k <1/2
в конечном итоге получим exp(k/n) > С(m)\cdot (k/n)^{m} ч.т.д

Откуда это взялось?
> вероятность того, что в первой ячейке меньше m должна быть меньше 1/2

если она >1/2, то с вероятностью хотя бы 1/2 все закончится позже, т.е. матожидание не меньше k/2

я нашел у себя ошибку, теперь у меня n(m+ \log n)

Ну да, теперь нижняя оценка очевидна. А как верхняя доказывается?

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

Да, наверное можно и так. Есть решение в одну строчку, которое использует неравенство Чернова.

с помощью Чернова понятно только как верхнюю оценку доказывать

А нижняя и так очевидна: ясно, что ответ не меньше $\text{[math]}$ и не меньше Ω(nm).

Блог пользователя ilyaraz