Seara, canibalul a capturat mai multe gnomi și le va mânca la micul dejun. Starea într-o stare bună, el a decis că va da mai multor gnomi șansa de a scăpa și de a explica condițiile.
„În dimineața următoare - a spus el, vă voi construi într-o coloană și a pus la întâmplare pe tine pălării în două culori (roșu și albastru) Deoarece ultimul din coloana, voi întreba ce culoare pălăria Togo, care va apela culoarea lui .. capace corect - da drumul, cei care numesc culoarea greșită. - să mănânce vei vedea pe toți cei care stau în față și auzi răspunsuri la cei din spatele, dar culoarea pălăriei nimeni nu vede să vorbească doar un singur cuvânt - .. „roșu“ sau " albastru ", altfel voi mânca pe rând."
Gnomii nu știu raportul dintre pălăria roșie și cea albastră. Nu pot fi date semnale suplimentare (intonare, pauze în răspunsuri etc.).
Cu toate acestea, pentru fiecare noapte a inventat piticii răspunsurile de ordine, care au asigurat supraviețuirea tuturor, dar unul dintre ei (în aceasta, cu toate acestea, a rămas, de asemenea, o șansă de a supraviețui), în aceste condiții.
Întrebare: în ce fel au venit gnomii?
RĂSPUNS
Cursul raționamentului
Soluțiile simple, atunci când fiecare pitic, de exemplu, numește culoarea capului în față, nu se potrivește. În acest caz, gnomii prin unul își vor cunoaște culoarea, iar alții vor trebui să se sacrifice pentru a salva inferiorul. Nu este potrivit.
Să ne imaginăm pentru o clipă că nu există restricții privind comunicarea dintre gnomi. Primul gnome va putea să vorbească și despre celelalte culori ale capacelor. Dar, din păcate, nimeni nu-l poate ajuta: nimeni nu-și vede capul deloc. Restul gnomilor fără opțiuni trebuie să vorbească numai culorile capacelor lor - altfel soluția nu va fi realizată. Doar primul pitic își poate permite luxul de a transmite restului o anumită codificare, cu ajutorul căreia pot supraviețui.
Deci, numai primul pitic, care vede toți oamenii care merg înainte, poate cripta câteva informații pentru restul. Dar ce poate fi criptat, dacă răspunsurile sunt doar 2: "roșu" sau "albastru"?
Faptul este că nu trebuie să transferați întreaga secvență. Fiecare pitic următor are aceleași informații ca toți ceilalți: el vede capacele din fața lui și aude răspunsurile colegilor săi anteriori în nenorocire. Din informația că primul pitic (și el a văzut toți piticii rămași) îi spune, este necesar să se izoleze informațiile pe care le are despre restul actualului pitic pentru a calcula culoarea capului său.
În două variante de răspunsuri este posibil să se cripteze, de exemplu, "chiar" și "ciudat". Apoi, ia o culoare roșie egală cu 1, iar albastrul va fi 0. Primul gnome rezumă culorile capacelor tuturor celorlalte, folosind acest cod. Iar rapoartele rezultate sunt cu voce tare (de exemplu, roșu - "chiar", "albastru" - ciudat - piticii au toată noaptea pentru a fi de acord asupra acestui lucru).
Cel de-al doilea pitic, după ce a auzit cifrul, îi însumează pe toți cei care sunt în față. Dacă rezultatul coincide cu ceea ce a spus primul pitic, atunci culoarea capacului său nu a afectat suma totală. Deci, este "zero" - albastru. Dacă rezultatul sa schimbat, atunci acesta este "unitatea" - roșu.
Cel de-al treilea și ulterior gnomii iau în considerare nu numai cei care sunt văzuți înainte, ci și răspunsurile gnomilor anteriori. Și comparați rezultatul cu cifrul primului gnom, calculând diferența (culoarea capului său).
Această metodă vă permite să supraviețuiți gnomei N-1. Total pitice astfel nu este important, problema este rezolvata pentru toate N. Primul pitic nu moară neapărat: 50% cod sansa poate coincide cu culoarea capacului și apoi va rămâne în viață și bine.
P.S. Ei spun că această sarcină este oferită în timpul unui interviu la Microsoft
Articole similare
-
Idei de fotografie pentru decorarea unei nunți pe plajă - portal de nunți aici nunta
-
Revista de nunta - trandafiri de nunta - №6 2018 - 2018 - trandafiri de nunta festive portal
Trimiteți-le prietenilor: