Ongelma vangeista ja korkkeista, joiden väri on määritettävä
Virkistys / / December 31, 2020
Suljettava järjestelmä näkee kaikki korkit, mutta voi sanoa vain "musta" tai "valkoinen", samalla kun se ilmoittaa kaikille piilotetuista tiedoista. Vangit eivät tiedä mustavalkoisten korkkien kokonaismäärää, vaihtoehtoja on enemmän kuin kaksi. Mutta pariteetin käsitteestä ne rajoittuvat vain kahteen versioon: luku voi olla joko parillinen tai pariton.
Avain ongelman ratkaisemiseen on tämä: vangit ovat yhtä mieltä siitä, että ensimmäinen vastaaja sanoo esimerkiksi "musta", jos hän näkee parittoman määrän mustia korkkeja edessä ja "valkoisia", jos hän näkee parillisen määrän mustia korkit.
Katsotaanpa esimerkkiä yllä olevasta kuvasta. Korkein vanki # 1 näkee kolme mustaa korkkia edessä. Hän sanoo "musta" ääneen. Tämä antaa kaikille muille tiedot siitä, että edessä on pariton määrä mustia korkkeja. Ensimmäinen vanki teki virheen lippiksensä värin kanssa, mutta se on okei: kun sen annetaan vastata väärin.
Vanki # 2 näkee pariton määrän mustia korkkeja edessään. Hän tajuaa olevansa valkoinen ja vastaa oikein. Vanki # 3 näkee parillisen määrän mustia korkkeja ja arvaa, että hänellä on musta korkki, jonka kaksi ensimmäistä vankia näki.
Vankeudessa oleva nro 4 kuulee vastauksen ja tajuaa, että hänen pitäisi etsiä parillinen määrä mustia korkkeja, koska hänen selänsä takana oli musta, mutta hän näkee vain yhden edessä ja päättelee, että korkki on musta. Vangit nro 5-9 etsivät parittomia määriä mustia korkkeja, jotka he vain näkevät, samalla kun tietävät, että heillä on valkoiset korkit. Vuosi tulee kymmenenteen vankiin. Jos vanki # 9 näki parittoman määrän mustia korkkeja, tämä tarkoittaa vain yhtä asiaa - vangilla # 10 on musta korkki.
Näin tämä algoritmi toimisi kaikille hubcaps-ryhmille. Ensimmäiselle osallistujalle virheellisen vastauksen todennäköisyys on 50%, mutta hänen antamansa tiedot parittomasta pariteetista antavat muiden vankien arvailla korkinsä värin.
Jokainen vastaaja alkaa arvioida parillisten ja parittomien ylärajojen määrää. Jos hänen mielessään laskettu luku ei ole sama kuin hän näkee, hänen korkki on samanvärinen. Joka kerta tässä tapauksessa seuraava vastaaja ottaa huomioon, että jäljellä olevien korkkien tasaisuus on nyt muuttunut.
Tämä palapeli on käännös TED-Ed-videosta.