Views: ²⁶¹⁴

Einsteins gåta

Fem hus i fem olika färger ligger på rad. I varje hus bor en ägare med en nationalitet som avviker från de andra husägarnas. Husägarna tycker alla om olika drycker, har olika favoritspel och har olika husdjur. Ingen husägare kan dricka samma sak, spela samma spel eller ha samma husdjur som någon av de andra.

Britten bor i det röda huset.
Svensken har en hund som husdjur.
Dansken dricker te.
Det gröna huset ligger till vänster om det vita huset.
Ägaren till det gröna huset dricker kaffe.
Den som spelar schack har en fågel.
Ägaren till det gula huset spelar go.
Mannen i huset i mitten dricker mjölk.
Norrmannen bor i det första huset.
Mannen som spelar bridge bor granne med den som har en katt.
Mannen som äger en häst bor granne med mannen som spelar go.
Den som spelar canasta dricker öl.
Tysken spelar backgammon.
Norrmannen bor bredvid det blå huset.
Mannen som spelar bridge har en granne som dricker vatten.

Vem har en fisk som hjusdjur?

Lösning

Vi skapar en lista $X$ med alla möjliga sextupler på formen (nationalitet, husnummer, husfärg, spel, dryck, husdjir). En lösning är fem sådana element vilka uppfyller kriterierna i problemet samt där varje komponent är unik.

A = ['britt', 'svensk', 'dansk', 'norsk', 'tysk']
B = [1..5]
C = [u'röd', u'vit', u'grön', u'gul', u'blå']
D = ['schack', 'go', 'bridge', 'canasta', 'backgammon']
E = [u'te', u'kaffe', u'mjölk', u'öl', u'vatten']
F = [u'hund', u'katt', u'fågel', u'häst', u'fisk']

Mängden $X$ innehåller alla möjliga sextupler.

X = [(a, b, c, d, e, f) for a in A for b in B for c in C for d in D for e in E for f in F]

Antal element i $X$ :

len(X)

15625

Mängden $X$ innehåller alltså $5^6$ olika sextupler. Antal möjliga sätt att välja fem element ur $X$ , utan återläggning och utan hänsyn till ordningen ges av $\binom{5^6}{5}$ .

binomial(5^6, 5)

7756055513916018750

Att undersöka var och en av dessa kombinationer skulle ta ett tag. Istället ugår vi från kriterierna och sållar bort de element i $X$ som inte kan ingå i en lösning.

Britten bor i det röda huset

Låt $P(x)$ och $Q(x)$ vara påståenderna '' $x$ är britt'' respektive '' $x$ bor i det röda huset''. Vi vill plocka bort från $X$ de individer (sextupel) som uppfyller $(P(x) \land \neg Q(x)) \lor (\neg P(x) \land Q(x)),$ det vill säga de '' $x$ som är britter och bor i ett hus som inte är rött eller de $x$ som inte är britter och som bor i ett rött hus''. Med andra ord ska vi behålla de $x$ som uppfyller negationen av ovanstående logiska uttryck. Från de Morgans lagar följer att $\neg((P(x) \land \neg Q(x)) \lor (\neg P(x) \land Q(x))) \qquad\Leftrightarrow\qquad (\neg P(x) \lor Q(x)) \land (P(x) \lor \neg Q(x)).$ Nationalitet och husfärg finner vi på första (index 0) respektive tredje (index 2) positionen i $x$ . Flera av ledtrådarna har samma uppbyggnad.

X = [x for x in X if (x[0] != 'britt' or x[2] == u'röd') and (x[0] == 'britt' or x[2] != u'röd')]
len(X)  # antal element kvar i X

10625

Svensken har en hund som husdjur

X = [x for x in X if (x[0] != 'svensk' or x[5] == u'hund') and (x[0] == 'svensk' or x[5] != u'hund')]
len(X)

7000

Dansken dricker te

