Waage und 12 Kugeln, Lösung und Diskussion

Es gibt zwar schon eine Lösung zum Problem der Waage und der 12 Kugeln - aber dort steht praktisch nichts mathematisch Interessantes: Nicht, wie man die Lösung findet, nicht, welche weiteren ähnlichen Probleme man sich stellen kann ... ich versuche es hier, besser zu machen.

Wie schon in der Aufgabenstellung erwähnt, gibt es zwei Arten von Lösungen:

• Bei einigen ist der "Plan", welche Kugeln in den drei Wägungen auf der Waage platziert werden, fest - ich nenne sie "statische Lösungsverfahren".
• Bei anderen hängt die Auswahl der Kugeln, die man bei der zweiten und dritten Wägung auf die Waage legt, von den Ergebnissen der vorherigen Wägungen ab - "dynamische Lösungsverfahren".

Ich werde hier ein wenig von beiden Verfahren erklären (nicht nur "die Lösung vom Himmel fallen lassen"). Ich beginne einmal mit den dynamischen Verfahren.

Die erste Wägung - samt einem wichtigen Abschätzverfahren

Es ist klar, dass man bei jeder Wägung (egal ob statisches oder dynamisches Verfahren) immer links und rechts gleich viele Kugeln hinlegen muss (würde man das nicht tun, würde das Ergebnis davon abhängen, ob und wieviel die schwerere Kugel tatsächlich schwerer ist, oder die leichtere leichter - was man aber nicht weiß).

Daher kann jedes Verfahren nur damit beginnen, dass man links und rechts entweder

• je eine
• je zwei
• je drei
• je vier
• je fünf
• oder je sechs

Kugeln hinlegt. Welche Aufteilungen davon sind sinnvoll? Dazu kann man sich überlegen, dass die noch übrigen Wägungen immer alle möglichen Fälle, die noch nicht nicht ausgeschlossen sind, unterscheiden können müssen. Ganz am Anfang bedeutet das:

• Es gibt noch 24 mögliche Lösungen (es kann ja jede der 12 Kugeln die sein, die man finden muss; und sie kann zu leicht sein oder zu schwer).
• Jede Wägung kann genau drei Möglichkeiten unterscheiden - indem die Waage links nach unten geht, rechts nach unten geht oder im Gleichgeweicht bleibt. Mit drei Wägungen kann man also höchstens 3 * 3 * 3 = 3³ = 27 Möglichkeiten unterscheiden. Und weil 24 nicht mehr ist als 27, ist es überhaupt möglich, dass es eine Lösung gibt!

Mit diesem Wissen können wir überlegen, welche Aufteilung bei der ersten Wägung sinnvoll ist. Nehmen wir zuerst an, dass wir links und rechts je eine Kugel hinlegen - 10 Kugeln bleiben also neben der Waage liegen. Wenn die Waage nun im Gleichgewicht bleibt, dann wissen wir, dass eine der restlichen 10 Kugeln die gesuchte ist. Es gibt also noch 20 mögliche Lösungen (jede der 10 Kugeln kann leichter oder auch schwerer sein), wir haben aber nur noch zwei Wägungen zur Verfügung. Diese zwei Wägungen können aber nur 3² = 9 Fälle unterscheiden - daher kann es kein Lösungsverfahren geben, das mit 1+1 Kugeln beginnt!

