Овој проблем, познат како „проблем со авион со 100 седишта“, е популарно прашање за интервју за работа бидејќи го тестира разбирањето на кандидатите за веројатноста, рекурзијата и техниките за решавање проблеми. Често се појавува на интервјуа за работа во технологија и финансии, особено во компании кои бараат силни квантитативни вештини (на пример, Google, Facebook, Amazon и финансиски фирми како хеџ фондови и инвестициски банки).
Можете ли да го најдете вистинскиот одговор и да објасните? Пред да го проверите решението, обидете се сами да го решите овој проблем!
Решение
Изненадувачки, решението е 50% (1/2). Ајде да разбереме зошто.
Прво, да го поедноставиме означувањето на седиштата. Вообичаено, авионските седишта имаат сложени ознаки како „22A“ или „47G“, но тука можеме само да ги нумерираме седиштата од 1 до 100, според тоа на кој патник му припаѓа. Патникот 1 е доделен на седиштето 1, патникот 2 на седиштето 2 итн.
Според проблемот, патникот 1 по случаен избор избира седиште (тоа може да биде и седиштето 1). Да речеме дека патникот 1 седи на седиштето j¹ (надредениот знак се однесува на фактот дека патникот 1 е тој што го зазема ова седиште). Сега, вториот патник во линија има две можности:
(а) Ако седиштето 2 е сè уште слободно (т.е. j¹≠2), патникот 2 ќе седне на седиштето 2.
(б) Ако j¹=2 (што значи патникот 1 го зел седиштето на патникот 2), патникот 2 ќе биде принуден да седи на случајно седиште.
Оттука, случајот (а) ефективно го ресетира проблемот со еден патник помалку и едно помалку седиште, бидејќи патникот 2 седи на своето седишта и можеме да заборавиме на него. Случајниот избор на првиот патник е направен, но важи истата логика: секој преостанат патник од патникот 3 па натаму или ќе седне на своето седиште или ќе седне по случаен избор кога неговото место е веќе зафатено. Затоа, единственото нешто што го прави случајот (а) е да го рестартира проблемот со еден патник помалку и можеме да го игнорираме.
Од друга страна, во случајот (б), седиштата 1 и седиштето 100 сè уште се достапни, а патникот 2 сега има случаен избор кој ги вклучува овие две опции. Иако има и други достапни седишта (седишта од 3 до 99), но тие не влијаат на исходот како што влијаат седиштата 1 и 100. Зошто? Па, ако патникот 2 седи на друго место (да речеме седиштето 42), тогаш сите други патници до патникот 42 ќе можат да седат на нивните доделени седишта. Кога ќе дојде редот на патникот 42, ќе се случи истата ситуација: неговото седиште е заземено, но седиштата 1 и од 43 до 100 сè уште се достапни. Уште еднаш, го ресетиравме проблемот и се вративме на случајот (б), но со помалку патници за распределба. Сепак, седиштата 1 и 100 сè уште ќе бидат достапни без разлика низ колку повторувања на случајот (б) поминуваме. Поради оваа причина, ќе се фокусираме на овие две клучни места.
Од тука, клучната опсервација е дека, без оглед на тоа што се случува со посредничките патници, евентуално патник ќе седне или на 1 или на 100. Кога тоа ќе се случи, постојат две можности:
- Ако некој седне на седиштето 100: Последниот патник нема да има друг избор освен да седне на седиштето 1. Сите други патници пред него ќе можат да седат на своите седишта.
- Ако е избрано седиштето 1: Во овој случај, патникот 1 и патникот што седнал на седиштето 1 си ги заменуваат седиштата. Сите последователни патници ќе можат да седат на нивните одредени седишта, вклучително и последниот патник (100).
Бидејќи овие два исхода се подеднакво веројатни поради симетријата на проблемот (секој патник има еднакви шанси да седне на кое било случајно место кога неговото седиште е зафатено), веројатноста последниот патник да седне на неговото доделено седиште (седиште 100) е 50 отсто. Покрај тоа, во другите 50 отсто од случаите, тој патник ќе седне на седиштето на патникот 1.