X = [x for x in X if (x[0] != 'dansk' or x[4] == u'te') and (x[0] == 'dansk' or x[4] != u'te')]
len(X)

4400

Det gröna huset ligger till vänster om det vita huset

Det vänstra huset har nummer 1 och högra har nummer 5. Det betyder att det gröna hustet kan inte vara nummer 5 och det vita kan inte vara nummer 1. Vi ska således ta bort dels de $x \in X$ vars hus är gröna med nummer 5 och dels de $x \in X$ vars hus är vita och har nummer 1. Negationen av ''grönt hus och nummer 5'' är ''inte grönt hus eller inte nummer 5''.

X = [x for x in X if x[2] != u'grön' or x[1] != 5]
X = [x for x in X if x[2] != u'vit' or x[1] != 1]
len(X)

4000

Notera att vi är inte har utrett denna ledtråd i sin helhet. Vi får fyra olika delfall. En för varje möjligt husnummer för det gröna huset och i varje sådant delfall är husnumret för det vita huset fixt. Vi väntar dock med att studera dessa olika fall efter att vi rensat bort fler element ur $X$ , eftersom vi då förhoppningsvis kan utesluta vissa av delfallen.

Ägaren till det gröna huset dricker kaffe

X = [x for x in X if (x[2] != u'grön' or x[4] == u'kaffe') and (x[2] == u'grön' or x[4] != u'kaffe')]
len(X)

2650

Den som spelar schack har en fågel

X = [x for x in X if (x[3] != 'schack' or x[5] == u'fågel') and (x[3] == 'schack' or x[5] != u'fågel')]
len(X)

1757

Ägaren till det gula huset spelar go

X = [x for x in X if (x[2] != u'gul' or x[3] == 'go') and (x[2] == u'gul' or x[3] != 'go')]
len(X)

1073

Mannen i huset i mitten dricker mjölk

X = [x for x in X if (x[1] != 3 or x[4] == u'mjölk') and (x[1] == 3 or x[4] != u'mjölk')]
len(X)

672

Norrmannen bor i det första huset

X = [x for x in X if (x[0] != 'norsk' or x[1] == 1) and (x[0] == 'norsk' or x[1] != 1)]
len(X)

411

Mannen som spelar bridge bor granne med den som har en katt

Vi kan med säkerhet ta bort alla element i $X$ vars fjärde och sjätte koordinat är 'bridge' respektive 'katt'. Med andra ord ska vi behålla de element vars fjärde koordinat är inte 'bridge' eller sjätte koordinat är inte 'katt'. Vi utreder dock inte denna ledtråd fullt ut nu, utan väntar tills det är färre element i $X$ .

X = [x for x in X if (x[3] != 'bridge') or (x[5] != u'katt')]
len(X)

379

Mannen som äger en häst bor granne med mannen som spelar go

Liknande resonemang som i föregående ledtråd. Även denna utreds här endast delvis.

X = [x for x in X if (x[5] != u'häst') or (x[3] != 'go')]
len(X)

367

Den som spelar canasta dricker öl

X = [x for x in X if (x[3] != 'canasta' or x[4] == u'öl') and (x[3] == 'canasta' or x[4] != u'öl')]
len(X)

208

Tysken spelar backgammon

X = [x for x in X if (x[0] != 'tysk' or x[3] == 'backgammon') and (x[0] == 'tysk' or x[3] != 'backgammon')]
len(X)

106

Norrmannen bor bredvid det blå huset

X = [x for x in X if (x[0] != 'norsk') or (x[2] != u'blå')]
len(X)

100

Vi vet redan att norrmannen bor i det första huset. Med andra ord är det blå huset det andra huset.

X = [x for x in X if (x[1] != 2 or x[2] == u'blå') and (x[1] == 2 or x[2] != u'blå')]
len(X)

59

Mannen som spelar bridge har en granne som dricker vatten

Detta är andra ledtråden om bridgespelaren. Även denna utreds inte här fullt ut. Troligtvis kan vi kombinera dessa när vi slutför analysen.

