De Moordenaar Op De Hielen

[PeterPan]

Een van de 8 leden van een bende heeft een moord gepleegd.

Twee naburige sheriffs hebben de zaak onderzocht, en zijn zo ver gevorderd, dat zij beiden het aantal verdachten tot 2 hebben weten te reduceren. Door hun loslippigheid is dat bij iedereen bekend.

Nu bellen ze elkaar op. Als blijkt dat zij precies 1 gemeenschappelijke verdachte hebben, dan zal ie worden gearresteerd.

Van de andere kant, als de bende weet wie van hen de dader is zal ie onmiddellijk worden geexecuteerd, hetgeen de sheriffs te allen tijde willen voorkomen.

Het is alom bekend dat de bendeleden de telefoon van de sheriffs afluisteren.

Hoe kunnen de sheriffs er in dat telefoongesprek achter komen wie de (eventueel) gemeenschappelijke verdachte is zonder het aan de bende te verraden.

[eendavid]

de arrestatiesheriff vraagt aan de vertelsheriff wie zijn 2 verdachten zijn. De arrestatiesherrif kan dan (eventueel) de arrestatie uitvoeren.

Of executeert de bende dan beide verdachten?

[jhnbk]

"Hoe kunnen de sheriffs er in dat telefoongesprek"

dus klopt volgens mij je antwoord niet eendavid

[wetenschapper_in_leer]

1 sheriff zegt 1 van zijn verdachten. als de andere deze ook als verdachte heeft dan weet hij het en zegt hij om de dieven te misleiden dat hij het niet weet en weg moet. dit is een signaal voor de andere dat het deze is. als hij de verdachte niet heeft dan is het de andere verdachte die de 1e weet, de 1e zegt zijn 2e verdachte en de 2e sheriff zegt dat hij het niet weet. zo kennen ze altijd beide verdachten en hebben de dieven twijfel tussen 2 of meer

[PeterPan]

1 sheriff zegt 1 van zijn verdachten. als de andere deze ook als verdachte heeft dan weet hij het en zegt hij om de dieven te misleiden dat hij het niet weet en weg moet. dit is een signaal voor de andere dat het deze is.

Deze code zouden de sheriffs met elkaar willen afspreken, maar hoe spreken ze dat met elkaar af, als ze daarvoor slechts dit afgeluisterde gesprek hebben?

[wetenschapper_in_leer]

wel... ze kunnen om de beurt een van diegene zeggen die het niet is, en als 1 van de 2 verdachten door de andere genoemd is weet deze het, maar als we dit in het langste scenario bekijke, dus: 1 van de verdachten wordt pas op het laatste gezegt, dan weten de dieven het ook. dus het is geen volledige oplossing....

[PeterPan]

Het is een heel gepuzzel, maar hier is een oplossing:

Stel de bendeleden heten

\(\{ad,ben,cor,dik,eef,ger,han,iep\}\)

Sheriff 1 heeft als verdachten

\(\{ad,ben\}\)

en sheriff 2

\(\{ad,cor\}\)

Sheriff 1 legt aan sheriff 2 telkens uit wat hij moet doen. En wat dat is blijkt uit de volgende reacties.

Sheriff 1 zegt dat zijn verdachtenlijstje één van de volgende 4 paren is:

\(\{ad,ben\},\{cor,dik\},\{eef,ger\},\{han,iep\}\)

Sheriff 2 verdeelt dit in 2 delen, zodat in één daarvan zijn 2 verdachten zitten: Hij zegt

deel 1

\(\{ad,ben\},\{cor,dik\}\)

en deel 2

\(\{eef,ger\},\{han,iep\}\)

Sheriff 1 kiest nu uit deze 2 delen elk een paar, zodat zijn verdachtenpaar erbij zit,

dus hij zegt bijvoorbeeld

\(\{ad,ben\},\{eef,ger\}\)

Nu kent sheriff 2 de dader!

Sheriff 2 neemt uit beide paren 1 element, waaronder de dader, dus hij zegt bijvoorbeeld

\(\ad\)

of

\(eef\)

.

Nu weet ook sheriff 1 wie de dader is.

De bendeleden weten niet of het

\(\ad\)

of

\(eef\)

is.

Het is een heel gepuzzel, maar hier is een oplossing:

Stel de bendeleden heten

\(\{ad,ben,cor,dik,eef,ger,han,iep\}\)

Sheriff 1 heeft als verdachten

\(\{ad,ben\}\)

en sheriff 2

