Mathe Profis gesucht!?
Wer kann die folgende Knobelaufgabe lösen, ich sitze schon ewig dran, komme aber nicht weiter:
Auf einem Tisch liegen n Steine, wobei n eine gerade Zahl ist. Die Spieler A und B nehmen abwechselnd Steine vom Tisch. Der Spieler, der am Zug ist, nimmt dabei jeweils entweder genau ein Drittel, genau die Hälfte oder genau zwei Drittel der Steine weg. Wenn dies nicht möglich ist, hat er verloren, und der andere Spieler ist Gewinner. Spieler A beginnt.
Für welche Zahlen n kann Spieler A und für welche Zahlen n kann Spieler B den Sieg erzwingen?
Vielen Dank schon einmal für alle die antworten :)
Aus welchem Wettbewerb ist die Aufgabe?
Wie meinst du das?
ob es matheolympiade oder ähnliches ist
Landeswettbewerb Mathematik
3 Antworten
Ein Spieler verliert, wenn die Restmenge an Steinen weder durch 2 noch durch 3 teilbar ist, denn dann können weder 1/2, 1/3 oder 2/3 der Steine entnommen werden. Für die Restmenge an Steinen, mit der Spieler B verliert, gibt es deshalb folgende Möglichkeiten:
r = (1 + 6*k) oder s = (5 + 6*k) mit k = 0,1,2,3,...
Man beachte, dass es in Abhängigkeit der Startmenge unendlich viele Möglichkeiten von restlichen Steinen r oder s gibt. Auch mit z.B. 6001 oder 6005 Steinen hat B verloren.
Weil A vorher am Zug war, muss die Menge davor um den Faktor 2 oder 3 oder 3/2 grösser gewesen sein, ansonsten hätte A keinen Zug machen können. Deshalb ergibt sich für die Anzahl der Steine in den Zügen davor folgende allgemeine Formel ({r,s} meint r oder s):
{r,s} * 2^m * 3^n * 3/2^p
m,n,p € {0,N}, (m+n+p) > 0
Die Potenzen von 3/2 kann man eliminieren:
{r,s} * 2^(m-p) * 3^(n+p)
Offensichtlich muss (2^(m-p) * 3^(n+p)) ganzzahlig sein, denn sonst wäre die Anzahl der Steine nicht ganzzahlig. Das ist der Fall, falls (m-p) >= 0 gilt. Man kann deshalb die Formel auch so schreiben:
{r,s} * 2^m * 3^n
m,n € {0,N}; (m+n) > 0
###
Nun stellt sich die Frage mit welcher Startmenge A den Sieg erzwingen kann. Dazu lässt man die Potenzen von 3 erst mal weg.
{r,s} * 2^m
m € N
Mit jedem Zug kann die verbleibende Menge an Steinen nur halbiert werden, und am Ende bleibt für B die Restmenge r oder s übrig.
(m ungerade) und (A beginnt) --> wird A sicher gewinnen.
(m gerade) und (A beginnt) --> wird A sicher verlieren.
Diesen Zusammenhang kann man sich an einigen Beispielen leicht verdeutlichen.
###
Nun nimmt man Potenzen von 3 hinzu. Angenommen die Anzahl der Steine beträgt beim Zug Nummern i
a(i) = {r,s} * 2^m * 3^n
Ein Spieler kann diese Menge wie folgt reduzieren:
(i) 1/2 weg: a(i+1) = a(i) - 1/2 * a(i) = 1/2 * a(i) = {r,s} * 2^(m-1) * 3^n
(ii) 1/3 weg: a(i+1) = a(i) - 1/3 * a(i) = 2/3 * a(i) = {r,s} * 2^(m+1) * 3^(n-1)
(iii) 2/3 weg: a(i+1) = a(i) - 2/3 * a(i) = 1/3 * a(i) = {r,s} * 2^m * 3^(n-1)
Aus der Betrachtung zuvor haben wir bereits gelernt, dass auch die Anzahl der noch möglichen Züge eine Rolle spielt, um B verlieren zu lassen.
Nimmt man Potenzen von 3 hinzu, kann der Gegenspieler die Anzahl der restlichen Züge beeinflussen, dann aus (n+m) möglichen Zügen bei Spielstand a(i) werden:
im Fall (i) m+n-1 (ein möglicher Zug weniger)
im Fall (ii) m+n (mögliche Züge unverändert)
im Fall (iIi) m+n-1 (ein möglicher Zug weniger)
Der Gegenspieler kann also durch strategisches Handeln im Fall von (ii) den sicheren Gewinn für A zunichte machen.
###
Meiner Ansicht nach verbleiben deshalb nur folgende Startwerte, wenn A beginnt und sicher gewinnen will
{r,s} * 2^m, m € N ungerade
####
Eventuell habe ich die Aufgabe falsch verstanden. Man befindet sich oft in einer Sackgasse und findet nicht mehr raus.
Vielen Dank!! Mich würde noch interessieren wie du auf die erste Formel gekommen bist.
Alle Zahlen, die nicht durch 2 oder 3 teilbar sind: 1,5,7,11,13,17,19,23,25,29,31 ...
Die 1,7,13,19,25,... weisen alle eine Differenz von 6 auf.
Die 5,11,17,23,29, ebenfalls.
Bei z.B. S= 8, woher soll ich dann wissen, ob es eine der Formeln entspricht? Also was ist k, n und m?
Ja, das Problem ist dann halt wieder, dass man z.B. 6 oder 12 weglässt, für die A aber auch den Sieg erzwingen kann..
Wenn du schon ewig dran sitzt musst du dir ja bereits schon irgendwelche Überlegungen/Notizen/Rechnungen, Sonstiges, gemacht haben.
Wie wäre es wenn uns davon mal einige gibst und man sich dann gemeinsam hinarbeitet anstatt das dir hier einer einfach die Lösung hinschreibt.
Besonders schwierig ist die Aufgabe erstmal nicht, da du sie ja sehr leicht mit Münzen oder anderen Gegenständen "nachspielen" kannst und so relativ schnell erste Ideen/Strategien entwickeln kannst, wenn es dir auf dem Blatt Papier zunächst zu schwierig ist.
Also, ich habe zunächst alle Zahlen ausprobiert:
Bei 2 gewinnt A
Bei 4 B
6-14A
16-20 wieder B
Das Problem ist dass ich keinen Zusammenhang finde...
Auch ist es so, dass bei allen Potenzen von 4 also z.B. 4³,4⁴... immer abwechselnd A und B gewonnen.
...immer abwechselnd... bei gerader Potenz der eine, bei ungerader Potenz der andere. könnte das die Lösung sein?
Teil der Lösung, denn was ist mit den anderen geraden Zahlen, die nicht Potenz von 2 sind?
Spieler A gewinnt aufjedenfall immer wenn n das doppelte einer Primzahl ist und Er genau die Hälfte nimmt. Spieler B gewinnt wenn x²=n aber n nicht das vielfache einer Primzahl ist. ( x kann jede beliebige Zahl sein)
Hoffe das ist richtig... hast du mittlerweile die Lösung?
Danke, aber was ist mit den anderen geraden Zahlen z.B. 6, 10,12,14...?