Auch bei 2+2 und 3+3 Kugeln am Anfang geht es nicht (weil dann bei Gleichgewicht noch immer 8 Kugeln, also 16 mögliche Lösungen bzw. 6 Kugeln, also 12 Lösungen übrigbleiben, was jeweils größer als 9 ist). Wenn bei der ersten Wägung 4+4 Kugeln aufgelegt werden, dann bleiben 4 weitere auf der Seite, mit 8 Lösungsmöglichkeiten, was kleiner als 9 ist - also könnte damit eine Lösung erfolgreich sein. Wie sieht es mit 5+5 Kugeln aus? Bei Gleichgewicht geht sich alles aus (die 4 möglichen Lösungen der 2 auf der Seite liegenden Kugeln sind ja erst recht weniger als 9), aber nun haben wir ein Problem mit den 5+5 Kugeln: Nehmen wir an, die Waage senkt sich links - dann könnte entweder unter den 5 linken Kugeln die eine sein, die zu schwer ist; oder rechts befindet sich eine, die zu leicht ist. Das sind 5+5 Möglichkeiten, was mehr als 9 ist - daher können wir mit zwei Wägungen nicht mehr alle diese Fälle unterscheiden. Eine Aufteilung 5+5 führt also nicht immer zu einer Lösung, und erst recht nicht 6+6 (wo ja auf jeden Fall 12 Möglichkeiten übrigbleiben).

Wir wissen also: Bei der ersten Wägung müssen 4+4 Kugeln auf die Waage. Aber wir haben darüberhinaus ein Verfahren gefunden, mit dem wir grob abschätzen können, ob nach einer Wägung überhaupt noch die Lösung sicher gefunden werden kann!

Die zweite Wägung eines dynamischen Verfahrens

Die erste Wägung kann drei Ergebnisse haben:

1. Waage geht links herunter: Dann wissen wir, dass entweder unter den linken vier Kugeln die eine schwerere ist oder unter den rechten vier die eine leichtere.
2. Waage geht rechts herunter: Entweder ist unter den vier rechts die schwerere; oder links die leichtere.
3. Waage bleibt im Gleichgewicht: Unter den vier neben der Waage ist die abweichende.

Statt weiterhin so lange Texte zu schreiben, müssen wir das kürzer hinschreiben können - nach dem alten Mathematikerspruch: "Die richtige Notation ist die halbe Lösung". Ich verwende einmal die folgenden Buchstaben:

• Wenn eine Kugel nur mehr eine schwerere sein kann (aber vielleicht auch eine der 11 gleich schweren - ich nenne die "normal"), dann soll dafür der Buchstabe S stehen;
• wenn sie nur eine leichtere oder eine normale sein kann, dann steht dafür L;
• und wenn sie schwerer oder leichter oder normal sein kann, dann wird das mit X gekennzeichnet.
• Wenn eine Kugel schließlich sicher "normal" ist, dann wird sie mit N bezeichnet.

Die drei Möglichkeiten oben ergeben also:

1. SSSS + LLLL / NNNN (durch + trenne ich die beiden Gruppen, die auf der Waage liegen; nach dem / stehen die Kugeln, die neben der Waage liegen und die uns "gerade noch interessieren").
2. LLLL + SSSS / NNNN
3. NNNN + NNNN / XXXX

Wir kümmern uns einmal um den dritten Fall - er sieht irgendwie leichter aus, weil wir nur mehr vier Kugeln betrachten müssen ... von denen wir allerdings praktisch nichts wissen! Aber probieren wir einmal: Wir legen links zwei der X-Kugeln, rechts die zwei anderen. Dann haben wir folgende möglichen Ergebnisse:

1. links runter: SS + LL
2. rechts runter: LL + SS
3. Gleichgewicht: kann nicht sein (weil wir ja aus der ersten Wägung wissen, dass eine der vier die abweichende sein muss!).

Im ersten Fall gibt es noch immer vier mögliche Lösungen (eine der zwei S ist die schwerere; oder eine der beiden L ist die leichtere). Die eine letzte Wägung kann aber nur drei Möglichkeiten unterscheiden - damit ist die Aufteilung 2+2 nicht ok. Also dann 1+1, mit folgenden Ergebnissen:

1. links runter: S + L / NN
2. rechts runter: L + S / NN
3. Gleichgewicht: N + N / XX

Den ersten und zweiten Fall könnten wir lösen: Im ersten Fall müssen wir nur die S-Kugeln mit einer N-Kugel vergleichen - wenn Gleichgewicht, dann ist die (danebenliegende) L-Kugel die leichtere, wenn S-Kugel nach unten geht, ist sie die schwerere. Aber im dritten Fall bleiben mit den XX vier Möglichkeiten übrig, die wir wieder mit den drei möglichen Ergebnissen einer Wägung nicht lösen können.