\(\{ad,cor\}\)

Sheriff 1 legt aan sheriff 2 telkens uit wat hij moet doen. En wat dat is blijkt uit de volgende reacties.

Sheriff 1 zegt dat zijn verdachtenlijstje één van de volgende 4 paren is:

\(\{ad,ben\},\{cor,dik\},\{eef,ger\},\{han,iep\}\)

Sheriff 2 verdeelt dit in 2 delen, zodat in één daarvan zijn 2 verdachten zitten: Hij zegt

deel 1

\(\{ad,ben\},\{cor,dik\}\)

en deel 2

\(\{eef,ger\},\{han,iep\}\)

Sheriff 1 kiest nu uit deze 2 delen elk een paar, zodat zijn verdachtenpaar erbij zit,

dus hij zegt bijvoorbeeld

\(\{ad,ben\},\{eef,ger\}\)

Nu kent sheriff 2 de dader!

Sheriff 2 neemt uit beide paren 1 element, waaronder de dader, dus hij zegt bijvoorbeeld

\(\ad\)

of

\(eef\)

.

Nu weet ook sheriff 1 wie de dader is.

De bendeleden weten niet of het

\(\ad\)

of

\(eef\)

is.

[eendavid]

het geval dat ze geen gemeenschappelijke verdachte hebben niet ingecalculeerd.

stel dat sherrif 2 {cor,eef} als verdachten heeft.

deel 1 {cor,dik} {eef ger}; deel 2 {ad, ben} en {han,iep}

sherrif 1 kan dan {ad,ben} en {cor,dik} kiezen.

sherrif 2 is in de overtuiging dat hij cor mag arresteren.

hij kiest cor en ben. sherrif 1 is in de overtuiging dat hij ben mag arresteren.

kortom, op de arrestatie wordt het een volledige puinhoop.

[PeterPan]

Het is een heel gepuzzel, maar hier is een oplossing:

Stel de bendeleden heten

\(\{ad,ben,cor,dik,eef,ger,han,iep\}\)

Sheriff 1 heeft als verdachten

\(\{ad,ben\}\)

en sheriff 2

\(\{ad,cor\}\)

Sheriff 1 legt aan sheriff 2 telkens uit wat hij moet doen. En wat dat is blijkt uit de volgende reacties.

Sheriff 1 zegt dat zijn verdachtenlijstje één van de volgende 4 paren is:

\(\{ad,ben\},\{cor,dik\},\{eef,ger\},\{han,iep\}\)

Sheriff 2 verdeelt dit in 2 delen, zodat in één daarvan zijn 2 verdachten zitten: Hij zegt

deel 1

\(\{ad,ben\},\{cor,dik\}\)

en deel 2

\(\{eef,ger\},\{han,iep\}\)

Sheriff 1 kiest nu uit deze 2 delen elk een paar, zodat zijn verdachtenpaar erbij zit,

dus hij zegt bijvoorbeeld

\(\{ad,ben\},\{eef,ger\}\)

Nu kent sheriff 2 de dader!

Sheriff 2 neemt uit beide paren 1 element, waaronder de dader, dus hij zegt bijvoorbeeld

\(ad\)

of

\(eef\)

.

Nu weet ook sheriff 1 wie de dader is.

De bendeleden weten niet of het

\(ad\)

of

\(eef\)

is.

[PeterPan]

het geval dat ze geen gemeenschappelijke verdachte hebben niet ingecalculeerd.

stel dat sherrif 2 {cor,eef} als verdachten heeft.

deel 1 {cor,dik} {eef ger}; deel 2 {ad, ben} en {han,iep}

sherrif 1 kan dan {ad,ben} en {cor,dik} kiezen.

sherrif 2 is in de overtuiging dat hij cor mag arresteren.

hij kiest cor en ben. sherrif 1 is in de overtuiging dat hij ben mag arresteren.

kortom, op de arrestatie wordt het een volledige puinhoop.

Dan hebben de sheriffs hun werk niet goed gedaan, en daar mogen we niet van uitgaan.

Stel namelijk dat ze beiden 1 gemeenschappelijke dader hebben, en die executeren.

Later blijkt dat ze beiden zich vergist hebben.

Dan sneuvelt een onschuldige.

Kortom, als je er van uit gaat dat de sheriffs zich kunnen vergissen, dan mogen ze niet te werk gaan als in de opgave.

Gegeven het feit dat ze wel zo te werk gaan houdt derhalve impliciet in dat ze zich niet zullen vergissen.