Разбъркване на карти

[Zarrie]

Колко е очакваният брой разбърквания на стандартно тесте карти (с 52 карти), които трябва да направите, преди да постигнете подреждане, което никога до сега не се е срещало преди в историята на човечеството?

Допускаме, че при разбъркване на картите се получава с еднаква вероятност всяка възможна тяхна подредба.

[inveidar]

Трябва да кажеш едно разбъркване за колко време се прави и кога е измислено стандартното тесте от 52 карти?

[Zarrie]

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

[inveidar]

Както казваха старите баби на село, когато аз бях младеж - МНОГО!
Нещо от порядъка на [tex]10^{50}[/tex]?

[Zarrie]

Абсолютно вярно
Или шансът първото разбъркване, което направим да е уникално е 100%

[optimeon]

Напълно съм съгласна!

[Гост]

Хитра и забавна задачка. Може да подхлъзне някого.
Накратко, отговорът е + БЕЗКРАЙНОСТ. !!!
Единственото предположение, което трябва да направи решаващият задачата, за да я реши, е дали досега в историята на човечеството е използвано поне едно разбъркване на тесте от 52 карти.
Ако нито едно подреждане не се е срещало досега в историята на човечеството, отговорът е едно. Защото първото подреждане, което направи експериментаторът, ще бъде и първото използвано в историята. С вероятност 100%. Ако са ползвани всички възможни подреждания (надали!), то отговорът е безкрайност. Защото никога няма да се получи неизползвано подреждане. Ако обаче в историята не са ползвани всички възможни подреждания, но е ползвано някога поне едно подреждане, то отговорът също е безкрайност. Точно това е и тънкият момент в цялата задача. Отговорът не зависи от броя на използваните до момента подреждания, само от това дали някога е ползвано поне едно подреждане.

Ако разгледаме въпроса каква е вероятността като направим едно произволно подреждане, то да се окаже неизползвано никога досега, отговорът зависи от броя на използваните до момента подреждания. Но очакването на броя подреждания, които трябва да се направят, докато стигнем до неизползвано преди подреждане, не зависи от броя на използваните до момента подреждания. Аз определено залагам на това, че в историята е ползвано поне едно подреждане на тесте от 52 карти. Някой залага ли на противното?

Мислите ли, че греша?
Нека някой да напише формулата, по която се пресмята очакваната стойност!

[Genie_Almo]

Нека броят на всички възможни разбърквания е [tex]n[/tex]. Да забравим за момент това, което всички знаят, а именно, че [tex]n=52![/tex] . Да предположим, че броят на всички уникални подредби, които човечеството така и не е успяло да постигне преди опитите на лирическия герой от тази задача, е [tex]k[/tex]. Нека [tex]X[/tex] е случайна величина, която приема за стойност броя опити до постигане на уникална подредба. Тогава, плътността на разпределението на X ще е:

[tex]P(X=1) = \left( \frac{n-k}{n} \right)^0 * \frac{k}{n}[/tex]

[tex]P(X=2) = \left( \frac{n-k}{n} \right)^1 * \frac{k}{n}[/tex]

[tex]P(X=3) = \left( \frac{n-k}{n} \right) ^2 * \frac{k}{n}[/tex]

.....

[tex]P(X=x) = \left( \frac{n-k}{n} \right) ^{x-1} * \frac{k}{n}[/tex]

.....

Съответно, математическото очакване за броя опити до постигане на уникална подредба е:

[tex]E(X) = 1*\left( \frac{n-k}{n} \right)^0 * \frac{k}{n} + 2*\left( \frac{n-k}{n} \right)^1 * \frac{k}{n} + 3*\left( \frac{n-k}{n} \right) ^2 * \frac{k}{n} + ... + x*\left( \frac{n-k}{n} \right) ^{x-1} * \frac{k}{n} + ... =[/tex]

[tex]=\frac{k}{n}* \left( 1*\left( \frac{n-k}{n} \right)^0 + 2*\left( \frac{n-k}{n} \right)^1 + 3*\left( \frac{n-k}{n} \right) ^2 + ... + x*\left( \frac{n-k}{n} \right) ^{x-1} + ...\right)[/tex] (1)

Умножаваме страните на равенството с [tex]\left( \frac{n-k}{n} \right)[/tex] . (тук е важно да се предположи, че [tex]n \ne k[/tex] - противното би означавало, че все още няма нито една разиграна подредба в историята )

[tex]E(X)*\left( \frac{n-k}{n} \right) =\frac{k}{n}* \left( 1*\left( \frac{n-k}{n} \right)^1 + 2*\left( \frac{n-k}{n} \right)^2 + 3*\left( \frac{n-k}{n} \right) ^3 + ... + x*\left( \frac{n-k}{n} \right) ^{x} + ...\right) =[/tex]

