Դիտել 100 բանտարկյալների խնդիր էջի վիքիկոդը

[[Պատկեր:100 prisoners problem qtl1.svg|thumb|upright=1.4|Յուրաքանչյուր բանտարկյալ պետք է գտնի իր թիվը 100 դարակից, բայց իրավունք ունի բացել միայն 50 դարակ։]]
'''100 բանտարկյալի խնդիր''', [[մաթեմատիկա|մաթեմատիկական]] [[մաթեմատիկական խնդիր|խնդիր]] [[հավանականությունների տեսություն|հավանականությունների տեսությունում]] և [[կոմբինատորիկա|կոմբինատորիկայում]]։ Խնդրում 100 համարակալված բանտարկյալներ փրկվելու համար պետք է գտնեն իրենց թիվը 100 տարբեր դարակներում։ Ըստ կանոնների՝ յուրաքանչյուր բանտարկյալ իրավունք ունի բացել 50 դարակ և չի կարող շփվել այլ բանտարկյալների հետ։ Առաջին հայացքից իրավիճակը անհույս է թվում, սակայն որոշ մարտավարությունների դեպքում փրկության բարձր հավանականություն կա։

Դանիացի ինֆորմատիկ Փիթեր Բրո Միլթերսոնը առաջին անգամ ներկայացրել է խնդիրը 2003 թվականին։

== Խնդիր ==
Գրականության մեջ կան 100 բանտարկյալների խնդրի տարբեր ձևակերպումներ։ Հետևյալ տարբերակը առարաջկել են [[Ֆիլիպ Ֆլայոլե|Ֆիլիպ Ֆլայոլեն]] և [[Ռոբերտ Սեջվիկ|Ռոբերտ Սեջվիկը]]<ref name="flajolet">{{Citation |author=Philippe Flajolet, Robert Sedgewick |title=Analytic Combinatorics |title-link=Analytic Combinatorics |pages=124 |year=2009 |publisher=Cambridge University Press}}</ref>.

:''Բանտի տնօրենը մահվան դատապարտված 100 բանտարկյալների, որոնք համարակալված են 1-100 թվերով, առաջարկում է փրկության վերջին հնարավորություն։ Սենյակում կա 100 դարակ ունեցող պահարան։ Տնօրենը յուրաքանչյուր դարակում պատահականության սկզբունքով դնում է բանտարկյալներից մեկի համարը։ Բանտարկյալները իրար հետևից մտնում են սենյակ։ Յուրաքանչյուր բանտարկյալ կարող է բացել և ստուգել 50 կամայական դարակ։ Ստուգելուց հետո դարակները կրկին փակվում են։ Եթե այս որոնման ժամանակ բոլոր բանտարկյալները գտնում են իրենց թիվը, բոլոր բանտարկյալները ներվում են։ Եթե բանտարկյալներից մեկը չի գտնում իր թիվը, բոլոր բանտարկյալները մահվան են դատապարտվում։ Նախքան առաջին բանտարկյալի սենյակ մտնելը, բանտարկյալները կարող են քննարկել և որոշել մարտավորություն, բայց առաջին բանտարկյալի սենյակ մտնելուց հետ միմիյանց հետ շփվելու իրավունք չունեն։ Ո՞րն է լավագույն մարտավարությունը։''

Եթե բանտարկյալները դարակները ստուգեն իրարից անկախ և պատահական, ապա մեկ բանտարկյալի կողմից իր թիվը գտնելու հավանականությունը 50% է։ Հետևաբար, հավանականությունը, որ բոլոր բանտարկյալները կգտնեն իրենց թիվը հավասար է բոլոր առանձին հավանականությունների արտադրյալին, որը <big>(</big>{{sfrac|1|2}}<big>)</big><sup>100</sup> ≈ {{val|0.0000000000000000000000000000008}} է, ինչը չափազանց փոքր թիվ է։

== Լուծում ==
=== Մարտավարություն ===
Գոյություն ունի մարտավարություն, որի կիրառման դեպքում բանտարկյալների փրկման հավանականությունը ավելի քան 30% է։ Բանտարկյալները չպետք է նախօրոք որոշեն, թե որ դարակներն են բացելու։ Յուրաքանչյուր բանտարկյալ կարող է օգտագործել բացված դարակում եղած [[ինֆորմացիա|ինֆորմացիան]], որպեսզի որոշի, թե հաջորդը որ դարակը պետք է բացի։ Կարևոր դիտարկում է այն, որ այս կերպ բանտարկյալների հաջողությունը այլ բանտարկյալների հաջողությունից [[Անկախություն (հավանականությունների տեսություն)|հավանականորեն անկախ]] չէ, քանի որ բոլոր կախված են թվերի [[Բաշխում (մաթեմատիկա)|բաշխումից]]<ref name="curtin2">{{Citation |author=Eugene Curtin, Max Warshauer |title=The locker puzzle |journal=Mathematical Intelligencer |volume=28 |pages=28–31 |year=2006 |doi=10.1007/BF02986999 |s2cid=123089718}}</ref>։