X = [x for x in X if (x[3] != 'bridge') or (x[4] != u'vatten')]
len(X)

52

Slutför: Det gröna huset ligger till vänster om det vita huset

Om det gröna huset har nummer $k$ , är det då möjligt att det vita huset har nummer $k + 1$ ? Om det finns ett grönt hus med nummer $k$ räknar vi antal vita hus med nummer $k + 1$ .

for k in [1..4] :
    if len([x for x in X if x[2] == u'grön' and x[1] == k]) > 0 :
        if len([x for x in X if x[2] == u'vit' and x[1] == k + 1]) > 0 :
            print u'Grönt hus kan vara nummer', k

Grönt hus kan vara nummer 4

Vi fann endast ett alterantiv, nämligen att det göna huset har nummer 4. Det betyder att det vita huset har nummer 5.

X = [x for x in X if (x[1] != 4 or x[2] == u'grön') and (x[1] == 4 or x[2] != u'grön')]
X = [x for x in X if (x[1] != 5 or x[2] == u'vit') and (x[1] == 5 or x[2] != u'vit')]
len(X)

24

Så här lång vet vi att det blåa, gröna och vita huset är det andra, fjärde respektive femta huset. Är det möjligt att det röda huset har nummer 1?

len([x for x in X if x[1] == 1 and x[2] == u'röd'])

0

Nej, det röda huset kan inte vara det första huset. Det ger att det gula huset är första huset och det röda huset är det tredje huset.

X = [x for x in X if (x[1] != 1 or x[2] == u'gul') and (x[1] == 1 or x[2] != u'gul')]
X = [x for x in X if (x[1] != 3 or x[2] == u'röd') and (x[1] == 3 or x[2] != u'röd')]
len(X)

23

Slutför: Mannen som äger en häst bor granne med mannen som spelar go

for k in [1..5] :
    if len([x for x in X if x[5] == u'häst' and x[1] == k]) > 0 :
        if len([x for x in X if x[3] == 'go' and x[1] == k - 1]) > 0 :
            print U'Hästen kan finnas i hus', k, 'och go kanske spelas i hus', k - 1
        if len([x for x in X if x[3] == 'go' and x[1] == k + 1]) > 0 :
            print U'Hästen kan finnas i hus', k, 'och go kanske spelas i hus', k + 1

Hästen kan finnas i hus 2 och go kanske spelas i hus 1

X = [x for x in X if (x[5] != u'häst' or x[1] == 2) and (x[5] == u'häst' or x[1] != 2)]
X = [x for x in X if (x[1] != 1 or x[3] == 'go') and (x[1] == 1 or x[3] != 'go')]
len(X)

14

Slutför de sista två ledtrådarna

Vi har kvar att utreda i sin helhet följande två påståenden.

Mannen som spelar bridge bor granne med den som har en katt.
Mannen som spelar bridge har en granne som dricker vatten.

I vilka hus spelas det möjligvis bridge?

Set([x[1] for x in X if x[3] == 'bridge'])

{2, 3, 4, 5}

I vilka hus finns det möjligtvis en katt?

Set([x[1] for x in X if x[5] == u'katt'])

{1, 4, 5}

I vilka hus dricks det eventuellt vatten?

Set([x[1] for x in X if x[4] == u'vatten'])

{1, 2, 5}

I vilka hus finns det en katt och även dricks vatten?

Set([x[1] for x in X if x[4] == u'vatten' and x[5] == u'katt'])

{1, 5}

Det ger oss tre alternativ.

Bridge i hus 2, katten i hus 1 och vatten i hus 1.
Bridge i hus 3, katten i hus 4 och vatten i hus 2.
Bridge i hus 4, katten i hus 5 och vatten i hus 5.

Tänk på att katten och vattnet ska vara granne med bridge-huset samt katten och vattnet finns endast samtidigt i hus 1 eller 5.