Weder 1+1 noch 2+2 funktioniert also bei der zweiten Wägung - wir brauchen eine "schrägere Idee"!

Hier ist sie: 2+1! Das geht natürlich nicht direkt (siehe Erklärung ganz am Anfang), aber wir können rechts eine weitere N-Kugel dazulegen. Wir legen also hin: XX + XN / X (die vierte X liegt auf der Seite) und haben nur folgende Fälle:

1. links runter: SS + LN / N (entweder eine der schwereren zieht links runter; oder rechts ist die leichtere)
2. rechts runter: LL + SN / N
3. Gleichgewicht: NN + NN / X

Wir haben nur mehr eine Wägung frei - aber das könnte sich nun ausgehen!

Die dritte Wägung eines dynamischen Verfahrens nach NNNN+NNNN/XXXX - die "AAB-Konfiguration"

Der dritte Fall aus der vorherigen Wägung ist leicht: Wir vergleichen die danebenliegende Kugel (die ja sicher die gesuchte sein muss! - alle anderen sind nun als N bewiesen) mit einer beliebigen N-Kugel, mit folgenden Ergebnissen:

1. links runter: S + N --> die links verwogene ist die gesuchte, und sie ist schwerer.
2. rechts runter: L + N --> die links verwogene ist die gesuchte, und sie ist leichter.
3. Gleichgewicht: unmöglich

Was tun wir mit den anderen beiden Fällen aus der vorherigen Wägung? Aus der ersten Wägung erhalten wir drei Kugeln, von denen wir wissen, dass sie SSL sind: Also entweder ist die erste oder die zweite die zu schwere, oder die dritte die zu leichte. Es gibt mehrere Arten, mit einer Wägung die richtige zu finden - hier ist eine: Man legt die beiden S auf die Waage und erhält dann:

1. links runter: S + N --> die linke ist die gesuchte, und sie ist schwerer.
2. rechts runter: N + S --> die rechte ist die gesuchte, und sie ist schwerer.
3. Gleichgewicht: N + N --> die danebenliegende ist die gesuchte, und sie ist leichter.

Wenn wir bei der zweiten Wägung den zweiten Fall hatten (LL+SN/N), dann können wir mit den drei LLS-Kugeln dasselbe Spiel spielen: L+L vergleichen - wo's raufgeht, ist die gesuchte, und sie ist leichter; bei Gleichgewicht ist's die danebenliegende, und sie ist schwerer.

Die beiden Fälle haben ein gleichartiges Muster: Aus zwei gleich markierten Kugeln (SS oder LL) und einer dritten, die ebenfalls schon mit S oder L markiert ist, kann man mit einer Wägung die Lösung finden ... ich nenne das eine AAB-Konfiguration, die uns hoffentlich bei dem komplizierteren SSSS+LLLL/NNNN-Fall aus der ersten Wägung weiterhilft!

Die zweite und dritte Wägung eines dynamischen Verfahrens nach SSSS+LLLL/NNNN

In diesem Fall wissen wir, dass links vier S-Kugeln liegen, rechts vier L-Kugeln. Wie weiter? Wenn wir schnell zu einer AAB-Konfiguration kommen, dann würden wir für viele Fälle die Lösung mit einer weiteren Wägung haben! Also probieren wir's ... nach einigem Herumprobieren bin ich auf folgendes gekommen: Man wiegt SSL + SSL / LL, mit folgenden Ergebnissen:

1. Waage geht links herunter: Entweder ist eine der beiden linken SS die gesuchte (und schwerer), oder die rechte L ist die gesuchte (und leichter). Man hat also drei Kugeln als SSL identifiziert, also eine AAB-Konfiguration gefunden!
2. Wenn die Waage rechts heruntergeht, dann hat man die anderen SSL als AAB identifiziert.
3. Und bei Gleichgewicht schließlich hat man die beiden LL als mögliche Lösungen identifiziert. Man kann sie direkt gegeneinander wiegen - wo's raufgeht, liegt die gesuchte leichtere. Man kann aber auch, "mathematiker-artig", eine N dazulegen und hat dann diesen Fall "auf eine AAB-Konfiguration" zurückgeführt ... das macht hier keinen Unterschied, hilft uns aber vielleicht bei anderen Problemen später!

