Корабль можно поставить всего двумя способами, не четырьмя? Или они сокращаются из-за симметрии?
Я написал "левая верхняя клетка корабля". Корабль от неё можно поставить либо направо, либо вниз.
Тестировал несколько раз по
![$10^9$ $10^9$](https://dxdy-01.korotkov.co.uk/f/0/6/5/065159456ed4c790e33155c119a0726f82.png)
расположения (по правилам игры, без касаний), ни разу не попалось два совпадающих.
Пусть у нас есть
![$N$ $N$](https://dxdy-04.korotkov.co.uk/f/f/9/c/f9c4988898e7f532b9f826a75014ed3c82.png)
элементов, которые мы выбираем
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
раз (с возвращением и независимо) с одинаковой вероятностью
![$\frac 1N$ $\frac 1N$](https://dxdy-03.korotkov.co.uk/f/6/3/4/634d958c093152077c4ab52defce996e82.png)
каждый. Вероятность того, что в полученной выборке объёма
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
найдутся совпадающие элементы, равна
![$$P_N(n)=1-\prod_{k=0}^{n-1}\left(1-\frac kN\right).$$ $$P_N(n)=1-\prod_{k=0}^{n-1}\left(1-\frac kN\right).$$](https://dxdy-02.korotkov.co.uk/f/d/b/c/dbc4b8f78a9deded1c0bde4dc074dada82.png)
У нас
![$n=10^9$ $n=10^9$](https://dxdy-01.korotkov.co.uk/f/0/0/5/005fdc113a506bd0af6e257d652a73a882.png)
, и пусть
![$N=10^{19}$ $N=10^{19}$](https://dxdy-01.korotkov.co.uk/f/4/9/e/49e461821758bad3b45beab8be37295a82.png)
. Вычислять вероятность совпадений по этой формуле, конечно, весьма накладно, но можно получить приближённую.
Раскрывая скобки, получим
![$$P_N(n)=\sum_{k=0}^{n-1}\frac kN-\sum_{0\leqslant k_1<k_2\leqslant n-1}\frac{k_1k_2}{N^2}+\sum_{0\leqslant k_1<k_2<k_3\leqslant n-1}\frac{k_1k_2k_3}{N^3}-\ldots=$$ $$P_N(n)=\sum_{k=0}^{n-1}\frac kN-\sum_{0\leqslant k_1<k_2\leqslant n-1}\frac{k_1k_2}{N^2}+\sum_{0\leqslant k_1<k_2<k_3\leqslant n-1}\frac{k_1k_2k_3}{N^3}-\ldots=$$](https://dxdy-01.korotkov.co.uk/f/4/b/7/4b7c2aa921cd6465ad56947057152f9682.png)
(число слагаемых конечное; 26/III в 21:52 удалил ненужные факториалы, которые тут оказались по недоразумению; далее их и не было)
![$$=\frac{n(n-1)}{1!\cdot 2N}-\frac{n(n-1)(n-\frac 13)(n-2)}{2!\cdot(2N)^2}+\frac{n^2(n-1)^2(n-2)(n-3)}{3!\cdot(2N)^3}-\ldots\approx$$ $$=\frac{n(n-1)}{1!\cdot 2N}-\frac{n(n-1)(n-\frac 13)(n-2)}{2!\cdot(2N)^2}+\frac{n^2(n-1)^2(n-2)(n-3)}{3!\cdot(2N)^3}-\ldots\approx$$](https://dxdy-04.korotkov.co.uk/f/7/d/c/7dc41dd918e677863806c42f25b3329c82.png)
(знаменатели дробей устроены вполне закономерно, а числители мы заменим соответствующими степенями произведения
![$n(n-1)$ $n(n-1)$](https://dxdy-04.korotkov.co.uk/f/b/c/5/bc5bf52fdceac27ab818c62af75b408e82.png)
, а также продолжим сумму "до бесконечности")
![$$\approx\frac 1{1!}\left(\frac{n(n-1)}{2N}\right)-\frac 1{2!}\left(\frac{n(n-1)}{2N}\right)^2+\frac 1{3!}\left(\frac{n(n-1)}{2N}\right)^3-\ldots=1-e^{-\frac{n(n-1)}{2N}}.$$ $$\approx\frac 1{1!}\left(\frac{n(n-1)}{2N}\right)-\frac 1{2!}\left(\frac{n(n-1)}{2N}\right)^2+\frac 1{3!}\left(\frac{n(n-1)}{2N}\right)^3-\ldots=1-e^{-\frac{n(n-1)}{2N}}.$$](https://dxdy-04.korotkov.co.uk/f/b/7/3/b7392e1bdb516a9dc17ac2432fcbee9982.png)
Оценкой погрешности не заморачиваюсь, так как наверняка эта формула (или похожая с
![$n^2$ $n^2$](https://dxdy-01.korotkov.co.uk/f/0/2/1/021273d50c6ff03efebda428e9e42d7782.png)
вместо
![$n(n-1)$ $n(n-1)$](https://dxdy-04.korotkov.co.uk/f/b/c/5/bc5bf52fdceac27ab818c62af75b408e82.png)
) уже лет сто как опубликована и с оценкой погрешности. Просто покажу величину погрешности на графиках.
Слева — это графики
![$P_N(n)$ $P_N(n)$](https://dxdy-01.korotkov.co.uk/f/0/b/b/0bbba54ad7a459faefe74d07fe416bb182.png)
и
![$1-e^{-\frac{n(n-1)}{2N}}$ $1-e^{-\frac{n(n-1)}{2N}}$](https://dxdy-03.korotkov.co.uk/f/a/3/4/a34d17c54c0a8f5c03be3b2012667e8782.png)
для
![$N=365$ $N=365$](https://dxdy-03.korotkov.co.uk/f/e/b/a/eba3622bef363c408e2b02b52530e46882.png)
(классическая задача о днях рождения) и для
![$N=100\,000$ $N=100\,000$](https://dxdy-03.korotkov.co.uk/f/2/4/a/24a95af98f4107bea707f09bd1560fe882.png)
, а справа — графики разности
![$P_N(n)-\left(1-e^{-\frac{n(n-1)}{2N}}\right)$ $P_N(n)-\left(1-e^{-\frac{n(n-1)}{2N}}\right)$](https://dxdy-04.korotkov.co.uk/f/f/1/f/f1ff2d195f6679b309868b7315c0c1c082.png)
.
Вложение:
Sovpadenia-365pd.gif [ 5.72 Кб | Просмотров: 1331 ]
Вложение:
Sovpadenia-100000pd.gif [ 6.41 Кб | Просмотров: 1331 ]
Хорошо видно, что при больших
![$N$ $N$](https://dxdy-04.korotkov.co.uk/f/f/9/c/f9c4988898e7f532b9f826a75014ed3c82.png)
погрешность маленькая.
Для
![$N=10^{19}$ $N=10^{19}$](https://dxdy-01.korotkov.co.uk/f/4/9/e/49e461821758bad3b45beab8be37295a82.png)
и
![$n=10^9$ $n=10^9$](https://dxdy-01.korotkov.co.uk/f/0/0/5/005fdc113a506bd0af6e257d652a73a882.png)
формула даёт
![$P\approx 0{,}04877$ $P\approx 0{,}04877$](https://dxdy-02.korotkov.co.uk/f/d/2/7/d27de9583b337b126d28145a588cde7582.png)
.
Обратная величина вероятности
![$\frac 1P\approx 20{,}5$ $\frac 1P\approx 20{,}5$](https://dxdy-02.korotkov.co.uk/f/1/6/b/16bcacc1f86c9af1c16b5c364a1cc9b282.png)
, поэтому для получения первого совпадения в среднем требуется
![$20{,}5$ $20{,}5$](https://dxdy-04.korotkov.co.uk/f/3/f/8/3f8bf356723abbabb76d9d7952bd59d982.png)
независимых выборок объёмом
![$10^9$ $10^9$](https://dxdy-01.korotkov.co.uk/f/0/6/5/065159456ed4c790e33155c119a0726f82.png)
. На этом пути можно и оценить объём генеральной совокупности, но для этого требуется сколько-то сотен таких выборок (для
![$n=10^7$ $n=10^7$](https://dxdy-01.korotkov.co.uk/f/0/0/6/006a4d121029e6e4f1d3ca630a3dd2f682.png)
получается
![$P\approx 5\cdot 10^{-6}$ $P\approx 5\cdot 10^{-6}$](https://dxdy-04.korotkov.co.uk/f/7/b/b/7bbbe67da250ed51ecc0ad4837e0a37082.png)
, поэтому таких выборок требуются миллионы).