[tex]= \frac{k}{n}* \left(0*\left( \frac{n-k}{n} \right)^0+1*\left( \frac{n-k}{n} \right)^1 + 2*\left( \frac{n-k}{n} \right)^2 + 3*\left( \frac{n-k}{n} \right) ^3 + ... + x*\left( \frac{n-k}{n} \right) ^{x} + ...\right)[/tex] (2)

После от (1) вадим (2) и получаваме:

[tex]E(X)*\left( \frac{k}{n} \right) =\frac{k}{n}* \left( \left( \frac{n-k}{n} \right)^0 + \left( \frac{n-k}{n} \right)^1 + \left( \frac{n-k}{n} \right) ^2 + ... + \left( \frac{n-k}{n} \right) ^{x-1} + \left( \frac{n-k}{n} \right) ^{x} + ...\right)[/tex]

Следователно:

[tex]E(X) = \left( \frac{n-k}{n} \right)^0 + \left( \frac{n-k}{n} \right)^1 + \left( \frac{n-k}{n} \right) ^2 + ... + \left( \frac{n-k}{n} \right) ^{x-1} + \left( \frac{n-k}{n} \right) ^{x} + ... = \left( \frac{1}{1-\left( \frac{n-k}{n}\right) }\right) = \frac{n}{k}[/tex]

Така намираме очквания брой опити, необходими за постигане на уникална подредба на тестето. Всъщност, горното е един от възможните начини да се стигне до широко известния факт, че „ако вероятността за успех при всеки опит е [tex]p[/tex], то очакваният брой опити до постигане на успех е [tex]\frac{1}{p}[/tex] ” .
Сега можем да се върнем към онова, което услужливо "забравихме" в началото - това, че [tex]n=52![/tex] .

Остава по някакъв начин да определим това [tex]k[/tex], за да намерим и някакъв количествен израз на оценката. Да си припомним, че [tex]k[/tex] са броят уникални подредби, които не са възпроизведени до този момент в историята на човечеството. Но колко горе-долу биха могли да бъдат те ? Да опитаме да определим обратното - броя на подредбите [tex]m[/tex], които до момента са били възпроизведени от човечеството. Тогава ще можем да намерим и [tex]k[/tex], което ще е равно на [tex]52!-m[/tex] .

Тук идва момента за смелите предположения и спекулации.
....

Според wikipedia.org ( https://en.wikipedia.org/wiki/Standard_52-card_deck#History ) , стандартното тесте от 52 карти се появява някъде в края на 15-ти или началото на 16-ти век. Да приемем обаче, че в последните 600 години, всеки от десет милиарда човека произвежда всяка секунда по една нова, уникална подредба с този вид карти. Това предположение е твърде пресилено, тъй като никога досега на Земята не са живеели 10млрд. човека едновременно, а още по-малко са били способни всяка секунда от живота си да правят по едно уникално разбъркване на тестето. Но нека умишлено се опитаме да намалим вероятността за постигане на уникална подредба от страна на нашия герой.
Сега ще използваме изчислителния ресурс на WolframAlpha.com , за да направим някои сметки.

Последните 600 години като времетраене се равняват на около [tex]1.893*10^{10}[/tex] секунди (https://www.wolframalpha.com/input?i=seconds+in+the+last+600+years) . Като умножим по 10млрд. човека, които всяка секунда правят по едно уникално разбъркване, получаваме [tex]1.893*10^{20}[/tex] уникални подредби до този момент.

С помощта на този гений с не дотам естествен интелект можем да сметнем и колко е 52! -> около [tex]8.066*10^{67}[/tex](https://www.wolframalpha.com/input?i=52%21)

При тези порядъци вече може да се предвкуси верният отговор на задачата.

Броят $k$ на невъзпроизведените до момента подредби е $8.066*10^{67} - 1.893*10^{20} = 1.893*10^{20} * (4.261*10^{47} - 1) \approx 1.893*10^{20} * 4.261*10^{47} \approx 8.066*10^{67}$

Всичко това показва, че броят на възпроизведените по нашия модел уникални пермутации на карти е твърде незначителен в сравнение с тези, които все още не са се появявали на бял свят. При това ние се опитахме значително да ги завишим, но явно нашите усилия се оказват практически безплодни.

И така, за очквания брой опити, необходими за постигане на уникална подредба, ( за който доказахме, че е $\frac{n}{k}$) е вече ясно, че много силно се приближа до 1 . ( https://www.wolframalpha.com/input?i=52%21%2F%2852%21-1.893*10%5E20%29 )

[tex]\left( \frac{52!}{52!-1.893*10^{20}} \right) = 1.0000000000000000000000000000000000000000000000023469412691125823...[/tex]

Всичко това ни представя може би донякъде изненадващия резултат, че при всяко случайно разбъркване на тестето, ние правим по една уникална подредба, която никога преди не е била повтаряна!