In allen drei Fällen ist man also bei AAB angelangt - man findet dann also mit einer einzigen weiteren (dritten) Wägung die gesuchte Kugel.

Damit haben wir ein dynamisches Lösungsverfahren für das 12-Kugel-Problem gefunden! In Kürze - ich bezeichne die 12 Kugeln mit a,b,...,k,l:

1. Wägung: abcd+efgh/ijkl

Bei Gleichgewicht der ersten Wägung:

2. Wägung: ij+ka/l

3. Wägung: Bei Gleichgewicht: l mit a, sonst ijk mit AAB-Konfiguration (ij+ka geht links runter: ijk=SSL; ij+ka geht rechts runter: ijk=LLS).

Wenn erste Wägung links runter:

2. Wägung: abe+cdf/gh ist SSL+SSL/LL

Bei Gleichgewicht: ghi mit AAB-Konfiguration (LLN).

Wenn links runter: abf ist SSL, also AAB-Konfiguration; wenn rechts unter: cde ist SSL, also AAB.

Wenn erste Wägung rechts runter:

2. Wägung: abe+cdf/gh ist LLS+LLS/S - ist symmetrisch zu "links runter".

Umbau des dynamischen Verfahrens in ein statisches Verfahren

Bei dynamischen Verfahren wiegt man nur so wenige Kugeln, wie nötig sind. Es ist aber klar, dass man bei jeder Wägung links und rechts gleich viele N-Kugeln dazustapeln kann, ohne dass sich am Ergebnis was ändert. Was das bringen soll? Nun, man könnte die Wägungen, die man beim dynamischen Verfahren entweder/oder macht, nun zugleich machen! Und wenn man die Wägungen dabei immer gleich kombinieren kann, dann würde ein Verfahren herauskommen, wo man nicht verschiedene Gruppen je nach vorherigen Ergebnissen wiegt, sondern immer die gleichen - also ein statisches Verfahren!

Probieren wir das einmal: Die erste Wägung ist natürlich gleich - wir können ja, wie weiter oben ausgerechnet, nur mit einer 4+4-Wägung anfangen, und zu diesem Zeitpunkt ist es noch egal, welche Kugeln wir wählen. Die erste Wägung ist also abcd+efgh/ijkl (mit den Bezeichnungen aus dem letzten Abschnitt).

Zweite Wägung: In den beiden Ungleichgewichtsfällen haben wir hier beim dynamischen Verfahren schon beide Male dasselbe ausgeführt, nämlich abe+cdf/gh - das war also schon ein "klein wenig statisch". Im Gleichgewichtsfall kommt nun noch ij+ka/l dazu ... aber das können wir nicht zugleich abwiegen, weil dann auf der a-Seite 4 Kugeln liegen, auf der anderen aber 5 - so geht das nicht. Was tun???

Wir schauen uns die zweite dynamische Wägung noch einmal an: Sie ist ja abe+cdf/gh und hat im Gleichgewichtsfall eine etwas "schmalere" nächste Wägung ergeben, nämlich nur mehr g+h. Wir könnten diese Wägung zu AAB "auffetten", sodass bei der zweiten Wägung weniger auf der Waage liegt = "Platz für ij+ka wird". Konkret:

Wir bauen unser dynamisches Verfahren so um, dass bei der zweiten Wägung abe+cdi/fgh gewogen wird (statt f nehmen wir also i, was sicher eine neutrale Kugel ist). Wenn die erste Wägung links nach unten ging, sind diese Kugeln SSL+SSN/LLL markiert. Was sind die möglichen Ergebnisse?

