100 կալանավորների ու լամպի խնդիր

Խնդիր 100 բանտարկյալների և լամպի մասին, հայտնի խնդիր դինամիկ իմացաբանական տրամաբանության ոլորտից՝ տեղեկատվության փոխանակման արձանագրություն կազմելու համար։

Ձևակերպում

Բանտ են մտել 100 բանտարկյալներ։ Նրանց ուղարկում են առանձին խցիկներ և մեկ առ մեկ բերվելու են մի սենյակ, որտեղ ոչինչ չկա, բացի մեկ լամպից, որը բանտարկյալին թույլատրվում է միացնել կամ անջատել. ի սկզբանե լամպն անջատված է։ Երաշխավորվում է, որ վաղ թե ուշ բանտարկյալներից յուրաքանչյուրը լամպով սենյակում կլինի այնքան անգամ, որքան ցանկանում է։ Ցանկացած պահի լամպով սենյակ բերված բանտարկյալը կարող է հայտարարել, որ բոլոր բանտարկյալներն արդեն գոնե մեկ անգամ եղել են սենյակում. եթե նա ճիշտ լինի, ապա բոլոր բանտարկյալներին բաց կթողնեն, եթե ոչ՝ մահապատժի կենթարկեն։ Նախքան առանձին խցիկներ ուղարկելը, բանտարկյալները հնարավորություն ունեն համաձայնության գալ միմյանց հետ։ Պահանջվում է մշակել ռազմավարություն, որը նրանց թույլ կտա ազատություն ստանալ

Դասական լուծում

Բանտարկյալներից ընտրվում է մեկը, որը կոչվում է հաշվորդ։ Սովորական կալանավորը լամպի սենյակում վարվում է հետևյալ կերպ․ Եթե նա տեսնում է, որ լամպն անջատված է, և ինքը երբեք չի միացրել լամպը, ապա նա միացնում է այն. հակառակ դեպքում ոչինչ չի անում։ Հաշվորդը, ընդհակառակը, արձագանքում է միայն միացված լամպին. նա անջատում է այն և հիշում, թե քանի անգամ է դա տեղի ունեցել։ 99-րդ անգամ լամպը անջատելուց հետո նա կարող է վստահ լինել, որ բոլոր բանտարկյալներն արդեն գոնե մեկ անգամ եղել են սենյակում։

Ընտրանքներ, ընդհանրացումներ և կապ այլ առաջադրանքների հետ

Եթե ավելացնենք այն պայմանը, որ օրական մեկ բանտարկյալ է բերվում լամպով սենյակ, օգտագործել որոշակի ենթադրություններ բանտարկյալի ընտրության հավանականության բաշխման տեսակի վերաբերյալ և/կամ հաշվի առնել ռազմավարություններ, որոնք երաշխավորում են ազատություն ստանալու մեկից մի փոքր ավելի քիչ հավանականություն, ապա հնարավոր են դառնում ավելի պարզ կամ ավելի արդյունավետ ռազմավարություններ մշակել։ Հնարավոր է նաև ընդհանրացում մի քանի սենյակների և անջատիչի ավելի քան երկու դիրքերի դեպքում, ինչպես նաև յուրաքանչյուր սենյակ մի քանի անգամ այցելելու անհրաժեշտություն և այլն։ Բացի այդ, խնդիրը զգալիորեն բարդանում է, երբ պահանջվում է, որ բանտարկյալների ռազմավարությունը սիմետրիկ լինի, այսինքն՝ բոլոր բանտարկյալները հետևեն նույն ալգորիթմին, եթե միևնույն ժամանակ անջատիչ(ներ)ի սկզբնական դիրքն անհայտ է։ Մի քանի սենյակների և երկու անջատիչների համար սիմետրիկ ռազմավարության մարտահրավերը կապված է «զարթնելու առաջադրանքի» (անգլ.՝ wakeup problem) հետ բաշխված հաշվարկների համար։

Ծագում

Առաջադրանքի հեղինակն անհայտ է։ Այն հայտնվել է 2001 թվականից ոչ ուշ։

Գրականություն

• Hans van Ditmarsch, Barteld Kooi. One Hundred Prisoners and a Light Bulb. — Springer, 2015. — Errata. — ISBN 9783319166940.

Արտաքին հղումներ

• «Задача 105155». problems.ru. Վերցված է 2019 թ․ ապրիլի 28-ին.
• К. Кноп (2011). «Заключенные и переключатель». Элементы. Վերցված է 2019 թ․ ապրիլի 28-ին.
• William Wu. «100 prisoners and a light bulb» (PDF). Վերցված է 2019 թ․ ապրիլի 28-ին.
• Majerech, Vladan (2022). «100 prisoners and a lightbulb -- looking back». arXiv:2208.00771 [cs.DM].