Enigmo pri arestitoj kaj ĉapeloj

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo

La enigmo pri arestitoj kaj ĉapeloj estas indukta enigmo (speco de logika enigmo) kiu engaĝas rezonadon pri agoj de aliaj uloj, en aspektoj de ludoteorio. Estas multaj variadoj, sed la centra temo restas la sama.

Kvar-ĉapela baza varianto de 2+2 ĉapeloj[redakti | redakti fonton]

Arestitoj en ĉapeloj

Laŭ la rakonto, kvar uloj estas arestitaj, sed la arestejo estas plena kaj la arestejisto ne havas lokon por meti ilin. Tiel la arestejisto venas kun la enigmo, kaj se ili sukcesos solvi ili povos iri liberaj sed se ili malsukcesos ili estos ekzekutitaj.

La arestejisto metas trion el ili sidantajn en linio. La kvara ulo estas metita trans ŝirmo (aŭ en apartia ĉambro). Li donas al ĉiuj kvar uloj vesti ĉapelojn. La arestejisto eksplikas ke estas du ruĝaj kaj du bluaj ĉapeloj. La arestitoj povas vidi la ĉapelojn antaŭ de si sed ne sur si aŭ malantaŭ. La kvara ulo malantaŭ la ŝirmo ne povas vidi aŭ esti vidata per ĉiu alia arestito. Neniu komunikado inter la uloj estas permesita.

Se iu arestito povas kompreni kaj diri voĉe al la arestejisto kiun koloron de ĉapelo li havas sur sia kapo, tiam ĉiuj kvar arestitoj iros liberaj. La enigmo estas trovi kiel la arestitoj povas eskapi.

Solvaĵo[redakti | redakti fonton]

Oni marku la arestitojn en linio kiel A B kaj C en ordo. Tial B povas vidi A (kaj lian ĉapelan koloron) kaj C povas vidi A kaj B (kaj iliajn ĉapelajn kolorojn).

La arestitoj scias ke estas nur du ĉapeloj de ĉiu koloro. Tiel se C observas ke A kaj B havas ĉapelojn de la sama koloro, C devas konkludi ke lia poseda ĉapelo estas la kontraŭa koloro. Tamen, se A kaj B havas ĉapelojn de malsamaj koloroj, tiam C nenion povas diri. La ŝlosilo estas ke B, post atendo de adekvata tempodaŭro, kaj sciante kion C devus fari, povas konkludi ke se C diras nenion do la ĉapeloj sur A kaj B devas esti de malsamaj koloroj. Estante pova vidi ĉapelon de A li povas konkludi lian posedan ĉapelan koloron. La kvara arestito ne estas uzata, lia nura destino en la engmo estas vesti la kvaran ĉapelon.

En komuno kun multaj enigmoj de ĉi tiu speco, la solvaĵo fidas sur la supozo ke ĉiuj partoprenantoj estas tutece racionalaj kaj estas inteligentaj sufiĉe por fari la adekvatajn konkludojn.

Post solvado de ĉi tiu enigmo, iu komprenkapablo en la naturo de komunikado povas esti ricevita per konsidero ke la signifo de silento de C atencas la regulon de foresto de komunikado; kun tio ke komunikado estas kutime difinita kiel la tradono de informo.

Kvar-ĉapela varianto de 3+1 ĉapeloj[redakti | redakti fonton]

En varianto de ĉi tiu enigmo estas 3 ĉapeloj de unu koloro kaj nur 1 ĉapelo de alia, estas sciate de kiu koloro estas 3 ĉapeloj kaj de kiu koloro estas 1 ĉapelo. La 3 arestitoj povas vidi unu la alian, kio estas ke A vidas B kaj C, B vidas A kaj C kaj C vidas A kaj B. D denove estas nur por vesti la lastan ĉapelon.

Solvaĵo[redakti | redakti fonton]

Estas du okazoj: en la bagatela okazo, unu el la tri arestitoj vestas la solo-koloran ĉapelon, kaj tial la aliaj du povas facile konkludi la koloron de iliaj ĉapeloj.

En la ne-bagatela okazo, la tri arestitoj A, B, C vestas ĉapelojn de la sama koloro, kaj D vestas la solo-koloran ĉapelon. Post mallonga tempo, ĉiuj kvar arestitoj devus kapabli konkludi ke pro tio ke neniu el la aliaj estis pova stati la koloron de lia poseda ĉapelo, D devas porti la solo-koloran ĉapelon.

Kvin-ĉapela varianto[redakti | redakti fonton]

En alia varianto, nur tri arestitoj kaj kvin ĉapeloj (supozite du nigraj kaj tri blankaj) estas koncernataj.

La tri arestitoj estas orditaj al stari en rekto vizaĝante la antaŭo, kun A en antaŭe kaj C malantaŭe. Al ili estas dirite ke tie estas du nigraj ĉapeloj kaj tri blankaj ĉapeloj. Unu ĉapelo estas tiam surmetita sur ĉiu kapo de arestito; ĉiu arestito povas nur vidi la ĉapeloj de la uloj antaŭ li kaj ne la sian posedan. La unua arestito kiu estas pova ĝuste diri la koloron de sia ĉapelo estos liberigita. Neniu komunikado inter la arestitoj estas permesita.

Post iu tempo, nur A estas povas diri ĝuste ke lia ĉapelo estas blanka. Kial estas tiel?

Solvaĵo[redakti | redakti fonton]