Մարտավարությունը նկարագրելու համար հարմար է բանտարկյալներից բացի համարակալել նաև դարակները, օրինակ՝ ըստ տողերի՝ սկսած վերևի ձախ անկյունից։ Համարակալումից հետո մարտավարությունը հետևյալն է<ref name="stanley">{{Citation |author=Richard P. Stanley |title=Algebraic Combinatorics: Walks, Trees, Tableaux, and More |pages=187–189 |year=2013 |publisher=Springer}}</ref>՝

# Յուրաքանչյուր բանտարկյալ առաջինը բացում է իր թվով համարակալված դարակը,
# Եթե այդ դարակում կա իր թիվը, ուրեմն առաջադրանքը ավարտված է հաջողությամբ,
# Հակառակ դեպքում բանտարկյալը հաջորը բացում է դարակում գրված թվով դարակը,
# Բանտարկյալը կրկնում է 2 և 3 կետերը մինչև իրենց թիվը գտնելը, կամ ձախողվելը, եթե թիվը չի գտնվում առաջին 50 փորձից հետո։

Եթե բանտարկյալը անվերջ փորձերի իրավունք ունենար, նա ի վերջո կբացեր իր դարակը՝ ձևավորելով շղթա։ Սկսելով իր համարի դարակից, բանտարկյալը երաշխավորում է, որ նա գտնվում է այն շղթայում, որի մեջ գտնվում է իր թիվը։ Գոյություն ունի միայն մեկ շղթա, որի երկարությունը 50-ից մեծ է, քանի որ առավելագույնը մեկ շղթա կարող է պարունակել կեսից ավելի դարակներ։

=== Օրինակներ ===
Ստորև ներկայացված է խնդրի պարզեցված տարբերակ, որտեղ կան ընդամենը 8 բանտարկյալներ և դարակներ, բայց յուրաքանչյուր բանտարկյալ կարող է ստուգել 4 դարակ։ Բանտի տնօրենը դարակներում դասավորել է բանտարկյալների թվերը հետևյալ կերպ․

:{| class="wikitable" style="text-align:center"
|-
! դարակի համար
| &nbsp;1 &nbsp; || &nbsp; 2 &nbsp; || &nbsp; 3 &nbsp; || &nbsp; 4 &nbsp; || &nbsp; 5 &nbsp; || &nbsp; 6 &nbsp; || &nbsp; 7 &nbsp; || &nbsp; 8 &nbsp;
|-
! բանտարկյալի համար
| 7 || 4 || 6 || 8 || 1 || 3 || 5 || 2
|}

Բանտարկյալները այժմ վարվում են հետրյալ կերպ․
* Առաջին բանտարկյալը բացում է առաջին դարակը և գտնում յոթ թիվը։ Հետո բացում է յոթերորդ դարակը և գտնում հինգ թիվը։ Հետո բացում է հինգերորդ դարակը, որտեղ գտնում է իր թիվը։
* Երկրորդ բանտարկյալը բացում է երկրորդ, չորրորդ և ութերորդ դարակները այս հերթականությամբ։ Վերջին դարակում գտնում է իր թիվը՝ երկուսը։
* Երրորդ բանտարկյալը բացում է երրորդ և վեցերորդ դարակները, որտեղ գտնում է իր թիվը։
* Չորրորդ բանտարկյալը բացում է չորրորդ, ութերորդ և երկրորդ դարակները, որտեղ գտնում իր թիվը։ Սա նույն շղթան է, որը հանդիպել էր երկրորդ բանտարկյալին և կհանդիպի ութերորդ բանտարկյալին նույնպես։ Այս բանտարկյալներից յուրաքանչյուրը կգտնի իր թիվը երրորդ բացված դարակում։
* Հինգերորդ և յոթերորդ բանտարկյալները կգտնեն իրենց թվերը նույն սկզբունքով։

Այս օրինակում բոլոր բանտարկյալները գտան իրենց թվերը։ Սակայն, միշտ չէ, որ դա հնարավոր է։ Օրինակ՝ եթե հինգերորդ և ութերորդ դարակների թվերը փոխարինեք միմիյանց հետ, առաջին բանտարկյալը չի կարողանա գտնել իր թիվը առաջին, յոթերորդ, հինգերորդ և երկրորդ դարակները բացելուց հետո․
:{| class="wikitable" style="text-align:center"
|-
! դարակի համար
| &nbsp; 1 &nbsp; || &nbsp; 2 &nbsp; || &nbsp; 3 &nbsp; || &nbsp; 4 &nbsp; || &nbsp; 5 &nbsp; || &nbsp; 6 &nbsp; || &nbsp; 7 &nbsp; || &nbsp; 8 &nbsp;
|-
! բանտարկյալի համար
| 7 || 4 || 6 || 8 || 2 || 3 || 5 || 1
|}

