Euler
ExamplesDas Rätsel findet man in
Euler und Gauß geraten in die Hölle. Der Teufel verspricht, sie freizulassen, wenn sie folgendes Rätsel lösen: Er denkt sich zwei Zahlen zwischen 2 und 99 aus und gibt Euler (P) das Produkt und Gauß (S) die Summe. Sie dürfen sich nicht über die Zahlen absprechen, müssen aber die Zahlen herausbekommen.
Es entspannt sich folgender Dialog.
P: "Ich weiß es nicht."
S: "Das wusste ich schon."
P: "Jetzt weiß ich die Zahlen!"
S: "Jetzt weiß ich sie auch!"
Welche dummen Zahlen hat Lucifer ausgesucht, so dass die beiden auf diese Art die Zahlen herausfinden konnten?
Die Lösung in Euler ist eine spannende Herausforderung.
Wir erzeugen dazu Vektoren p und q, so dass p[i], q[i] alle möglichen Kombinationen von Zahlen durchläuft. Das ist natürlich mit einem kleinen Programm sehr einfach.
>function pq () ...
p=[]; q=[];
for i=2 to 99
for j=2 to i
p=p|j; q=q|i;
end;
end;
return {p,q}
endfunction
>{p,q}=pq();
Hier sind die ersten 11 Kombinationen.
>(p'|q')[1:11]
2 2
2 3
3 3
2 4
3 4
4 4
2 5
3 5
4 5
5 5
2 6
Für das Folgende schreiben wir uns eine Funktion, die die Indizes von Elementen aus einen Vektor aussondert, die nur einmal vorkommen.
>function isonce(v) := nonzeros(getmultiplicities(v,v)==1);
Es ist offenbar so, dass die Aussage von P "Ich weiß es nicht" bedeutet, dass das Produkt, das er hat, mehrmals unter allen Produkten vorkommt.
Wir nennen die Index-Liste der Zahlen, bei denen P nichts weiß, PW = "P weiß".
>PW=isonce(p*q);
Wir drucken uns eine Liste von Produkten, bei denen P nicht weiß, wie die Zahlen heißen.
>unique((p*q)[PW]); %[1:20]
[4, 6, 8, 9, 10, 14, 15, 21, 22, 25, 26, 27, 33, 34, 35, 38, 39, 46, 49, 51]
Man beachte dass 8 darin vorkommt. Die Zahlen können dann nur 2 und 4 sein. Ansonsten kommen Produkte von Primzahlen vor.
Wir drucken uns die ersten 10 Elemente der Liste von Kombinationen, bei denen P die Antwort gewusst hätte.
>(p'|q')[PW][1:10]
2 2
2 3
3 3
2 4
2 5
3 5
5 5
2 7
3 7
5 7
S sagt ja nun: "Das war mir klar."
Das bedeutet, dass seine Summe p+q nicht in den Summen vorkommt, für die P eine Antwort gewusst hätte. Wir müssen also nur alle Summen p+q aussondern, die nicht unter den Summen (p+q)[PW] vorkommen.
Dazu schreiben wir eine Hilfsfunktion.
>function notin(v,x) := nonzeros(indexof(v,x)==0);
Nun können wir die Indizes aussondern, für die S klar war, dass P das Ergebnis nicht wissen konnte. Wir nennen das Ergebnis SWMK = "S - War mir klar".
>SWMK=notin((p+q)[PW],p+q);
Es bleiben nicht viele Summen übrig.
>unique((p+q)[SWMK])
[11, 17, 23, 27, 29, 35, 37, 41, 47, 53]
Nun sagt P: "Jetzt weiß ich es!"
Das bedeutet, dass P ein Produkt hat, das nur auf eine Weise als p*q geschrieben werden kann, so dass p+q in den noch verfügbaren Summen vorkommt.
Dazu müssen wir nur unter allen p[i], q[i] mit korrekter Summe diejenigen aussondern, deren Produkt einmalig ist. Das Ergebnis zeißt PWJ = "P weiß jetzt".
>PWJ=SWMK[isonce((p*q)[SWMK])];
Es sind überraschend viele Kombinationen.
>(p'|q')[PWJ]
Real 86 x 2 matrix
4 7
3 8
2 9
4 13
10 13
13 14
7 16
11 16
13 16
10 17
12 17
9 18
11 18
17 18
4 19
8 19
10 19
16 19
7 20
17 20
...
Die schärfste Selektion ergibt sich nun, weil S sagt: "Nun weiß ich es auch!"
Analog dem vorigen Vorgehen bedeutet dass, dass die Summe von S nur zu einem Paar p[i], q[i] gehört, das noch in der Liste vorkommt. Es ist hat die Nummer 69.
>SWJ=PWJ[isonce((p+q)[PWJ])]
69
Hier ist die Lösung.
>p[SWJ]|q[SWJ]
[4, 13]