Det betyder att vi till att börja med kan ta bort de fall då bridge spelas i femte huset.

X = [x for x in X if x[1] != 5 or x[3] != 'bridge']
len(X)

13

Vi definierar en funktion för en enkel naiv kontroll om det är möjligt att finna en lösning bland de resterande sextuplerna. Kontrollen går ut på att räkna antal olika nationaliteter, nummer, färger, spel, drycker och husdjur. Om antalet i samtliga fall är lika med 5, så kan det finnas en lösning.

def kontroll(X) :
    return all(map(lambda k : Set([x[k] for x in X]).cardinality() == 5, range(6)))

Vi undersöker de tre olika fallen var för sig genom att ta bort de sextupler som inte uppfyller aktuella villkor och använder sedan kontrollfunktionen för att undersöka om vi tog bort för mycket. Förhoppningsvis kan vi på så vis utesluta två av de tre fallen.

Fall 1: Bridge i hus 2, katten i hus 1 och vattnet i hus 1.

X1 = [x for x in X if (x[1] != 2 or x[3] == 'bridge') and (x[1] == 2 or x[3] != 'bridge')]
X1 = [x for x in X1 if (x[1] != 1 or x[5] == u'katt') and (x[1] == 1 or x[5] != u'katt')]
X1 = [x for x in X1 if (x[1] != 1 or x[4] == u'vatten') and (x[1] == 1 or x[4] != u'vatten')]
kontroll(X1)

True

Bridge i hus 3, katten i hus 4 och vattnet i hus 2.

X2 = [x for x in X if (x[1] != 3 or x[3] == 'bridge') and (x[1] == 3 or x[3] != 'bridge')]
X2 = [x for x in X2 if (x[1] != 4 or x[5] == u'katt') and (x[1] == 4 or x[5] != u'katt')]
X2 = [x for x in X2 if (x[1] != 2 or x[4] == u'vatten') and (x[1] == 2 or x[4] != u'vatten')]
kontroll(X2)

False

Bridge i hus 4, katten i hus 5 och vattnet i hus 5.

X3 = [x for x in X if (x[1] != 4 or x[3] == 'bridge') and (x[1] == 4 or x[3] != 'bridge')]
X3 = [x for x in X1 if (x[1] != 5 or x[5] == u'katt') and (x[1] == 5 or x[5] != u'katt')]
X3 = [x for x in X1 if (x[1] != 5 or x[4] == u'vatten') and (x[1] == 5 or x[4] != u'vatten')]
kontroll(X3)

False

Alltså är det endast första alternativet som är möjligt.

X = X1
len(X)

6

Vi är nästan klar! För vilken av nationaliteterna finns det en dubblett?

for n in A :
    print n.ljust(7), len([x[0] for x in X if x[0] == n])

britt   1
svensk  1
dansk   2
norsk   1
tysk    1

Vi behöver ta bort en dansk. I vilka hus bor dessa danskar?

[x[1] for x in X if x[0] == 'dansk']

[2, 5]

Vilka andra bor i det andra och femte huset?

[x[0] for x in X if x[1] == 2]
[x[0] for x in X if x[1] == 5]

['dansk']
['svensk', 'dansk']

Aha! Dansken i femte huset ska bort eftersom den enda svensken bor i det femte huset.

X = [x for x in X if x[1] != 5 or x[0] != 'dansk']
len(X)

5

Skriv ut de återstående sextuplerna.

for t in X :
    print t[0].ljust(7), t[1], '',t[2].ljust(5), t[3].ljust(11), t[4].ljust(7), t[5]

britt   3  röd   schack      mjölk   fågel
svensk  5  vit   canasta     öl      hund
dansk   2  blå   bridge      te      häst
norsk   1  gul   go          vatten  katt
tysk    4  grön  backgammon  kaffe   fisk

Vi har löst Einsteins gåta. Det är tysken som har en fisk som husdjur.