Ընտրող հարսնացուի առաջադրանք

Ընտրող հարսնացուի առաջադրանք (որոշման կայացման խնդիր), գիտական առաջադրանք, որն առաջին անգամ ձևակերպվել է 1960 թվականին Մարտին Գարդների կողմից։

Անգլալեզու գիտական գրականության մեջ հանդիպում է նաև քարտուղարի առաջադրանք տարբերակը։

Ձևակերպում

Առաջադրանքը կարելի է ձևակերպել հետևյալ կերպ.

1. Հարսնացուն փնտրում է իր համար ամուսին, ընդորում գոյություն ունի միայն մեկ թափուր տեղ։
2. Կա թեկնածուների հայտնի թիվ՝ $n$:
3. Հարսնացուն պատահական սկզբունքով շփվում է թեկնածուների հետ՝ ամեն մեկի հետ միայն մեկ անգամ։
4. Յուրաքանչյուր թեկնածուի պարագայում հայտնի է, թե նա արդյոք լավն է կամ վատն է նախորդ թեկնածուից։
5. Հերթական թեկնածուի հետ շփման արդյունքում հարսնացուն պետք է կամ մերժի, կամ ընդունի թեկնածուի առաջարկությունը։ Եթե ընդունի առաջարկությունը, ապա գործընթացը դադարեցվում է, իսկ եթե հարսնացուն մերժի թեկնածուին, ապա հարսնացուն այլևս չի կարող վերադառնալ նրա մոտ։
6. Նպատակն է ընտրել լավագույն թեկնածուին։

Լուծում

1963 թվականին Ռուսաստանի գիտությունների ակադեմիայի ակադեմիկոս Եվգենի Դինկինը առաջ քաշեց առաջադրանքի լուծումը՝ մասնավոր դեպքի համար։ Առաջադրանքի ընդհանուր լուծումը 1966 թվականին հայտնաբերել է Սաբիր Հուսեյնզադեն։

Առաջադրանքի նկատմամբ մեծ ուշադրություն է դարձվել հատկապես այն պատճառով, որ օպտիմալ ռազմավարությունը ունի հետաքրքիր յուրահատկություն։ Եթե հավանական թեկնածուների թիվը բավականին շատ է (օրինակ 100-ից ավելին), ապա օպտիմալ ռազմավարությունը կկայանա նրանում, որ մերժվեն բոլոր առաջին $n/e$ (որտեղ $e=2{,}718\,281\ldots$՝ բնական լոգարիթմի հիմքը) թեկնածուները և հետո ընտրվի այն առաջինը, որը նախորդներից ամենալավը կլինի։ $n$-ի ավելացման դեպքում լավագույն թեկնածուի ընտրության հավանականությունը ձգտում է $1/e$, այսինքն մոտ 37 %:

Հետաքրքիր փաստեր

Ռուսաստանի գիտությունների ակադեմիայի թղթակից-անդամ Բորիս Բերեզովսկին հայցվող գիտությունների դոկտորի գիտական աստիճանի համար գրված «Նախագծային որոշումների ընդունման ալգորիթացումը և դրանց կիրառման տեսական հիմքերի մշակումը» վերնագրով ատենախոսության մեջ ընդհանրական կերպով անդրադարձել է ընտրող հարսնացուի առաջադրանքին։

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

• С. М. Гусейн-Заде Разборчивая невеста. — МЦНМО, 2003. — Т. 25. — 20 с. — (Библиотека «Математическое просвещение»). — ISBN 5-94057-076-3
• С. М. Гусейн-Заде. Разборчивая невеста. Видео-лекция. Малый мехмат, МГУ, 30.11.2002.
• И. Р. Высоцкий, И. В. Ященко Задачи заочных интернет-олимпиад по теории вероятностей и статистике —  МЦНМО, 2017, с.255, 275 — ISBN 978-5-4439-1136-6