Իսկ հետևյալ դասավորության դեպքում առաջին բանտարկյալը բացում է առաջին, երրորդ, յոթերորդ և չորրորդ դարակները, որից հետո ձախողվում է․
:{| class="wikitable" style="text-align:center"
|-
! դարակի համար
| &nbsp; 1 &nbsp; || &nbsp; 2 &nbsp; || &nbsp; 3 &nbsp; || &nbsp; 4 &nbsp; || &nbsp; 5 &nbsp; || &nbsp; 6 &nbsp; || &nbsp; 7 &nbsp; || &nbsp; 8 &nbsp;
|-
! բանտարկյալի համար
| 3 || 1 || 7 || 5 || 8 || 6 || 4 || 2
|}

Ընդ որում, այս դասավորության դեպքում վեցերորդ բանտարկյալից բացի բոլորը ձախողվում են։

=== Տեղափոխությամբ ներկայացում ===
{{Բազմապատիկ պատկերներ
|ուղղություն=horizontal
|պատկեր1=Permutation cycles qtl1.svg
|պատկեր2=Permutation cycles qtl2.svg
|լայնություն=300
|նկարագրություն=Տեղափոխության ներկայացումը գրաֆի տեսքով (1&nbsp;7&nbsp;5)(2&nbsp;4&nbsp;8)(3&nbsp;6) և (1&nbsp;3&nbsp;7&nbsp;4&nbsp;5&nbsp;8&nbsp;2)(6)}}
Տնօրենի կողմից դարակներին բանարկյալների թիվ նշանակելը մաթեմատիկորեն կարելի է ներկայացնել որպես 1-100 թվերի [[տեղափոխություն (մաթեմատիկա)|տեղափոխություն]]։ Նման տեղափոխությունը 1-100 բնական թվերի բազմության [[փոխմիարժեք համապատասխանություն]] է ինքն իր հանդեպ։ Թվերի հաջորդականությունը, որը շարունակական տեղափոխությունից հետո վերադառնում է առաջին թվին կոչվում է տեղափոխության [[ցիկլային տեղափոխություն|ցիկլ]]։ Յուրաքանչյուր տեղափոխություն կարելի է բաժանել տարանջատ ցիկլերի, այսինքն՝ ցիկլերի, որոնք չունեն ընդհանուր տարր։ Վերևի առաջին օրինակի տեղափոխությունը կարելի է ներկայացնել հետևյալ կերպ

:<math>(1 ~ 7 ~ 5 )( 2 ~ 4 ~ 8) (3 ~ 6)</math>

որը կազմված է 3 երկարությամբ երկու և 2 երկարությամբ մեկ ցիկլից։ Երրորդ օրինակի տեղափոխությունը կունենա հետևյալ տեսքը՝

:<math>(1 ~ 3 ~ 7 ~ 4 ~ 5 ~ 8 ~ 2) (6)</math>

որը կազմված է 7 և 1 երկարություններ ունեցող մեկական ցիկլերից։ Այս նշանակումը եզակի չէ, քանի որ <math>l</math> երկարությամբ ցիկլը կարելի է գրել <math>l</math> տարբեր ձևով՝ կախված ցիկլի առաջին թվից։ Դարակները բացելու ընթացքում յուրաքանչյուր բանտարկյալ հետևում է մեկ ցիկլի, որը միշտ ավարտվում է իրենց թվով։ Ութ բանտարկյալների դեպքում այս մարտավարությունը հաջողվում է այն և միայն այն դեպքում, երբ ամենաերկար ցիկլի երկարությունը չի գերազանցում 4-ը։ Եթե տեղափոխությունը պարունակում է 5 կամ ավել երկարություն ունեցող ցիկլ, ապա բոլոր այն բանտարկյալները, որոնց թիվը գտնվում է այդ ցիկլում չեն գտնում իրենց թիվը առաջին չորս քայլից հետո։

=== Հաջողության հավանականություն ===
[[Պատկեր:Permutation longest cycle length pmf qtl2.svg|thumb|1-ից 100 թվերի պատահական տեղափոխության ամենաերկար ցիկլի երկարության [[Բաշխում (մաթեմատիկա)|բաշխումը]]։ Կանաչ տարածքը համապատասխանում է բանտարկյալների փրկության հավանականությանը։]]

Նախնական խնդրում 100 բանտարկյալներին հաջողվում է փրկվել, եթե տեղափոխության ամենաերկար ցիկլի երկարությունը չի գերազանցում 50-ը։ Հետևաբար, իրենց փրկվելու հավանականությունը հավասար է հավանականությանը, որ 1-ից 100 թվերի [[պատահական տեղափոխություն]]ը չի փարունակում 50-ից մեծ երկարություն ունեցող ցիկլ։ Այս հավանականությունը կարելի է հաշվել հետևյալ կերպ։

1-ից 100 թվերի տեղափոխությունը կարող է պարունակել առավելագույնը մեկ <math>l > 50</math> երկարությամբ ցիկլ։ Գոյություն ունի այդ ցիկլի տարրեը ընտրելու ճիշտ <math>\tbinom{100}{l}</math> տարբերակ (տես՝ [[ընտրույթ]])։ Այս ցիկլում թվերը կարող են դասավորվել <math>(l-1)!</math> ձևով, քանի որ <math>l</math> երկարություն ունեցող իրարից տարբեր ցիկլերը կարելի է ներկայացնել <math>l</math> տեղափոխությամբ՝ ցիկլերի սիմետրիայի պատճառով։ Մնացած թվերը կարելի է դասավորել <math>(100-l)!</math> ձևով։ Հետևաբար, 1-ից 100 թվերի <math>l > 50</math> երկարություն ունեցող տեղափոխությունների քանակը հավասար է