1. links runter: abi=SSN ist AAB, was mit einer Wägung zu entscheiden ist.
2. rechts runter: ecd=LSS, also ist cde AAB - ebenfalls mit einer Wägung zu entscheiden.
3. Gleichgewicht: fgh=LLL, also AAB - auch mit einer Wägung zu entscheiden.

Wenn die erste Wägung rechts nach unten ging, kommt symmetrisch auch raus, dass eine weitere Wägung reicht.

Nun aber können wir abe+cdi/fgh mit ka+ij/l (die umgedrehte zweite Wägung aus dem dynamischen Verfahren, wenn die erste Wägung im Gleichgewicht war) kombinieren und erhalten als zweite Wägung:

abek+cdij/fghl

Wie gehen wir mit dem Ergebnis dieser Wägung um? Ungefähr so: Wenn die erste Wägung im Gleichgewicht war, dann wissen wir ja, dass a...h alle neutral sind, daher haben wir eigentlich nur ak+ij/l gewogen und können dieselben Schlüsse ziehen wie beim dynamischen Verfahren. Wenn aber die erste Wägung nach links ging, dann waren ja sicher i...l neutral, wir haben also praktisch abe+cdi/fgh gewogen und können auch passenden Schlüsse ziehen. Und dasselbe geht auch, wenn die erste Wägung nach rechts ging.

Zwei Wägungen sind also schon "statisch" - wir brauchen noch die dritte. Dazu müssen wir einmal alle dritten Wägungen aus dem dynamischen Verfahren aufsammeln. Der Reihe nach sind das:

• l+a (oder statt a eine andere neutrale Kugel)
• i+j/k
• a+b/i
• c+d/e
• f+g/h (oder zwei andere Kugeln von fgh, weil fgh hier LLL ist)
• nocheinmal die drei letzten Wägungen, weil die Ergebnisse symmetrisch sind (a+b/i ist nun LLN statt SSN, kann aber mit der gleichen Wägung entschieden werden)

Direkt lassen sich diese Wägungen nicht kombinieren, weil i einmal verwogen werden muss (zweite Zeile), einmal auf der Seite liegen muss (dritte Zeile). Mhm.

Eine Idee: AAB kann man nicht nur durch Verwiegen der zwei A-Kugeln entscheiden, sondern auch anders - allerdings nur, wenn A und B verschieden sind (also z.B. AAB=SSL): Dann kann man auf eine Seite SL legen, auf die andere NN. Wenn die Waage links runter geht, dann ist S die gesuchte (und schwerer), wenn sie rechts runtergeht, dann ist L die gesuchte (und leichter). Wir können also aus ijk=SSL oder LLS (siehe die Kurzbeschreibung im letzten Kapitel!) jk gegen zwei N-Kugeln verwiegen:

• l+a (oder statt a eine andere neutrale Kugel)
• jk+nn/i
• a+b/i
• c+d/e
• f+g/h (oder zwei andere Kugeln von fgh, weil fgh hier LLL ist)