Alprenante ke A vestas nigran ĉapelon:

  • Se B vestas nigran ĉapelon same bone, C povas tuj diri ke li vestas blankan ĉapelon post rigardo je la du nigraj ĉapeloj antaŭ li.
  • Se B ne vestas nigran ĉapelon, C estos ne kapabla diri la koloron de lia ĉapelo (pro tio ke antaŭ li estas nigra kaj blanka). De ĉi tie, B povas konkludi de nigra ĉapelo de A kaj respondo de C ke li (B) ne vestas nigran ĉapelon (alie la pli supra situacio estos okazas) kaj pro tio vestas blankan ĉapelon.

Ĉi tiu pro tio demonstras ke A devas ne vesti nigran ĉapelon.

Tri-ĉapela varianto[redakti | redakti fonton]

En ĉi tiu varianto estas 3 arestitoj kaj 3 ĉapeloj. Al ĉiu arestito estas donita ĉapelo de hazarda koloro, ruĝa aŭ blua, egalprobable kaj sendepende por ĉiu arestito. Ĉiu persono povas vidi la ĉapelojn de du aliaj, sed ne sian posedan. Laŭ komando, samtempe, ĉiu el ili devas diri konjekton pri sia poseda ĉapela koloro aŭ silenti. Ili venkas kaj liberiĝas se almenaŭ unu persono konjektas ĝuste kaj neniu konjektas malĝuste, silento estas nek ĝusta nek malĝusta.

Ĉi tiu enigmo ne havas 100% venkan strategion, tiel la demando estas: kio estas la plej bona strategio? Kiu strategio donas la plej grandan probablon de venko?

Se konsideri kolorojn de ĉapeloj kiel bitoj, ĉi tiu problemo havas iujn gravajn aplikojn en kodoteorio.

Solvaĵo[redakti | redakti fonton]

75% venka probablo estas ebla. Ĉiu arestito, se vidas ke la aliaj du havas saman koloron, devas diri la kontraŭan koloron. Se li vidas ke la aliaj du havas malsamajn kolorojn, li devas silenti. Ĉi tiu strategio venkas en ĉiu okazo krom se ĉiuj tri arestitoj havas ĉapelojn de la sama koloro, tiel el 8 eblaj egalprobablaj okazoj (BBB, BBR, BRB, BRR, RBB, RBR, RRB, RRR) ĝi malvenkas en 2 okazoj (BBB, RRR) kaj venkas en ceteraj 6 okazoj.

La solvaĵo fidas je sendependeco de koloroj de la ĉapeloj de apartaj arestitoj. Aliokaze, la 8 eblaj kombinaĵoj de koloroj povas esti ne egalprobablaj. Se la okazoj BBB, RRR estas sufiĉe pli verŝajnaj, la alia strategio povas esti pli bona.

Dek-ĉapela varianto[redakti | redakti fonton]

En ĉi tiu varianto estas 10 arestitoj kaj 10 ĉapeloj. Al ĉiu arestito estas donita ĉapelo de hazarda koloro, ruĝa aŭ blua, egalprobable. Sed la kvanto de ĉapeloj de ĉiu koloro estas ne sciata al la arestitoj. La arestitoj estas liniitaj tiel kie ĉiu povas vidi la ĉapelojn antaŭ lin sed ne malantaŭ. Startante de la arestito en la malantaŭo de la linio kaj laŭ la ordo antaŭen, ili devas ĉiu, laŭvice, diri nur unu vorton kiu devas esti "ruĝa" aŭ "blua". Se la vorto de ulo koincidas kun lia ĉapela koloro, do li estos liberigita; se ne, li estos ekzekutita.

Kompleza gardisto avertas ilin pri ĉi tiu provo je unu horo antaŭe kaj diras al ili ke ili povas formuli planon laŭ kiu sekvante la interkonsentitajn regulojn, 9 el la 10 arestitoj povos certe liberiĝi, kaj 1 havos 50/50 ŝancon liberiĝi. Kiu estas la plano?

Solvaĵo[redakti | redakti fonton]

La arestitoj povas uzi duuman kodon kie ĉiu blua ĉapelo = 0 kaj ĉiu ruĝa ĉapelo = 1. La arestito en la dorso de la linio adicias ĉiujn valorojn kaj se la sumo estas para li diras "blua" (blua estante 0 kaj pro tio para) kaj se la sumo estas nepara li diras "ruĝa". Ĉi tiu arestito havas 50/50 ŝancon de havo de la ĉapela koloro kiun li diris. Sed ĉiu sekva arestito povas kalkuli lian posedan koloron per adiciado de la ĉapeloj antaŭ li kaj malantaŭ li post aŭdo de la respondoj ekde la dua, kaj komparo de ĝi al la komenca respondo donita per la arestito en la malantaŭo de la linio. La tuteca kvanto de ruĝa ĉapeloj devas esti para aŭ nepara nombro kongruanta la komencan paran aŭ neparan respondon donitan per la arestito en malantaŭo.

Malsimile al la antaŭa enigmo, ĉi tie la solvaĵo ne fidas je sendependeco de koloroj de la ĉapeloj de apartaj arestitoj. Malgraŭ ajna dependeco, ĉi tiu strategio donas 50/50 ŝancon por la malantaŭa arestito, kaj certan liberigon por la ceteraj. Tamen en okazo de dependeco de koloroj, povas ekzisti la alia, pli bona strategio.

Eksteraj ligiloj[redakti | redakti fonton]