:<math>\binom{100}{l} \cdot (l-1)! \cdot (100-l)! = \frac{100!}{l}</math>։

Հավանականությունը, որ [[հավասարաչափ բաշխում|հավասարաչափ բաշխված]] պատահական տեղափոխությունը չի ունենա 50-ից մեծ երկարություն ունեցող ցիկլ հաշվվում է [[պատահույթ]]ի և այդ [[պատահույթի լրույթ]]ի բանաձևով․

:<math>1 - \frac{1}{100!} \left( \frac{100!}{51} + \ldots + \frac{100!}{100} \right) = 1 - \left( \frac{1}{51} + \ldots + \frac{1}{100} \right) = 1 - ( H_{100} - H_{50} ) \approx 0.31183,</math>

որտեղ <math>H_n</math>-ը <math>n</math>-րդ հարմոնիկ թիվն է։ Հետևաբար, ցիկլին հետևող մարտավարությամբ բանատրկյալները փրկվում են ավելի քան 31% դեպքերում<ref name="stanley" />։

=== Ասիմպտոտիկ հավանականություն ===
[[Պատկեր:Integral Test.svg|thumb|Հարմոնիկ թվերը կարելի է մոտարկվել լոգարիթմով։]]

Եթե 100-ի փոխարեն դիտարկվում է <math>2n</math> բանտարկյալ, որտեղ <math>n</math>-ը կամայական բնական թիվ է, ապա այս մարտավարությունը կիրառելու դեպքում բանտարկյալների փրկության հավանականությունը տրվում է հետևյալ կերպ՝

:<math>1 - ( H_{2n} - H_n ) = 1 - (H_{2n} - \ln 2n) + (H_n - \ln n) - \ln 2</math>։

Օգտվելով [[Էյլեր-Մասկերոնի հաստատուն|Էյլեր-Մասկերոնի <math>\gamma</math> հաստատունից]] և դիրատկելով  <math>n \to \infty</math> սահմանաը, ստանում ենք՝

:<math>\lim_{n \to \infty} (H_n - \ln n) = \gamma</math>

որից հետևում է, որ փրկման ասիմպտոտիկ հավանականությունը հավասար է՝

:<math>\lim_{n \to \infty} ( 1 - H_{2n} + H_n ) = 1 - \gamma + \gamma - \ln 2 = 1 - \ln 2 \approx 0.30685</math>։

Քանի որ հավանականությունների հաջորդականությունը [[Մոնոտոն ֆունկցիա|մոնոտոն նվազում]] է, հետևաբար այս մարտավարությամբ բանտարկյալները փրկվում են ավելի քան 30% դեպքերում՝ անկախ բանտարկյալների քանակից<ref name="stanley" />։

=== Օպտիմալություն ===
2006 թվականին Յուջին Կուրտինը և Մաքս Վարշաուերը ապացուցեցին, որ ցիկլին հետևելու մարտավարությունը օպտիմալ է։ Ապացույցը հիմնված է այս և առնչվող խնդրի, որտեղ բանտարկալները իրավունք ունեն ներկա գտնվել սենյակում և տեսնել դարակների բացումը,  համարժեքության վրա։ Մաթեմատիկորեն այս համարժեքությունը հիմնված է [[Ֆոատայի լեմմա]]յի վրա (ցիկլերի կանոնական նշանակման և տեղափոխությունների նշանակման փոխմիարժեք համապատասխանություն)։ Երկրորդ խնդրում փրկության հավանականությունը կախված չէ ընտրված մարտավարությունից և հավասար է նախնական խնդրի հավանականությանը, եթե այն լուծելու համար կիրառվի ցիկլին հետևելու մարտավարությունը։ Քանի որ նախնական խնդրի կամայական մարտավարություն կարելի է կիրառել երկրորդ խնդրի համար, բայց այն չի կարող ունենալ ավելի բարձր փրկման հավանականություն, ուրեմն ցիկլին հետևելու մարտավարությունը օպտիմալ է<ref name="curtin">{{Citation |author=Eugene Curtin, Max Warshauer |title=The locker puzzle |journal=Mathematical Intelligencer |volume=28 |pages=28–31 |year=2006 |doi=10.1007/BF02986999 |s2cid=123089718}}</ref>։