Schaffen wir es, auf eine Seite vier Kugeln zu legen? Es geht sich nicht aus :-(

Das mit dem jk war vielleicht doch keine so gute Idee, weil nun eine Kugel mehr auf die Waage kam. Also zurück zur vorherigen Liste:

• l+a (oder statt a eine andere neutrale Kugel)
• i+j/k
• a+b/i
• c+d/e
• f+g/h (oder zwei andere Kugeln von fgh, weil fgh hier LLL ist)

Können wir a+b/i "drehen", sodass i auf der Waage liegt? abi war ja SSN oder LLN, und hier könnten wir statt a+b auch gern a+i wiegen: Bei Gleichgewicht ist dann b die gesuchte! Also müsste als dritte Wägung auch eine Summe aus Folgendem funktionieren (die ersten zwei Wägungen habe ich schon passend umgedreht):

• l+a (oder statt a eine andere neutrale Kugel)
• i+j/k
• i+a/b
• c+d/e
• f+g/h (oder zwei andere Kugeln von fgh, weil fgh hier LLL ist)

Und als "Summe" erhalten wir:

licf+ajdg/kbeh

Es sieht so aus, als hätten wir ein statisches Verfahren gefunden! - mit folgenden Wägungen (die Buchstaben habe ich jeweils aufsteigend sortiert):

• abcd+efgh/ijkl
• abek+cdij/fghl
• cfil+adgj/behk

Schauen wir, ob es funktioniert, indem wir für alle möglichen Lösungen die Wäge-Ergebnisse aufschreiben - sie müssen sich alle unterscheiden! L bedeutet hier "Waage senkt sich links", R "Waage senkt sich rechts", = "Waage bleibt im Gleichgewicht":

	a	b	c	d	e	f	g	h	i	j	k	l
schwerer	LLR	LL=	LRL	LRR	RL=	R=L	R=R	R==	=RL	=RR	=L=	==L
leichter	RRL	RR=	RLR	RLL	LR=	L=R	L=L	L==	=LR	=LL	=R=	==R

Tatsächlich!! - es hat funktioniert - alle Wägeergebnisse sind verschieden.

Ich höre hier mit den statischen Verfahren auf - manche Leute haben noch nette Tricks gefunden, wie man die drei Zeichen L, R und = als ternäre Ziffern interpretiert, sodass man sich nicht die Tabelle merken muss, sondern sich die Nummer der abweichenden Kugel aus dem Wägeergebnis als Zahl im Dreiersystem ausrechnen kann. Ein Beispiel dafür ist die andere Lösung, die hier angegeben ist.

Ich schaue mir aber noch schnell das Problem für andere Zahlen von Wägungen an!

Wieviele Kugeln kann man mit einer Wägung entscheiden?

Keine. Tatsächlich. Warum?

Das mindeste, was man zum Verwiegen braucht, sind zwei Kugeln. Wenn man die aber beide auf die Waage legt und sie sich links senkt, dann weiß man nicht, ob die linke schwerer oder die rechte leichter ist! Auch rechnerisch kann man sich das überlegen: Eine Wägung kann drei Ergebnisse unterscheiden, bei zwei Kugeln gibt es aber schon vier Möglichkeiten (erste schwerer, erste leichter, zweite schwerer, zweite leichter). Allerdings ist auch bei zwei Kugeln das Rätsel nicht sinnvoll: Denn ist nun die erste schwerer oder die zweite leichter?

Wieviele Kugeln kann man mit zwei Wägungen entscheiden?

Zwei Wägungen können 3²=9 Fälle unterscheiden, also prinzipiell das Problem für 4 Kugeln lösen. Überlegen wir, wie man das machen kann:

• Entweder wiegt man zuerst ab+cd. Dann hat man z.B. bei Ausschlag der Waage nach links noch vier Fälle (ab+cd=SS+LL), die man aber mit einer Wägung nicht vollständig entscheiden kann.
• Versuchen wir's also mit a+b/cd. Nun hat man aber bei Gleichgewicht cd=XX, also wieder vier Fälle, die nicht mit der zweiten Wägung zu entscheiden sind.

Also lassen sich mit zwei Wägungen das Rätsel für höchstens drei Kugeln entscheiden:

• Erste Wägung: a+b/c
• Bei Gleichheit 2.Wägung c+a=X+N, bei Ungleichheit ebenfalls c+a, aber nun als N+X.

Es ist schon erstaunlich, dass nur eine weitere Wägung die Zahl dann von 3 auf 12 hochkatapultiert!

Kann man mit drei Wägungen auch 13 Kugeln lösen?

Für 13 Kugeln gibt es 26 mögliche Lösungen. Das ist noch immer weniger als 3³=27 - man könnte also hoffen, dass man mit 3 Wägungen auch die "falsche" aus 13 herausfinden kann. Geht das?

Bei der ersten Wägung könnten wir (wie bei 12-Kugeln) 4+4 Kugeln auf die Waage legen - dann bleiben aber im Gleichgewichtsfall 5 daneben liegen, mit 10 möglichen Ergebnissen (jede kann entweder die schwerere oder die leichtere sein), was sich mit zwei weiteren Wägungen nicht vollständg lösen lässt (weil 3²=9<10).

Wenn man aber 5+5 Kugeln auf die Waage legt, scheitern wir bei Nicht-Gleichgewicht, wie schon im ersten Abschnitt erklärt. 12 Kugeln ist also tatsächlich das Maximum für drei Wägungen.

Der Witz der Zusatzkugel

Bevor ich hier zum "highlight" komme, nämlich der Anzahl der Kugeln, die man mit vier Wägungen "lösen" kann, noch ein Zwischenproblem: Nehmen wir an, wir hätten nicht nur die gegebenen Kugeln, sondern zusätzlich noch eine Kugel, von der wir sicher wissen, dass sie "normal" ist - was ändert das dann an der Anzahl an lösbaren Kugeln?

(Wie ich auf diese Frage komme? - naja, bei den 4 XXXX-Kugeln der 2. Wägung beim 12-Kugelproblem hat man ja eine solche Kugel zu den 2+1 dazugetan, und das hat "megamäßig" geholfen ...). Also:

• Mit einer Wägung kann man nun plötzlich doch für eine Kugel entscheiden, ob sie zu leicht oder zu schwer ist.
• Mit zwei Wägungen kann man aus 4 Kugeln die richtige herausfinden (sieht man ja bei der 2. Wägung des 12-Kugelproblems).
• Mit drei Wägungen: Hier können wir nun bei der ersten Wägung links 4 Kugeln und die N-Kugel, rechts 5 Kugeln drauflegen! Bei Ungleichgewicht gibt es dann noch 9 mögliche Lösungen, was genau gleich der Maximalanzahl 3² ist, die wir mit den restlichen zwei Wägungen noch lösen können - es könnte sich also ausgehen! Und damit könnten wir das Problem dann auch für 13 Kugeln lösen! (im Gleichgewichtsfall geht's so wie bei 12 Kugeln weiter). Probieren wir's: Wir haben nach Ungleichgewicht nun SSSSN und LLLLL (oder LLLL und SSSSS - aber das ist symmetrisch zu lösen). In der zweiten Wägung können wir nun SSL+SSL/LLL wiegen - und was auch immer herauskommt, wir haben ein AAB in der Hand: Entweder die linken zwei SS und die rechte L, oder die rechten zwei SS und die linke L, oder die danebenliegenden LLL - wir sind also nach einer weiteren Wägung fertig!

Erkenntnis: Mit einer Zusatz-Normalkugel kann man - zumindest bei einer, zwei und drei Wägungen - die "theoretische Maximalanzahl", nämlich [3^k/2] Kugeln entscheiden, wo k die Anzahl der Wägungen ist ([x] bezeichnet dabei die größte ganze Zahl kleiner oder gleich x):

• k = 1: [3¹/2] = [3/2] = 1
• k = 2: [3²/2] = [9/2] = 4
• k = 3: [3³/2] = [27/2] = 13

Wieviele Kugeln kann man mit vier Wägungen entscheiden?

Viele. Aber wie viele? Berechnen wir zuerst den absoluten Maximalwert: Vier Wägungen können 3⁴=81 Fälle unterscheiden. Damit ließe sich im Idealfall aus 40 Kugeln die eine schwerere oder leichtere herausfinden, weil es dann 2*40=80 mögliche Lösungen gibt. Aber sind es tatsächlich so viele?

Für eine genauere Einschränkung schauen wir uns - wie gerade für drei Wägungen - die erste Wägung an: Wir legen dort x+x Kugeln auf die Waage, y lassen wir daneben liegen. y kann höchstens 13 sein, weil wir aus diesen Kugeln ja mit drei Wägungen das Ergebnis finden müssen (aus dem letzten Abschnitt wissen wir, dass wir mit einer zusätzlichen Normalkugel in 3 Wägungen 13 Kugeln entscheiden können! - hier haben wir im Gleichgewichtsfall sicher viel mehr Normalkugeln zur Verfügung).

Damit x+x+y höchstens 40 ist, darf x höchstens 13 sein. Wenn wir 13+13 Kugeln verwiegen und die Waage nicht im Gleichgewicht bleibt, haben wir noch 26 mögliche Lösungen - weniger als die 3³=27, die wir mit den restlichen 3 Wägungen entscheiden können, daher kann sich das ausgehen! Daher könnte die Maximalzahl für vier Wägungen 13+13+13=39 Kugeln sein.

Und tatsächlich glaube ich, dass ich für 39 Kugeln ein dynamisches Lösungsverfahren gefunden habe ... das ich hier aber nicht verrate: Das kann jeder, der bis hierher gekommen ist, selber finden!

Und wenn man wieder eine weitere Normalkugel dazulegt, dann geht es wieder mit 40 Kugeln, denke ich! ...

Die abschließende große Hypothese

Es scheint, dass man einen vollständigen Induktionsbeweis führen können müsste, dass

• mit einer Zusatz-Normalkugel in k Wägungen die "unpassende" aus [3^k/2] Kugeln gefunden werden kann;
• ohne eine Zusatz-Normalkugel in k Wägungen die "unpassende" aus [3^k/2 - 1] Kugeln gefunden werden kann.

Diesen Beweis ordentlich zu führen, überlasse ich gern anderen :-)

Offene Frage: Kann ein statisches Verfahren immer gleich viele Kugeln leisten wie ein dynamisches mit gleich viel Wägungen?

Mit drei Wägungen kann man höchstens 12 Kugeln lösen - sowohl mit einem dynamischen wie mit einem statischen Verfahren. Auch bei zwei Wägungen sind dynamisches und statisches Verfahren gleich mächtig, und bei einer Wägung sowieso. Aber gilt das allgemein? Gibt es immer, wenn es ein dynamisches Verfahren gibt, auch ein statisches Verfahren? Das ist nicht offensichtlich, weil das dynamische Verfahren ja "mehr Information in sich zurückspeist". Ich habe aber keine Ahnung, wie ein Beweis aussieht, der zu einem dynamischen Verfahren immer ein statisches konstruieren kann.

Offene Frage: Kann man das statische Verfahren für 12 Kugeln eleganter erklären?

Das statische Verfahren habe ich oben durch "Umbau" des dynamischen Verfahrens gefunden.

Man kann auch direkt versuchen, die oben gezeigte Tabelle für das statische Verfahren auszufüllen. Dazu muss man sich zuerst klar machen, dass die Kombination === in keinem Feld stehen kann (denn dann würde die entsprechende Lösungskugel ja gar nicht auf die Waage gelegt worden sein, und dann wüsste man nicht, ob sie schwerer oder leichter ist, wenn sie die abweichende ist). Außerdem steht immer in der unteren Zelle das "Gegenteil" der oberen, wenn man L gegen R austauscht. Zuletzt müssen an jeder Position gleich viele L, R und = vorkommen, weil alle vier Wägungen von der Form 4+4/4 sind (was ich nicht bewiesen habe - aber ich vermute, dass ein statisches Verfahren für 12 Kugeln nur so gelingt). Mit etwas Herumbasteln findet man dann Tabellenwerte, die diese Bedingungen erfüllen - das ist dann aber eine typische "Lösung, die vom Himmel fällt".

Die Frage ist: Gibt es eine bessere, schönere, "elegantere" Erklärung für ein (bestimmtes) statisches Verfahren? Bei den Zahlen 12 und 3 fallen einem schon andere mathematische Dinge ein: Ein 3-dimensionaler Würfel hat 12 Kanten. Außerdem hat ein Würfel, wenn man auf eine Spitze schaut, eine dreifache Rotationssymmetrie. Es ist mir aber nicht gelungen, aus diesen geometrischen Vorstellungen ein statisches Verfahren "herauszukitzeln" - der Würfel ist "zu symmetrisch dazu". Hat jemand eine Idee, wie das gehen könnte?