== Պատմություն ==
100 բանտարկյալների խնդիրն առաջին անգամ դիտարկել է դանիացի ինֆորմատիկ Փիթեր Բրո Միլթերսոնը 2003 թվականին։ Նա այն հրատարակել է Աննա Գալի հետ «30. Ավտոմատների, լեզուների և ծրագրավորման միջազգային կոլոքվիումի» ({{lang-en|30. International Colloquium on Automata, Languages and Programming}}, ([[ICALP]])) աշխատություններում<ref name="miltersen">{{Citation |author=Anna Gál, Peter Bro Miltersen |title=Proceedings 30th International Colloquium on Automata, Languages and Programming (ICALP) |pages=332–344 |year=2003 |contribution=The cell probe complexity of succinct data structures}}</ref>։ Իրենց տարբերակում առաջին խաղացողը (թիմ Ա) պատահական գունավորում է Բ թիմի անդամների անուններով թղթի կտորները կարմիր կամ կապույտ և տեղադրում տարբեր տուփերում։ Որոշ տուփեր դատարկ են (տես [[#Դատարկ դարակներ|ներքևում]])։ Հաղթելու համար Բ թիմից յուրաքանչյուրը տուփերի կեսը բացելուց հետո պետք է գուշակի իր գույնը<ref name="miltersen"/>։ Սկզբում Միլթերսոնը ենթադրել է, որ հաղթելու հավանականությունը արագ ձգտում է զրոյի, երբ խաղացողների քանակը ձգտում է անվերջության։ Սական, Սվեն Սքյումը, որը [[Օրհուսի համալսարան]]ում Միլթերսոնի կոլեգան էր, առաջարկել է ցիկլին հետևելու մարտավարությունը խնդրի այն դեպքի համար, երբ դատարկ տուփեր չկան։ Հրատարակությունում այս պարտավարությունը գտնելը հանձնարարված էր որպես վարժություն։ Հոդվածը ստացել լավագույն հոդվածի մրցանակ<ref name="curtin" />։

2004 թվականի ամռանը խնդիրը հայտնվել է [[Մաթեմատիկական գիտությունների գիտահետազոտական ինստիտուտ]]ի կողմից հրատարակվող «Էմիսարը» ({{lang-en|The Emissary}}) եռամսյա հանդեսի Ջո Բուլերի և [[Էլվին Բեռլեկեմպ]]ի կողմից գլուխկոտրուկների բաժնում։ Այնտեղ հեղինակները տուփերը փոխարինել են ROM-ներով (միայն կարդալու հիշողություն), իսկ մասնակիցների համարով գունավորված թղթերը՝ մասնակիցների թիվը դրական կամ բացասական [[Նշան (մաթեմատիկա)|նշանով]]։ Հեղինակները նշել են, որ հաղթելու հավանականությունը կարելի է մեծացնել նույնիսկ այն դեպքում, երբ առաձին խաղացողը չի գտնում իր թիվը։ Դրան հասնելու համար, յուրաքանչյուր անդամ է հաշվի բոլոր բացված տուփերում նշանների արտադրյալը, և եթե վերջում նրան չի հաջողվում գտնել իր թիվը, խաղացողը պետք է ենթադրի, որ իր թիվը ունի հաշվված նշանը։ Չնայած այս ենթադրությունը ճիշտ է միայն 50% դեպքերում, եթե ցիկլի երկարությունը <math>1 + \lfloor n/2 \rfloor</math> է, ապա բոլոր խաղացողները միաժամանակ կա՛մ ճիշտ կլինեն, կա՛մ սխալ։ Մարտավարության այս փոփոխությունը զգալի առավելություն է տալիս փոքր քանակով խաղացողների դեպքում, բայց աննշան է մեծ թվով խաղացողների դեպքում<ref name="buhler">{{Citation |author=Joe Buhler, Elwyn Berlekamp |title=Puzzles Column |journal=The Emissary |volume=Spring 2004 |pages=3 |year=2004 |url=http://www.msri.org/web/msri/about-msri/news/emissary-newsletter |access-date=2024 թ․ փետրվարի 9 |archive-url=https://web.archive.org/web/20230705065619/https://www.msri.org/web/msri/about-msri/news/emissary-newsletter |archive-date=2023 թ․ հուլիսի 5 |url-status=live}}</ref>։

Հաջորդ տարիներին խաղը մտել է մաթեմատիկական գրականության մեջ, որտեղ ներկայացվել է տարբեր տեսքերով, ինչպես օրինակ՝ սեղանին քաղաքարտերով<ref>{{Citation |author=Richard E. Blahut |title=Cryptography and Secure Communication |pages=29–30 |year=2014 |publisher=Cambridge University Press}}</ref> կամ պահարաններում դրամապանակներով<ref name="curtin" />։ Բանտարկյալների տեսքով այն հրատարակվել է 2006 թվականին Քրիստոֆ Պոպպեի կողմից «[[Scientific American]]»-ում և Փիթեր Ուինքլերի կողմից «College Mathematics Journal»-ում<ref name="pöppe">{{Citation |author=Christoph Pöppe |title=Mathematische Unterhaltungen: Freiheit für die Kombinatoriker |journal=Spektrum der Wissenschaft |volume=6/2006 |pages=106–108 |year=2006 |url=http://www.spektrum.de/alias/mathematische-unterhaltungen/freiheit-fuer-die-kombinatoriker/848868 |access-date=2024 թ․ փետրվարի 9 |archive-url=https://web.archive.org/web/20141221205420/http://www.spektrum.de/alias/mathematische-unterhaltungen/freiheit-fuer-die-kombinatoriker/848868 |archive-date=2014 թ․ դեկտեմբերի 21 |url-status=live |language=german}}</ref><ref name="winkler">{{Citation |author=Peter Winkler |title=Names in Boxes Puzzle |journal=College Mathematics Journal |volume=37 |number=4 |pages=260, 285, 289 |year=2006}}</ref>։ Փոքր փոփոխություններով Ֆիլիպ Ֆլայոլեն, Ռոբերտ Սեջվիկը և Ռիչարդ Պ. Սթենլին օգտագործել են այս խնդիրը իրենց կոմբինատորիկայի դասագրքում<ref name="flajolet" /><ref name="stanley" />։

== Տարբերակներ ==
=== Դատարկ տուփեր ===
ՍԿզբում Գալն ու Միլթերսենը իրենց հոդվածում դիտարկել են այն դեպքը, երբ տուփերի քանակը երկու անգամ մեծ է երկրորդ թիմի անդամների քանակից, բայց տուփերի կեսը դատարկ է։ Սա ավելի բարդ խնդիր է, քանի որ դատարկ տուփերը ոչ մի տեղ չեն ուղղորդում, հետևաբար ցիկլին հետևելու մարտավարությունը չի կարող կիրառվել։ Հայտնի չէ, թե արդյոք այս դեպքում հաղթելու հավանականությունը ձգտում է զրոյի, երբ խաղացողների քանակը ձգտում է անվերջության<ref name="miltersen" />։

2005 թվականին Նավին Գոյալը և [[Մայքլ Սաքս (մաթեմատիկոս)|Մայքլ Սաքս]]ը ավելի ընդհանուր խնդրի համար, որտեղ դատարկ տուփերի և թիմի յուրաքանչյուր անդամին թույլատրվող փորձերի քանակը փոփոխական է, մշակել են մարտավարություն՝ հիմնվելով ցիկլին հետևելու մարտավարության վրա։ Այս դեպքում նույնպես հաղթելու հավանականությունը ձգտում է զրոյի, բայց ավելի դանդաղ, քան Գալն ու Միլթերսենը առաջարկել էին։ Եթե խաղացողների քանակն ու թույլատրելի փորձերի հարաբերությունը ֆիքսված է, փրկվելու հավանականությունը մեծ է զրոյից, երբ ավելի շատ դատարկ տուփեր են ավելացվում<ref>{{Citation |author=Navin Goyal, Michael Saks |title=A parallel search game |journal=Random Structures & Algorithms |volume=27 |number=2 |pages=227–234 |year=2005 |doi=10.1002/rsa.20068 |s2cid=90893}}</ref>։

2009 թվականին [[Դեյվիդ Ավիս]]ը և [[Էնն Բրոդբենտ]]ը դիտարկել են խնդրի [[Քվանտային բարդության տեսություն|քվանտային]] տարբերակ, որտեղ երկրորդ թիմի անդամները վստահաբար հաղում են<ref>{{Citation |author=David Avis, Anne Broadbent |title=Third International Conference on Quantum, Nano and Micro Technologies ICQNM '09 |pages=63–66 |year=2009 |contribution=The quantum locker puzzle}}</ref>։

=== Չարամիտ տնօրեն ===
Եթե տնօրենը պարտավոր չէ թվերը դարակներում պատահական բաշխել, և տեղյակ է, որ բանտարկյալները պատրաստվում են կիրառել վերևում նշված մարտավարությունը, նա կարող է ձախողել մարտավարությունը։ Դրա համար տնօրենը պարզապես պետք է համոզվի, որ դարակներում բանտարկյալների թվերը 50-ից մեծ ցիկլով տեղափոխություն են կազմում։ Այս դեպքում բանտարկյալները կարող են պարզապես համաձայնվել և դարակները պատահականության սկզբունքով վերահամարակալել<ref>{{Citation |author=Philippe Flajolet, Robert Sedgewick |title=Analytic Combinatorics |pages=177 |year=2009 |publisher=Cambridge University Press}}</ref>։

=== Բանտարկյալների մեկը կարող է մեկ փոփոխություն անել ===
Այն դեպքում, երբ բանտարկյալներից մեկը կարող է սկզբում մտնել սենյակ, '''ստուգել բոլոր դարակները''' և փոխանակել երկու դարակի պարունակությունը, բոլորը բանտարկյալները միշտ փրկվում են։ Այս պնդումը ճիշտ է, քանի որ 50-ից մեծ երկարություն ունեցող կամայական ցիկլ հնարավոր է կոտրել այնպես, որ բոլոր ցիկլերը 50-ից փոքր երկարություն ունենան։

=== Իր թիվը գտնող յուրաքանչյուր բանտարկյալ փրկվում է ===
Այն դեպքում, երբ իր թիվը գտնող յուրաքանչյուր բանտարկյալ ազատ է արձակվում, կամայական բանտարկյալի փրկվելու սպասվող հավանականությունը հետևյալն է (եթե տեղափոխությունը պատահական է). 

առանց պարտավարության՝ <math>\frac{1}{2}</math>,

սկզբնական խնդրի մարտավարությամբ՝ <math>(1 - \ln(2)) \cdot 1 + \sum_{k = \lfloor n/2 \rfloor + 1}^N  \frac{1}{k} \left(1-\frac{k}{n}\right) = 1 - \ln(2) + \sum_{\lfloor n/2 \rfloor + 1}^N \frac{1}{k} - \sum_{k = \lfloor n/2 \rfloor + 1}^N \frac{1}{n} = 1 - \ln(2) + \ln(2) - \frac{1}{2} = \frac{1}{2}:</math>

Պետք է նշել, որ չնայած այս [[մաթեմատիկական սպասում|սպասումները]] նույն արժեքն ունեն, դրանք տարբեր [[Հավանականության բաշխում|բաշխումներից]] են։ Երկրորդ մարտավարության դեպքում որոշ բանտարկյալների մահը կամ փրկվելը նախորոշված է տրված տեղափոխության դեպքում, մինչդեռ առաջին մարտավարության դեպքում (պատահական ընտրություն) անկախ տեղափոխությունից յուրաքաչյուր բանտարկյալ ունի փրկվելու 1/2 շանս։

=== Մոնտի Հոլի խնդիր ===
2009 թվականին Ադամ Ս. Լանդսբերգը առաջարկել է 100 բանտարկյալների խնդրի հետևյալ տարբերակը, որը հիմնված է հայտնի [[Մոնտի Հոլի պարադոքս]]ի վրա<ref name="landsberg" />.

:''Երեք փակ դռների հետևում պատահական բաշխված են մեքենա, մեքենայի բանալի և այծ։ Կան երկու խաղացողներ. առաջին խաղացողը պետք է գտնի մեքենան, երկրորդը՝ մեքենայի բանալին։ Խաղացողները շահում են մեքենան միայն այն դեպքում, երբ երկուսն էլ հաղջությամբ գտնում են իրենց մասը։ Առաջին խաղացողը մտնում է սենյակ և կարող է բացել երեք դռներից մեկը։ Եթե առաջինը հաջողությամբ գտնում է մեքենան, դռները նորից փակվում են և երկրորդ խաղացողն է մտնում սենյակ։ Երկրորդ խաղացողը նույնպես կարող է բացել երկու դուռ, բայց խաղացողները չեն կարող հաղորդակցվել միմիայնց հետ։ Ինչքա՞ն է հաղթելու հավանականությունը, եթե երկու խաղացողներն էլ օպտիմալ վարվեն։''

Եթե խաղացողները դռները պատահական բացեն, ապա հաղթելու հավանականությունը {{sfrac|4|9}} (մոտ 44%) է։ Սակայն, օպտիմալ մարտավարությունը հետևյալն է.

* Առաջին խաղացողը սկզբում բացում է առաջին դուռը։ Եթե մեքենան առաջին դռան հետևում է, ուրեմն առաջին խաղացողին հաջողվեց գտնել մեքենան։ Եթե առաջին դռան հետևում մեքենայի բանալին է, ուրեմն խաղացողը հաջորդը բացում է երկրորդ դուռը, իսկ եթե առաջին դռան հետևում այծն է, առաջին խաղացողը հաջորդը բացում է երրորդ դուռը։
* Երկրորդ խաղացողը սկզբում բացում է երկրորդ դուռը։ Եթե մեքենայի բանալին երկրորդ դռան հետևում է, ուրեմն երկրորդ խաղացողին հաջողվեց գտնել մեքենայի բանալին։ Եթե երկրորդ դռան հետևում այծ է, ուրեմն խաղացողը հաջորդը բացում է երրորդ դուռը, իսկ եթե երկրորդ դռան հետևում մեքենան է, ուրեմն խաղացողը բացում է առաջին դուռը։

Մեքենայի, մեքենայի բանալու և այծի հնարավոր վեց բաշխումների դեպքում խաղացողները բացում են հետևյալ դռները (կանաչ դեպքերում խաղացողին հաջողվել է գտնել իր իրը).

:{| class="wikitable"
| || Մեքենա − Բանալի − Այծ || Մեքենա − Այծ − Բանալի || Բանալի − Մեքենա − Այծ || Բանալի − Այծ − Մեքենա || Այծ − Մեքենա − Բանալի || Այծ − Բանալի − Մեքենա
|-
| Խաղացող 1
| style="background:#B9FFC5;" | Դուռ 1։ Մեքենա
| style="background:#B9FFC5;" | Դուռ 1։ Մեքենա
| style="background:#B9FFC5;" | Դուռ 1։ Բանալի <br /> Դուռ 2։ Մեքենա
| style="background:#FFCBCB;" | Դուռ 1։ Բանալի <br /> Դուռ 2։ Այծ
| style="background:#FFCBCB;" | Դուռ 1։ Այծ <br /> Դուռ 3։ Բանալի
| style="background:#B9FFC5;" | Դուռ 1։ Այծ <br /> Դուռ 3։ Մեքենա
|-
|-
| Խաղացող 2
| style="background:#B9FFC5;" | Դուռ 2։ Բանալի
| style="background:#B9FFC5;" | Դուռ 2։ Այծ <br /> Դուռ 3։ Բանալի
| style="background:#B9FFC5;" | Դուռ 2։ Մեքենա <br /> Դուռ 1։ Բանալի
| style="background:#FFCBCB;" | (Դուռ 2։ Այծ) <br /> (Դուռ 3։ Մեքենա)
| style="background:#FFCBCB;" | (Դուռ 2։ Մեքենա) <br /> (Դուռ 1։ Այծ)
| style="background:#B9FFC5;" | Դուռ 2։ Բանալի
|}
Այս մարտավարության հաջողությունը հիմնված է խաղացողների հաջողության և ձախողման միջև կորելացիա ստեղծելու վրա։ Այստեղ, հաղթելու հավանականությունը {{sfrac|2|3}} է, որը օպտիմալ է, քանի որ առաջին խաղացողը չի կարող դրանից ավելի բարձր հաղթելու հավանականություն ունենալ<ref name="landsberg">{{Citation |author=Adam S. Landsberg |title=The Return of Monty Hall |journal=Mathematical Intelligencer |volume=31 |number=2 |pages=1 |year=2009 |doi=10.1007/s00283-008-9016-8 |doi-access=free}}</ref>։ Այլ տարբերակներում երեք մրցանակներ թաքնված են երեք դռների հետևում և երեք խաղացողներ պետք է գտնեն իրենց նշանակված մրցանակը։ Այս դեպքում ևս հաղթելու հավանականությունը {{sfrac|2|3}} է, երբ կիրառվում է օպտիմալ մարտավարություն<ref>{{Citation |author=Eric Grundwald |title=Re: The Locker Puzzle |journal=Mathematical Intelligencer |volume=32 |number=2 |pages=1 |year=2010 |doi=10.1007/s00283-009-9107-1 |doi-access=free}}</ref>։

=== Կենտ թվով հնարավորություններ ===
Խնդրի տարբերակներից մեկում բանտարկյալները իրենց թվերը պետք է գտնեն ոչ թե առաջին 50 փորձի ընթացքում, այլ պետք է գտնեն կենտ համարով փորձի ժամանակ {{math|1, 3, ..., 97, 99}}: Այս դեպքում ևս ցանկացած բանտարկյալ ունի հաջողելու 50% հնարավորություն։ Հիմնական մարտավարությունը կաշխատի, եթե բանտարկյալների տեղափոխությունը ունի միայն կենտ երկարությամբ ցիկլեր։ 100 բանտարկյալների և հիմնական մարտավարության դեպքում փրկվելու հավանականությունը 7.9589% է, որը զգալիորեն մեծ է պատահական ընտրության դեպքում փրկվելու հավանականությունից` {{math|(1/2){{sup|100}}}}-ից։

== Տես նաև ==
* [[Բանտարկյալի դիլեմա]]
* [[Անսպասելի մահապատժի պարադոքս]]

== Ծանոթագրություններ ==
{{ծանցանկ}}

== Գրականություն ==
* {{Citation |author=Philippe Flajolet, Robert Sedgewick |title=Analytic Combinatorics |year=2009 |publisher=Cambridge University Press |isbn=978-1-139-47716-1}}
* {{Citation |author=Richard P. Stanley |title=Algebraic Combinatorics: Walks, Trees, Tableaux, and More |year=2013 |series=Undergraduate Texts in Mathematics |publisher=Springer |isbn=978-1-461-46998-8}}
* {{Citation |author=Peter Winkler |title=Mathematical Mind-Benders |year=2007 |publisher=Taylor and Francis |isbn=978-1-568-81336-3}}

== Արտաքին հղումներ ==
* Rob Heaton: [http://robertheaton.com/2014/01/13/mathematicians-hate-civil-liberties-100-prisoners-100-boxes/ Mathematicians hate civil liberties - 100 prisoners and 100 boxes], 13 January 2014
* Oliver Nash: [http://ocfnash.wordpress.com/2009/12/12/pity-the-prisoners/ Pity the prisoners] {{Webarchive|url=https://web.archive.org/web/20140714230456/http://ocfnash.wordpress.com/2009/12/12/pity-the-prisoners/ |date=2014-07-14 }}, 12 December 2009
* Jamie Mulholland: [https://web.archive.org/web/20140714120037/http://people.math.sfu.ca/~jtmulhol/math302/notes/25-Prisoners-in-Boxes.pdf Prisoners in Boxes], Spring 2011 (PDF)
* [[MinutePhysics]]: {{YouTube|eivGlBKlK6M|An Impossible Bet}} and {{YouTube|C5-I0bAuEUE|Solution to The Impossible Bet}}, 8 December 2014
* [[Veritasium]]: {{YouTube|iSNsgj1OCLA|The Riddle That Seems Impossible Even If You Know The Answer}}, 20 June 2022
* Robert Feldt: [https://gist.github.com/robertfeldt/5038002a2654a0f06e4d8af51ab5d2f6 Stochastic simulation in Julia] to check the optimal strategy, 6 July 2022

[[Կատեգորիա:Մաթեմատիկական գլուխկոտրուկներ]]