\(\begingroup\)
120 Kugeln und eine Balkenwaage
Gegeben sind N = 120 Kugeln, die alle gleich aussehen. Eine Kugel ist schwerer, oder leichter, als alle anderen Kugeln. Mit einer Balkenwaage soll die >falsche Kugel< identifiziert werden incl. der Angabe, ob diese Kugel schwerer, oder leichter ist, als alle anderen Kugeln.
-- wie viele Wägungen W sind minimal erforderlich ?
-- wie laufen diese Wägungen ab ?
-- angenommen: Die Verteilung der Kugeln ist pro Wägung stets gleich.
Man kennt nach Ablauf von W Wägungen nur den jeweiligen Ausschlag der
Balkenwaage; Beispiel :
1. Wägung: ▼ ( linke Waagschale ist schwerer, und geht nach unten )
2. Wägung: ▲ ( linke Waagschale ist leichter, und geht nach oben )
3. Wägung : ▬ ( beide Schalen sind im Gleichgewicht )
4. Wägung: ▲ ( linke Waagschale ist leichter, und geht nach oben )
etc.
Wie könnte so eine stets gleiche Verteilung der Kugeln pro Wägung aussehen, um nach W Wägungen etwa mit der Information > ▼ ▲ ▬ ▲ ….. < die >falsche Kugel< zu identifizieren, incl. Gewichtsangabe (schwerer / leichter) ?
Autor: Dipl.- Ing. Josef Meiler
120 Kugeln und eine Balkenwaage
Gegeben sind N = 120 Kugeln, die alle gleich aussehen. Eine Kugel ist schwerer, oder leichter, als alle anderen Kugeln. Mit einer Balkenwaage soll die >falsche Kugel
\(\begingroup\)minimal sind zwei Wägungen notwendig - ich nehme Kugel 1 und 2 und hab' das Glück, das die Waage kippt - ich nehm' dann die potentiell leichtere und vergleich sie mit einer dritten Kugel - kippt die Waage wieder, ist die potentiell leichtere Kugel wirklich leichter, ansonsten ist die potentiell schwerere Kugel wirklich schwerer 😁 😁 😁 \(\endgroup\)
\(\begingroup\)Hier wie ich vorgehen würde:
Zunächst teile ich die 120 Kugeln in 3 Stapel (Stapel I, Stapel II und Stapel III) je 40 Kugeln auf und wiege zunächst Stapel I gegen Stapel II und dann Stapel II gegen Stapel III. Anhand dieser beiden Wiegungen erkenne sowohl in welchem Stapel die Kugel mit abweichendem Gewicht ist als auch ob diese Kugel leichter oder schwerer ist als alle anderen.
Ich konzentriere mich nun auf den 40er Stapel mit der Kugel mit abweichendem Gewicht und teile diese auf in zwei Stapel mit je 11 Kugeln (Stapel IV und Stapel V) und einen Stapel mit 18 Kugeln (Stapel VI). Nun wiege ich Stapel IV gegen Stapel V und weiss nun wiederum in welchem der drei Stapel sich die gesuchte Kugel befindet.
Befindet sich die Kugel im 18er-Stapel, dann teile ich diesen wiederum in drei 6er-Stapel auf, wiege zwei von denen gegeneinander, und teile denjenigen der drei Stapel, in dem sich die Kugel befindet, in drei Zweier-Stapel ein. Dann werden wieder zwei dieser Stapel gewogen... und nach 6 Wiegungen kenne ich das Ergebnis.
Befindet sich die Kugel im 11er-Stapel, teile ich diesen in zwei 3er-Stapel und einen 5er-Stapel auf. Der 5er-Stapel wiederum würde im nächsten Zug in zwei 2er-Stapel und einen 1er-Stapel aufgeteilt werden...
Insgesamt kenne ich mit dieser Strategie mit Wahrscheinlichkeit 3/10 das Ergebnis nach 5 Zügen und mit Wahrscheinlichkeit 7/10 nach 6 Zügen.\(\endgroup\)
\(\begingroup\)Noch besser:
40->15,15,10
15->3,3,9
3->1,1,1
9->3,3,3
3->1,1,1
10->3,3,4
3->1,1,1
4->1,1,2
2->1,1
Dann habe ich die Kugel mit Wahrscheinlichkeit 1/2 nach 5 Zügen und mit Wahrscheinlichkeit 1/2 in 6 Zügen gefunden.
\(\endgroup\)
\(\begingroup\)Mir gefallen die lustigen Kugeln oben im Bild. 😄
Leider ist es bei mir auf der Startseite nicht zu sehen, sondern nur wenn ich den Artikel aufrufe.\(\endgroup\)
\(\begingroup\)Hallo dlchnr,
Du schreibst:
>natürlich ist mir klar, dass Du auf die minimale Maximalzahl abzielst, mit der das Rätsel immer gelöst werden kann<
Der Ausdruck >minimale Maximalzahl< ist mir unbekannt.
Natürlich ist die Sache so zu verstehen, dass alle Fälle betrachtet werden müssen; es handelt sich nicht um ein >Glücksspiel<.
viele Grüße
JoeM \(\endgroup\)
\(\begingroup\)Hallo Slash,
Du schreibst:
>Mir gefallen die lustigen Kugeln oben im Bild.
Leider ist es bei mir auf der Startseite nicht zu sehen, sondern nur wenn ich den Artikel aufrufe.<
Dazu folgendes:
Das finde ich auch schade: Anscheinend habe ich beim Einstellen des Artikels irgendwas >falsch gemacht<
Vielleicht kann das >matroid< noch ändern ?.
Wie das geht, weiss ich nicht; kannst Du dazu was beitragen ?
viele Grüße
JoeM\(\endgroup\)
\(\begingroup\)Hallo Trumpf,
Du schreibst in Deinem letzten Kommentar:
>Dann habe ich die Kugel mit Wahrscheinlichkeit 1/2 nach 5 Zügen und mit Wahrscheinlichkeit 1/2 in 6 Zügen gefunden.<
Dazu folgendes: Es geht nicht um Wahrscheinlichkeiten.
Es gibt einen absoluten min. Wert aller Wägungen W mit Wahrscheinlichkeit von 1,00 . Damit sind alle Möglichkeiten abgedeckt.
viele Grüße, und viel Spass beim weiteren Rätseln.
JoeM
\(\endgroup\)
\(\begingroup\)
Der Link muss so aussehen
\sourceon nameDerSprache
\sourceoff
Gehe einfach zu "Meine früheren Uploads" und kopiere den Link aus dem Fenster - einfach anklicken, dann geht das Fenster auf. Ist ja eigentlich nur HTML-Code, wenn ich nicht irre. Habe es dir gerade geändert und eine Anfrage geschickt.
Gruß, Slash\(\endgroup\)
\(\begingroup\)@JoeM: Ich verstehe deinen Einwand nicht.
Meine Strategie liefert mit 100%iger Wahrscheinlichkeit das Ergebnis nach spätestens 6 Zügen und mit Wahrscheinlichkeit 50% sogar früher. Letztgenannte Zusatzinformation ist hier auf jeden Fall interessant, wenn man die Qualität anderer Strategien mit der von mir genannten Strategie vergleichen will und wenn man dies nicht berücksichtigt, dann ist die von mir genannte Strategie bereits optimal, denn eine Strategie, die nach 5 Zügen sicher das Ergebnis liefert, gibt es nicht.
Um das Problem interessanter zu machen, würde ich es an deiner Stelle übrigens in folgendem Sinne stochastisch erweitern (andernfalls ist es ja bereits gelöst, wie ich behaupte):
"Es bezeichne T die minimale Anzahl an Versuchen, die nötig sind um das Problem sicher (also mit 100%iger Wahrscheinlichkeit) zu lösen. Man bezeichne eine Strategie S als optimal, wenn folgende Bedingungen erfüllt sind:
- Die Strategie S löst das Problem sicher in höchstens T Versuchen.
- Unter denjenigen Strategien, die das Problem sicher in höchstens T Versuchen lösen, gibt es keine Strategie, welche das Problem mit höherer Wahrscheinlichkeit in höchstens T-1 Versuchen löst als Strategie S.
- Unter denjenigen Strategien, die das Problem sicher in höchstens T Versuchen lösen und mit gleicher Wahrscheinlichkeit wie S in T-1 Versuchen lösen, gibt es keine Strategie, welche das Problem mit höherer Wahrscheinlichkeit in höchstens T-2 Versuchen löst als Strategie S.
- ...
Welches ist eine optimale Strategie?"
Die Existenz einer solchen Strategie dürfte klar sein. Fraglich ist nur, ob die von mir genannte Strategie bereits in diesem Sinne optimal ist.
\(\endgroup\)
\(\begingroup\)Hallo JoeM,
mit zwei Wägungen von jeweils 40 Kugeln pro Waagschale werden die 40 Kugeln bestimmt, die die eine im Gewicht abweichende Kugel enthalten. Dabei ist auch gleich bestimmt ob diese leichter oder schwerer ist.
Jetzt werden noch 4 Wägungen benötigt um die Kugel zu selektieren.
Man kann mit 6 Wägungen diese Knobelaufgabe auch für 243 Kugeln lösen.
Viele Grüße
salomeMe\(\endgroup\)
\(\begingroup\)Hallo salomeMe,
Du schreibst :
>mit zwei Wägungen von jeweils 40 Kugeln pro Waagschale werden die 40 Kugeln bestimmt, die die eine im Gewicht abweichende Kugel enthalten. Dabei ist auch gleich bestimmt ob diese leichter oder schwerer ist.
Jetzt werden noch 4 Wägungen benötigt um die Kugel zu selektieren.
Man kann mit 6 Wägungen diese Knobelaufgabe auch für 243 Kugeln
lösen.<
Dazu folgendes:
Wenn man so vorgeht, wie Du es hier beschrieben hast, dann benötigt man für 120 Kugeln: 2 + 4 = 6 Wägungen, und
für 243 Kugeln: 2 + 5 = 7 Wägungen (und nicht 6, wie Du schreibst)
Diese Strategie ist nicht die beste !
viele Grüße
JoeM
\(\endgroup\)
\(\begingroup\)Nicht optimal im Sinne meiner Definition von Optimalität? Oder was genau verstehst du unter "optimal"? Glaubst du eine Strategie zu kennen, die stets mit weniger als 6 Versuchen zum Ziel führt?
MfG
Trumpf
P.S.: Ich heiße übrigens Trumpf, mit diesem Trump möchte ich nichts zu tun haben ;)
P.S. 2: salomeMe hat Recht. Mit seiner Strategie benötigt er bei 243 Kugeln immer genau 6 Züge, denn 2+4 ist nicht gleich 7 xD\(\endgroup\)
\(\begingroup\)Hallo Trumpf,
ich glaube nicht nur, eine Strategie zu kennen, die stets mit weniger, als 6 Versuchen zum Ziel führt.
Ich weiss es:
Meine Strategie führt stets mit weniger, als 6 Versuchen zum Ziel.
Zu 100 %
PS: meine Nachricht an SalomeMe habe ich korrigiert; ich hatte mich verschrieben; es muss natürlich heissen > 2 + 5 = 7 <.
PS: Sorry; mit Trump will ich auch nichts zu tun haben !
viele Grüße
JoeM
\(\endgroup\)
\(\begingroup\)Trotzdem hat er Recht, er benötigt mit seiner Strategie immer genau 6 Züge.
P.S.: Ich hoffe deine Lösung wird nicht so enttäuschend ausfallen, wie deine letzte Lösung des Ziegenproblems (EDIT: siehe Kommentar unter deinem vorhergehenden Artikel) ;)\(\endgroup\)
\(\begingroup\)Hallo Trumpf,
was ich verspreche, kann ich selbstverständlich halten.
Was die 243 Kugeln mit 6 Wägungen angeht:
Meine Strategie kann ich mit 6 Wägungen auf wesentlich mehr, als 243 Kugeln anwenden.
viele Grüße
JoeM
\(\endgroup\)
\(\begingroup\)Hallo Trumpf,
nebenbei:
was meinst Du mit Deiner Nachricht:
> P.S.: Ich hoffe deine Lösung wird nicht so enttäuschend ausfallen, wie deine letzte Lösung des Ziegenproblems <
Ich habe zwei >Ziegenprobleme< eingestellt; welches von beiden meinst Du ?
Was war für Dich daran so enttäuschend ?
Hast Du dafür andere Lösungen ?
viele Grüße
JoeM\(\endgroup\)
\(\begingroup\)Hallo fermat63,
Du hast mir eine private Nachricht gesendet.
Das Antworten über die private Nachricht klappt nicht.
Ich hab mir Deinen Link angesehen.
Anscheinend geht es um 12 Kugeln, und 3 Wägungen.
Ja... Mein Artikel hat damit was zu tun.
Könntest Du bitte Deine Fragen hier stellen; dann kann ich besser, und schneller antworten.
viele Grüße
JoeM \(\endgroup\)
\(\begingroup\)Ich stelle mal meine Frage an JoeM über PM(wie von ihm gewünscht) hier als Kommentar ein:
Hallo JoeM
Kurze Frage:
Hat das Rätsel mit Informations Theorie zu tun, also dem Shannon information content und entropy, wie in diesem Video mit David McKay "weighing problem with 12 balls" (etwa ab Min. 21):
hier
Ein Buch von David McKay ist auch zum konstenfreien download als pdf erhältlich(nur zum eigenen Gebrauch, nicht zum Ausdrucken oder Kopieren, Weiterleiten ! Dieses ist im Copyright noch ausgeführt).
Viele Grüsse
fermat63 \(\endgroup\)
\(\begingroup\)Hallo Trumpf,
Dein Kommentar lautet u.a.:
>dann ist die von mir genannte Strategie bereits optimal, denn eine Strategie, die nach 5 Zügen sicher das Ergebnis liefert, gibt es nicht.
Um das Problem interessanter zu machen, würde ich es an deiner Stelle übrigens in folgendem Sinne stochastisch erweitern (andernfalls ist es ja bereits gelöst, wie ich behaupte)....<
Dazu folgendes:
1) Deine Strategie ist nicht optimal.
2) Deine Behauptung >gelöst< ist falsch.
3) Dein Ansatz > ... eine Strategie, die nach 5 Zügen sicher das
Ergebnis liefert, gibt es nicht <, ist ebenfalls falsch.
4) Dein Ansatz, das Problem interessanter zu machen durch eine stochastische Erweiterung ist nicht interessant.
viele Grüße
JoeM
\(\endgroup\)
\(\begingroup\)Also der Start mit 3 Gruppen a 40 Kugeln dürfte suboptimal sein.
Besser dürften 3 etwas kleinere Gruppen sein, die mittels zweier Wägungen eine schwerere oder leichtere Kugel in einer der drei Gruppen ergeben oder aber eine unbestimmt abweichende Kugel in der Restgruppe, die aber mit drei weiteren Wägungen lösbar ist.
z.B.:
120->->37,37,37 (9)
9->->3,3,3
3->1,1,1
37-> ...
Vielleicht hat ja jemand eine Idee, wie man eine Restgruppe > 9 (also 12 oder 15 oder 18 ... mit drei Wägungen noch lösen kann, so dass der alternative Zweig nur noch 36 oder 35 oder 34 ... Kugeln abhandeln muss?
\(\endgroup\)
\(\begingroup\)Hallo JoeM,
zu 1): Das stimmt, ich kenne die Lösung inzwischen. Das Problem ist leider nicht neu, man findet die Lösung im WWW. Ich habe übrigens geschrieben, dass es fraglich ist, ob meine Lösung optimal ist.
zu 2) & 3): Das hast du aus dem Kontext gerissen, ich hatte das als Hypothese gekennzeichnet ("wie ich behaupte").
zu 4): Das sehe ich anders. Es ist nämlich nicht gerade klar, dass die Lösung, auf die du hinaus möchtest, auch in diesem Sinne optimal ist.
MfG
Trumpf
P.S.: Hast du meine Kritik an deiner Lösung zum Ziegenproblem gelesen?
\(\endgroup\)
\(\begingroup\)Hallo fermat63,
vielen Dank für Deinen Link >mit 12 Kugeln und 3 Wägungen<
Bei K = 12 Kugeln sind W = 3 Wägungen erforderlich.
Ich finde: Der Artikel ist >zu kompliziert<; es geht einfacher:
Mein Algorithmus ist allgemein, und deckt für max. K min. Wägungen W ab.
Beispiel: Für max. K = 12 Kugeln sind min. W = 3 Wägungen erforderlich.
Beispiel: Für max. K = 120 Kugeln sind min. W = 5 Wägungen erforderlich.
viele Grüße
JoeM
\(\endgroup\)
\(\begingroup\)Hallo Trumpf,
Deine Kritik zum Ziegenproblem habe ich nicht gelesen.
Ansonsten:
Ich habe das >Kugelproblem< bereits vor ca. 21 Jahren schon allgemein gelöst.
Da gab es noch kein www.
Nebenbei: wie viele Wägungen sind für 9840 Kugeln erforderlich ?
viele Grüße
JoeM \(\endgroup\)
\(\begingroup\)Hallo Trumpf,
na endlich;
N = 3 Kugeln: W = 2 Wägungen
N = (3+1)*3 = 12 Kugeln: W = 3
N = (12+1)*3 = 39 Kugeln: W = 4
N = (39+1)*3 = 120 Kugeln: W = 5
N = (120+1)*3 = 363 Kugeln: W = 6
usw.
Wie erfolgt die Wägung z.B. für N = 120 Kugeln ?
viele Grüße
JoeM
\(\endgroup\)
\(\begingroup\)Es konkrekt aufzuschreiben ist mir zu mühsam. Die Lösung lässt sich recht einfach aus dieser Lösung für das selbe Problem mit 12 Kugeln ableiten ().\(\endgroup\)
\(\begingroup\)Hallo dlchnr,
die Aufgabe ist nur dann optimal lösbar, wenn man zu Anfang 2- mal 40 Kugeln abwiegt.
Alles andere geht nicht.
viele Grüße
JoeM\(\endgroup\)
\(\begingroup\)Hallo Trumpf,
Du schreibst:
>Es konkret aufzuschreiben ist mir zu mühsam. Die Lösung lässt sich recht einfach aus dieser Lösung für das selbe Problem mit 12 Kugeln ableiten ().<
Dazu meine Meinung:
Wie soll man aus diesem Link mit 12 Kugeln auf 120 Kugeln schliessen ?
Kannst Du das näher erklären ?
Ansonsten:
In meiner Aufgabe stand noch folgendes:
-- angenommen: Die Verteilung der Kugeln ist pro Wägung stets gleich.
Man kennt nach Ablauf von W Wägungen nur den jeweiligen Ausschlag der
Balkenwaage; Beispiel :
1. Wägung: ▼ ( linke Waagschale ist schwerer, und geht nach unten )
2. Wägung: ▲ ( linke Waagschale ist leichter, und geht nach oben )
3. Wägung : ▬ ( beide Schalen sind im Gleichgewicht )
4. Wägung: ▲ ( linke Waagschale ist leichter, und geht nach oben )
etc.
Wie könnte so eine stets gleiche Verteilung der Kugeln pro Wägung aussehen, um nach W Wägungen etwa mit der Information > ▼ ▲ ▬ ▲ ….. < die >falsche Kugel< zu identifizieren, incl. Gewichtsangabe (schwerer / leichter) ?
Hast Du dazu eine Idee ?
viele Grüße
JoeM\(\endgroup\)
\(\begingroup\)Hallo Trumpf,
zu Deinem Kommentar:
>zu 4): Das sehe ich anders. Es ist nämlich nicht gerade klar, dass die Lösung, auf die du hinaus möchtest, auch in diesem Sinne optimal ist.<
Das sehe ich anders.
Meine Strategie ist optimal; es gibt keine bessere.
viele Grüße
JoeM
\(\endgroup\)
\(\begingroup\)Ist das wirklich so klar? Theoretisch kann man mit 5 Wiegevorgänge 243 verschiedene Fälle unterscheiden, nicht nur 240.
Kannst du beweisen, dass es keine Strategie geben kann, welche mit positiver Wahrscheinlichkeit nur 4 Versuche benötigt?\(\endgroup\)
\(\begingroup\)Hallo JoeM,
zu Deiner Antwort auf meinen Vorschlag.
Wenn Deine Aufgabenstellung analog mit 243 Kugeln gestellt worden wäre, hätte ich natürlich 2 mal je 81 Kugel je Schale abgewogen. Danach je einmal je 27, 9, 3, 1 und wäre auch mit insgesamt 6 Wägungen fertig.
Wahrscheinlich könnte man mit 6 Wägungen sogar noch etwas mehr Kugeln behandeln, falls sich nach 2 Wägungen ergibt, dass die 243 gewogenen Kugel alle das gleiche Gewicht haben. Hätte man noch 4 Wägungen um aus dem Rest die eine herauszufiltern. Der Rest wären wohl 30, also zusammen 273 Kugeln.
Mit meiner Strategie könnte ich mit 5 Wägungen aber nur 91 Kugeln sicher filtern.
Könnte es sein, dass vergessen wurde, dass der Rest (den ich eingeführt habe) eine Kugel enthält von der noch nicht bekannt ist, ob sie leichter oder schwerer ist?
Beste Grüße
salomeMe
\(\endgroup\)
\(\begingroup\)Hallo salomeMe,
mit Deiner Methode kann man nach 2, 3, 4, 5, 6, ..... Wägungen
3, 9, 27, 81, 243,...... Kugeln erfassen.
Die optimale Methode bedeutet aber:
nach 2, 3, 4, 5, 6, ..... Wägungen kann man 3, 12, 39, 120, 363,...... Kugeln erfassen.
kleiner Tipp:
die 1. Wägung sieht aus, wie bei Dir; alle weiteren Wägungen verlaufen anders, als bei Deiner Vorgehensweise.
viele Grüße
JoeM
\(\endgroup\)
\(\begingroup\)Man kann die von JoeM beabsichtigte Lösung für 0,5*((3^n)-3) Kugeln (für n grössergleich 3) aus der von mir zuvor verlinkten Lösung für 12 Kugeln ableiten. Ich poste jetzt mal eine Beispiellösung für 120 Kugeln in der Hoffnung damit die Randdiskussionen, die sich hier ergeben haben, etwas zu befeuern.
\hideon
Ich notiere die Zahlen von 1 bis 120. Ich beginne damit der Zahl 1 ihre eindeutige Darstellung als Summe/Differenz einer Teilmenge der Dreierpotenzen von Grad 0 bis Grad 4 zuzuordnen [1 = 1*3^0 + 0*3^1 + 0*3^2 + 0*3^3 + 0*3^4]. Dann notiere ich für die 1 ein positives Vorzeichen sowie einen fünfstelligen Vektor, welcher die obige Darstellung repräsentiert, d.h.
1<->(+,(1,0,0,0,0)).
Dann ändere ich jede "1" in diesem Vektor in eine "-1" und addiere zu allen anderen Komponenten eine 1, es ergibt sich also der Vektor
(-1,1,1,1,1),
dieser Vektor repräsentiert offenbar die Zahl 119 [119 = (-1)*3^0 + 1*3^1 + 1*3^2 + 1*3^3 + 1*3^4], also notiere ich (erneut mit positivem Vorzeichen, da 119 positiv ist)
119<->(+,(-1,1,1,1,1)).
Ich führe die gleiche Prozedur noch einmal durch und erhalte den Vektor
(0,-1,-1,-1,-1),
dieser repräsentiert die Zahl -120 [-120 = 0*3^0 + (-1)*3^1 + (-1)*3^2 + (-1)*3^3 + (-1)*3^4], also notiere nun (diesmal mit negativem Vorzeichen, da -120 negativ ist)
120<->(-,(0,-1,-1,-1,-1)).
Im nächsten Durchgang beginne ich mit der kleinsten noch nicht betrachteten Zahl. So erhalte ich beispielsweise im zweiten Durchgang die Verknüpfungen
2<->(+,(-1,1,0,0,0)),
114<->(+(0,-1,1,1,1)),
116<->(-(1,0,-1,-1,-1)).
Nach 40 Durchgängen habe ich jeder Zahl einen Vektor zugeordnet. Die Kugeln werden nun durchnummeriert mit den Zahlen von 1 bis 120. Nun können die einzelnen Wiegevorgänge folgendermaßen organisiert werden: Im k-ten der fünf Wiegeschritte werden genau diejenigen Kugeln, die Eintrag "-1" in der k-ten Komponente ihres Zahlenvektors tragen, auf die linke Seite der Waage gelegt und genau diejenigen Kugeln, die Eintrag "1" in der k-ten Komponente ihres Zahlenvektors tragen, auf die rechte Seite der Waage gelegt (also jeweils genau 40, je eine aus jedem 3er-Zyklus).
\hideoff
\hideon
Nun werden die fünf Wiegevorgänge durchgeführt, die Ergebnisse werden notiert. Danach wird für den k-ten Wiegeschritt eine "-3^(k-1)" notiert, falls die Waage links nach unten ausschlug, eine "0" falls die Waage ausgeglichen war und eine "3^(k-1)", falls die Waage rechts nach unten ausschlug und diese fünf Zahlen werden dann addiert. Der Betrag dieser Summe gibt nun die Nummer der Kugel mit abweichendem Gewicht an und das Vorzeichen der Summe gibt an, ob die Kugel leichter oder schwerer ist als die anderen: Stimmt das Vorzeichen der Summe mit dem Vorzeichen überein, mit welchem die Nummer der Kugel gekennzeichnet wurde, so ist die Kugel schwerer als alle anderen und sind die Vorzeichen verschieden, so ist die Kugel leichter.
\hideoff
EDIT: Wie von salomeMe in seinem nächsten Beitrag angemerkt, ist diese Lösung nur dann zulässig, wenn man annimmt die Kugeln nummerieren zu können bzw. wenn man (durch spezielle Sortierungen der Kugeln außerhalb >und auch auf der Waage<) dazu in der Lage ist zu jedem Zeitpunkt für einzelne Kugeln zu wissen, auf welchen Seiten der Waage sie bisher in welcher Reihenfolge gelegen haben. Dem Einwand, dass dies nicht im Sinne der Aufgabenstellung ist ("Kugeln, die alle gleich aussehen" - Warum sollte das in der Aufgabenstellung erwähnt werden, wenn es letztendlich erlaubt wäre die optische Ununterscheidbarkeit der Kugeln trickreich, z.B. durch Nummerierung, zu umgehen?), muss ich mich anschließen.
EDIT: Selbiges gilt selbstverständlich für BEIDE im Folgenden (am 22.02 um 01:06 und um 02:37) vom Artikelautor geposteten Lösungen, welche übrigens sehr viel uneleganter sind als diese Lösung (sorry, aber das musste jetzt einfach sein 😁 ).\(\endgroup\)
\(\begingroup\)Hallo Trumpf,
Du schreibst:
>Ist das wirklich so klar? Theoretisch kann man mit 5 Wiegevorgänge 243 verschiedene Fälle unterscheiden, nicht nur 240.
Kannst du beweisen, dass es keine Strategie geben kann, welche mit positiver Wahrscheinlichkeit nur 4 Versuche benötigt?<
Ich sehe das so:
Bei 5 Wägungen gibt es 5^3 - 1 = 242 Möglichkeiten.
Eine Möglichkeit muss man abziehen (alle Kugeln gleich schwer)
Für 120 Kugeln ( eine leichter/schwerer) gibt es 120*2 =240 Möglichkeiten.
Nun könnte man meinen, die Sache sollte auch für 121 Kugeln funktionieren: 121*2 = 242 Möglichkeiten.
Aber das funktioniert nicht;
Beispiel 13 Kugeln ( statt 12 Kugeln ):
Hier gilt: 3 Wägungen; d.h. 3^3 - 1 = 26 Möglichkeiten; sowie
13*2 = 26 Möglichkeiten für schwer/leicht.
Bei 13 Kugeln, und 3 Wägungen kann man zwar die >falsche Kugel< identifizieren, aber man kann nicht sagen, ob diese Kugel leichter oder schwerer ist.
Es liegt wohl daran, dass 26 nicht durch 3 teilbar ist.
Was meinst Du mit >positiver Wahrscheinlichkeit<
viele Grüße
JoeM
\(\endgroup\)
\(\begingroup\)Ich meine damit eine Strategie, bei der die zukünftigen Wiegevorgänge (sowie auch deren Anzahl) vom Ausgang vergangener sowie des gegenwärtigen Wiegevorgangs abhängen dürfen und für die ein Fall existiert, in dem sie schon nach 4 Versuchen das Ergebnis liefern (bzw. nach 2 Versuchen im 12er-Beispiel). Ich empfinde die Nichtexistenz solcher Strategien nicht als trivial. Und schon deswegen ist diese Erweiterung der Fragestellung für mich spannend.
Es muss sich dabei natürlich um eine Strategie handeln, für welche das Kriterium einer "stets gleiche[n] Verteilung der Kugeln pro Wägung" nicht erfüllt ist.
Wenn man den allgemeinen Fall betrachtet (sprich: wenn die Anzahl der Kugeln nicht gleich 0,5*(3^n-3) für ein n groessergleich 3 sein muss), dann dürfte übrigens leicht zu erkennen sein, dass diese Erweiterung der Fragestellung interessant ist. Und selbst wenn sich herausstellen sollte, dass die bezüglich dieser Erweiterung optimale Strategie in den genannten Spezialfällen dieselbe ist, wie in der von dir formulierten Problemstellung, ändert das für mich nichts daran, dass die erweiterte Problemstellung auch in diesen Fällen interessant ist. Auch dann wäre es nämlich immer noch eine allgemeinere Problemstellung.
Um es überspitzt zu formulieren: Dass die Zahl 1 das Problem "3-2" löst, heisst nicht, dass nicht andere Fragestellungen, die ebenfalls durch die Zahl 1 gelöst werden, interessanter sein können. ;)\(\endgroup\)
\(\begingroup\)Hallo Trumpf,
ich habe gerade Deinen Kommentar zum meinem >Ziegenproblem< gelesen:
>P.S.: Ich hoffe deine Lösung wird nicht so enttäuschend ausfallen, wie deine letzte Lösung des Ziegenproblems (EDIT: siehe Kommentar unter deinem vorhergehenden Artikel)<
Du hast anscheinend mein >Ziegenproblem< falsch interpretiert;
siehe dazu meinen Kommentar zum Artikel >Ziegenproblem<.
Vielleicht kannst Du jetzt das >Ziegenproblem< lösen ?!
viele Grüße
JoeM \(\endgroup\)
\(\begingroup\)Hallo SalomeMe,
es gibt verschiedene Möglichkeiten, das Kugelproblem zu lösen.
Ich finde: Die eleganteste Methode ist folgende:
Nach W Wägungen hat man bei jeweils gleicher Verteilung der Kugeln nur z.B. die Info:
> ▼ ▲ ▬ ▲ ….. <
Beispiel mit N = 12 Kugeln, und W = 3 Wägungen:
Man kennt nach 3 Wägungen nur den jeweilige Ausschlag der Balkenwaage;
dann kann man die >falsche Kugel< identifizieren; etwa so:
http://matheplanet.com/matheplanet/nuke/html/uploads/9/44117_W888.jpg
http://matheplanet.com/matheplanet/nuke/html/uploads/9/44117_W999.jpg
beste Grüße
JoeM
\(\endgroup\)
\(\begingroup\)Hallo Trumpf,
ich halte fest: Du hast meine Aufgabe (Ziegenproblem) leider nicht verstanden !
Zum Trost: Du bist nicht der Einzige.
viele Grüße
JoeM\(\endgroup\)
\(\begingroup\)Was hälst du davon in der Kommentarspalte des entsprechenden Artikel konkret auf meine Einwände einzugehen, statt hier herumzuschimpfen? Als Verfasser des Artikels solltest du dich dazu verpflichtet fühlen, ernsthaft zu versuchen Missverständnisse aufzuklären und auf handfeste Kritik angemessen zu reagieren. Das scheint bei dir aber leider nicht der Fall zu sein.
Ich werde in der Kommentarspalte dieses Artikels ab jetzt übrigens nur noch auf Anmerkungen mit Bezug zu diesem Artikel reagieren, so wie sich das ja eigentlich gehört (bzw. überhaupt nicht mehr, siehe unten).
EDIT:
Zu deinem Folgekommentar: "Ausreden"?! Wenn das dein Ernst ist, ist das eine Bestätigung dessen, was ich gerade geschrieben habe, wie sie klarer kaum sein könnte.
EDIT:
Auch aus der Kommentarspalte dieses Artikels halte ich mich von jetzt an vielleicht besser heraus.\(\endgroup\)
\(\begingroup\)Hallo Trumpf,
ich schimpf nicht herum;
ich halte nur fest, dass Du >mit Ausreden< keine Lösung gefunden hast.
Es sei denn; Du lieferst noch eine.
viele Grüße
JoeM\(\endgroup\)
\(\begingroup\)Hallo JoeM,
nehmen wir mal an, dass eine Strategie für 120 Kugeln existiert, die nach 5 Wägungen mit beginnenden zwei 40-er Wägungen zum Ziel führt.
Behauptung:
Dann muss auch eine Strategie für 130 Kugeln existieren, die mit 5 Wägungen zum Ziel führt.
Beweis:
Bei 130 Kugeln und beginnenden zwei 40-er Wägungen, kann es jetzt passieren, dass zweimal Gleichgewicht erzielt wird, die gesuchte Kugel also unter den 10 nicht gewogenen Kugeln ist. Mit den noch ausstehenden 3 Wägemöglichkeiten kann man mit traditionellen Mitteln die abweichende Kugel eindeutig bestimmen und auch, ob sie leichter oder schwerer ist.
Bemerkung:
Ob so etwas wie Durchnummerieren von Kugeln und Vektorzuweisungen zu den Nummern, noch etwas mit Knobeln zu tun hat, erscheint mir fraglich. Man sollte es schon ohne Manipulationen an den Versuchsgegenständen hinbekommen können.
Andererseits scheint mir aus mathematischer Sicht das Aufzeigen einer besseren Strategie als der, die bisher allgemein als optimale angesehen wurde, recht interessant. Sie wäre vielleicht als normaler Artikel auch veröffentlicht, wohl aber nicht so beachtet worden.
Ich warte jetzt nur noch auf die Auflösung und hoffe, dass ich angenehm überrascht werde.
Viele Grüße
salomeMe
\(\endgroup\)
\(\begingroup\)Hallo salomeMe,
im letzten Teil meiner Aufgabe wurde nach folgendem gefragt:
-- angenommen: Die Verteilung der Kugeln ist pro Wägung stets gleich.
Man kennt nach Ablauf von W Wägungen nur den jeweiligen Ausschlag der
Balkenwaage; Beispiel :
1. Wägung: ▼ ( linke Waagschale ist schwerer, und geht nach unten )
2. Wägung: ▲ ( linke Waagschale ist leichter, und geht nach oben )
3. Wägung : ▬ ( beide Schalen sind im Gleichgewicht )
4. Wägung: ▲ ( linke Waagschale ist leichter, und geht nach oben )
etc.
Wie könnte so eine stets gleiche Verteilung der Kugeln pro Wägung aussehen, um nach W Wägungen etwa mit der Information > ▼ ▲ ▬ ▲ ….. < die >falsche Kugel< zu identifizieren, incl. Gewichtsangabe (schwerer / leichter) ?
Meine Antwort lautet:
Ja, es gibt so eine Verteilung, die zum Ziel führt:
http://matheplanet.com/matheplanet/nuke/html/uploads/9/44117_W111.jpg
http://matheplanet.com/matheplanet/nuke/html/uploads/9/44117_W222.jpg
http://matheplanet.com/matheplanet/nuke/html/uploads/9/44117_W333.jpg
http://matheplanet.com/matheplanet/nuke/html/uploads/9/44117_W444.jpg
http://matheplanet.com/matheplanet/nuke/html/uploads/9/44117_W555.jpg
Es genügt, nach 5 Wägungen den jeweiligen Ausschlag der Balkenwaage zu kennen,
um die >falsche Kugel< incl. deren Gewicht (schwerer/leichter) zu identifizieren.
Du kannst das gerne testen; es funktioniert immer.
beste Grüße
JoeM
\(\endgroup\)
\(\begingroup\)hallo joem,
wie trumpf bereits gesagt hat, fehlt der beweis dafür, dass die von dir angegebene (aber wie ebenfalls bereits gesagt wurde, allgemein bekannte) strategie optimal ist. das wäre einen artikel wert gewesen, für diskussionen ist eig das forum, hier konkret die 'knobelecke' gedacht. der satz 'Meine Strategie ist optimal; es gibt keine bessere.' ist kein solcher beweis, übrigens auch nicht die wiederholte erklärung der strategie. sie wurde als EINE lösung des wägeproblems verstanden, dass es DIE lösung sein soll, gerade nicht. auch wenn vllt niemand eine bessere strategie auf lager hat, ist das kein beweis. insofern hältst du nicht was du versprichst. falls du noch nicht weisst, worauf ich hinaus will, schau mal hier.
probier es nochmal, ich bin sicher, du kannst das besser.
bye trunx\(\endgroup\)
\(\begingroup\)Hallo JoeM,
habe die beiden Auflösungsvarianten schnell mal überflogen. Danke für die Mühe, die dafür erforderlich war. Die erste Variante scheint ja eventuell ohne Nummerierung der Kugeln auszukommen, wenn die Waagschalen geeignet für die Separierung der entsprechenden Kugelteilmengen ausgelegt sind. Schüler mögen mit dem Wägealgorithmus eventuell zu recht kommen. Ich würde lieber eine Wägung mehr machen, wenn ich mir sicher sein wollte keinen Fehler gemacht zu haben.
Werde mir heute Abend mehr Zeit nehmen und eine nicht ganz so oberflächliche Meinung zu den Lösungsvarianten bilden.
Da beide Varianten die 120 Kugel nach 2 Wägungen nicht auf 40 Kugeln einschränken, wobei schon bekannt ist, dass die abweichende Kugel leichter oder schwerer ist, hat mein Gedanke die mögliche Anzahl auf 130 Kugeln auszudehnen, keinen Sinn gehabt.
Viele Grüße
salomeMe\(\endgroup\)
\(\begingroup\)Hallo JoeM,
zu Deinem Kommentar vom Mo. 22. Februar 2016 01:06:46
A) 12 Kugeln sieht ok aus
B) 39 Kugeln sieht ok aus
C) 120 Kugeln...
1. Wägung ohne Ausschlag ok
1. Wägung mit Ausschlag
Kugeln 1 - 40 Kugeln 41 – 80 auf/ab
2.Wägung (tausche 13 Kugeln li/re, und den Rest auf einer Seite gegen neutrale Kugeln)
Kugeln 41 – 53, 14 – 40 Kugeln 1 – 13, 81 – 93
\
wohl Flüchtigkeitsfehler:
Kugeln 41 bis 53, 14 bis 40 sowie Kugeln 1 bis 13, 81 bis 107
2 a) kein Ausschlag
Kugeln 41 – 53, 14 – 40 Kugeln 1 – 13, 81 – 93 gleich
\
vererbter Flüchtigkeitsfehler (noch 3 mal):
Kugeln 41 bis 53, 14 bis 40 sowie Kugeln 1 bis 13, 81 bis 107 gleich
Folge: Eine der Kugeln 54 bis 80 ist schwer (27 Kugeln, 3 weitere Wägungen)
2 b) Ausschlag auf/ab
Kugeln 41 – 53, 14 – 40 Kugeln 1 – 13, 81 – 93 auf/ab
Kugeln 41 – 53, 14 – 40 Kugeln 1 – 13, 81 – 107 auf/ab
Folge: Eine der Kugeln 14 bis 40 ist leicht (27 Kugeln, 3 weitere Wägungen)
2 c) Ausschlag ab/auf
Kugeln 41 – 53, 14 – 40 Kugeln 1 – 13, 81 – 93 ab/auf
Kugeln 41 – 53, 14 – 40 Kugeln 1 – 13, 81 – 107 ab/auf
Folge:
Kugeln 1 – 13 Kugeln 41 – 53 auf/ab
Dies ist genau folgender Fall: 1. Wägung mit Ausschlag für B) 39 Kugeln: 3 weitere Wägungen sind erforderlich (rekursive Anwendung von A) = 12 und B) = 39 Kugeln).
Das Verfahren lässt sich somit auf jede Anzahl von Kugeln (K = 363 etc.) anwenden.
\
Diese Behauptung ist vermutlich nicht sauber bewiesen. Man müsste von (3^n -3)/2 auf (3^(n+1) -3)/2 schließen, falls man es mit Vollständiger Induktion beweisen will.
Ein Beweis dafür, dass das Verfahren für 12 Kugeln optimal ist habe ich unter folgendem Link gefunden:
http://de.math.wikia.com/wiki/Waage_und_12_Kugeln%2C_L%C3%B6sung_und_Diskussion
Ob das für n>3 aber eine optimale Strategie bleibt, ist fraglich. Aber Du wirst dort auch ein Argument dafür finden, von dem ich aber nicht 100% überzeugt bin.
Mit dem statischen Lösungsbeispiel werde ich mich nicht mehr beschäftigen. Da scheint mir auf den ersten Blick der Vorschlag von @Trumpf vom So. 21. Februar 2016 00:56:45 ein allgemeinerer Ansatz zu sein, wenn ich auch erst den Anfang davon beginne zu verstehen.
Wenn Du die Vorschläge von @trunx vom Mo. 22. Februar 2016 09:41:55 beherzigst, wirst Du künftig besser verstanden werden.
Wenn man sich intensiv und vor Allem lange mit einem mathematischen Problem beschäftigt, vergisst man mit der Zeit oft auf welchem Wege man zu den Ergebnissen gekommen ist oder man verliert das Gefühl das Wichtige vom Unwichtigen trennen zu können. Funktionierende Beispiele sind zwar gut und schön, aber schöner ist erklären zu können, wie man auf das Beispiel gekommen ist. Dann wird man von Außenstehenden manchmal auch verstanden.
Viel Erfolg beim Beweisen Deiner Aussagen!
Beste Grüße
salomeMe\(\endgroup\)
\(\begingroup\)Hallo salomeMe,
Du schreibst ... > Flüchtigkeitsfehler.... < bei N = 120 Kugeln.
Vielen Dank für Deinen Hinweis; da ist mir in der Eile eine Fehler unterlaufen; der aber keinen Einfluss auf die Gesamtlösung hat.
Natürlich müssen in beiden Schalen gleich viele Kugeln sein.
mit den besten Grüßen
JoeM
\(\endgroup\)
\(\begingroup\)Hallo salomeMe,
vielen Dank für Deinen Link (12 Kugeln, und 3 Wägungen).
Bei 12 Kugeln gibt es 24 Mögl. dafür, dass eine Kugel schwerer, oder leichter ist.
Mit 3 Wägungen kann man 3^3 – 1 = 26 Möglichkeiten abdecken (eine Möglichkeit muss man abziehen; das wäre der Fall, dass alle Kugeln gleich schwer sind ).
Nun könnte man meinen, dass man auch 13 Kugeln mit 3 Wägungen erfassen kann
(13 * 2 = 26 Möglichkeiten).
In Deinem Link wird aber bewiesen, dass das nicht geht:
Es funktioniert für N = (3^3 – 3)/2 = 12 Kugeln mit 3 Wägungen.;
Für N = 13 Kugeln kann man nach 3 Wägungen nur die >falsche Kugel< identifizieren, aber ohne Gewichtsangabe.
Da bei meinem Verfahren für N = 39, 120, 363, 1092, 3279, 9840, …. immer rekursiv auf 12, 39, 120, …. Kugeln zurückgegriffen werden muss; sollte das als Beweis ausreichen.
Ansonsten würde man in bestimmten Fällen rekursiv auf 13 Kugeln mit restlichen
3 Wägungen treffen ---> Widerspruch.
Natürlich wäre ein allgemeiner Nachweis durch Induktion schöner; ich denk mal drüber nach.
Mit besten Grüßen
JoeM
\(\endgroup\)
\(\begingroup\)Hallo salomeMe,
Du schreibst:
>Mit dem statischen Lösungsbeispiel werde ich mich nicht mehr beschäftigen<.
Das finde ich sehr schade.
Meine Meinung ist: Dies ist die beste aller Lösungen.
Die Verteilung siehe auf den 1. Blick nicht schwer aus.
Die Lösung basiert auf meiner >Rekursion<, ist aber wesentlich schwieriger herzuleiten.
Das besondere ist:
Es genügt, nach 5 Wägungen jeweils den Ausschlag der Waage zu kennen;
hier 2 Beispiele:
http://matheplanet.com/matheplanet/nuke/html/uploads/9/44117_Bild1.jpg
http://matheplanet.com/matheplanet/nuke/html/uploads/9/44117_Bild2.jpg
http://matheplanet.com/matheplanet/nuke/html/uploads/9/44117_Bild5.jpg
http://matheplanet.com/matheplanet/nuke/html/uploads/9/44117_Bild6.jpg
Ich denke, es lohnt sich, die Sache näher anzusehen.
beste Grüße
JoeM
\(\endgroup\)
\(\begingroup\)@joem: wieder wiederholst du nur zum zigsten Male dein Vorgehen und wieder 'beweist' du nur, dass das Verfahren auch für größere Kugelanzahlen FUNKTIONIERT (was beides, glaube ich, jetzt auch der Letzte verstanden hat und wirklich kein Problem mehr ist), aber immer noch nicht, dass dieses Verfahren das optimale ist. Einziger Fortschritt, den ich sehe 'Meine Meinung ist: Dies ist die beste aller Lösungen.'
Es ist schon mal eine Einsicht, dass das wirklich nur eine Meinung ist.\(\endgroup\)
\(\begingroup\)Holla JoeM,
schon wieder hast Du Dir so viel Arbeit gemacht.
Zur optimalen Strategie:
Dass sie mit 12 Kugeln eine optimale bezügliche der Wägeanzahl ist, war mir klar. Mir ist auch einigermaßen klar, dass bei größeren Kugelanzahlen eine optimale Strategie bezügliche der Wägeanzahl maximal eine Kugel mehr erledigen könnte als Deine. Es müsste also gezeigt werden, dass für größere Anzahlen, diese Kugel mehr nicht möglich ist.
Deinen Hinweis "(eine Möglichkeit muss man abziehen; das wäre der Fall, dass alle Kugeln gleich schwer sind)" verstehe ich nicht, da dieser Fall nach Voraussetzung nicht eintreten kann.
Zum Beweis für die unendlich vielen großen Kugelanzahlen:
Ich denke ein Induktionsbeweis ist recht leicht zu führen - eigentlich nur eine Verallgemeinerung Deiner rückwärts gerichteten Begründungen in die andere Richtung.
Zu den statischen Beispielen:
Wenn ich mit @Trumpf's Lösungsvorschlag abgeschlossen habe, werde ich prüfen, ob Deine Beispiele äquivalent sind. Wenn aus den 5 Wägeresultaten per Formel die Nummer der Kugel zu ermitteln wäre, wie es bei @Trumpf's Lösungsvorschlag der Fall sein soll, wäre es gut Deine Formel zu erfahren.
Viele Grüße
salomeMe
\(\endgroup\)
\(\begingroup\)Hallo salomeMe,
Du schreibst:
> Zu den statischen Beispielen:
Wenn ich mit @Trumpf's Lösungsvorschlag abgeschlossen habe, werde ich prüfen, ob Deine Beispiele äquivalent sind. Wenn aus den 5 Wägeresultaten per Formel die Nummer der Kugel zu ermitteln wäre, wie es bei @Trumpf's Lösungsvorschlag der Fall sein soll, wäre es gut Deine Formel zu erfahren. <
Bitte melde Dich.
Mich würde Deine Meinung interessieren, wenn Du Deine Analyse von Trumps Lösungsvorschlag gecheckt hast.
beste Grüße
JoeM
\(\endgroup\)
\(\begingroup\)"Mich würde Deine Meinung interessieren, wenn Du Deine Analyse von Trumps Lösungsvorschlag gecheckt hast."
http://matheplanet.com/matheplanet/nuke/html/uploads/9/44668_Unbenannt.jpg\(\endgroup\)
\(\begingroup\)Hallo Trumpf,
Du schreibst:
"Mich würde Deine Meinung interessieren, wenn Du Deine Analyse von Trumps Lösungsvorschlag gecheckt hast."
Pardon !
Diesen Vorschlag kenne ich nicht; es war auch keine Absicht, Deinen Namen falsch zu schreiben.
viele Grüße
JoeM\(\endgroup\)
\(\begingroup\)Hallo salomeMe
siehe folgenden Link:
http://de.math.wikia.com/wiki/Waage_und_12_Kugeln,_L%C3%B6sung
was sagt Dir das ?
viele Grüße
JoeM\(\endgroup\)
\(\begingroup\)Hallo JoeM,
danke für den Link:
http://de.math.wikia.com/wiki/Waage_und_12_Kugeln,_L%C3%B6sung
Dessen Inhalt sagt mir, dass mir unklar ist, wie die 3 Kugelnummer-Konstelationen für die 3 Wägungen zustande gekommen sind - wohl zufällig. Die Auswertung der Wägungen erinnert an die von @Trumpf vorgeschlagene. Sie ist aber analog zu den 3 Kugelnummer-Konstelationen bestimmt schwerer nachvollziehbar, als @Trumpf's Auswertung. Ich vermute der Verfasser hat alle 24 Fälle durchgerechnet und dann die Lösungsstrategie so hingebogen, dass sie funktioniert.
Dann sagt sie mir natürlich noch, dass es eine große Anzahl geeigneter Kugelkonstellationen für die statische Lösung solcher Wägeprobleme gibt. Eventuell ist diese Anzahl identisch oder größer als die der dynamischen Lösungsvarianten.
Dahingegen ist @Trumpf's Strategie von Anfang bis Ende eindeutig festgelegt und für 3 bis 5 Wägungen, falls das Script keine Fehler enthält als richtig geprüft.
Ist der Induktionsbeweis für das dynamische Verfahren schon fertig? Der würde mich etwas interessieren. Auch von der allgemeinen Optimalität der dynamischen Wägelösung bin ich noch nicht überzeugt - lässt sich das Argument für das 12-Kugelproblem, auch auf die größeren Anzahlen ausweiten?
Viele Grüße
salomeMe\(\endgroup\)
\(\begingroup\)Hallo salomeMe,
zu Deiner letzten Mitteilung:
1) Ich hab mir die Lösung von Trumpf, sowie die Lösung nach dem Link, den
ich Dir gesendet habe, nur kurz angesehen.
Ich vermute, dass beide Verfahren ähnlich ablaufen.
2) einen Induktionsbeweis habe ich mir noch nicht überlegt.
3) was meinst Du mit:
>Auch von der allgemeinen Optimalität der dynamischen Wägelösung bin ich noch nicht überzeugt - lässt sich das Argument für das 12-Kugelproblem, auch auf die größeren Anzahlen ausweiten?<
viele Grüße
JoeM \(\endgroup\)
\(\begingroup\)Hollo JoeM,
zu 1) eventuell steckt in der verlinkten Lösung auch ein Fehler. Man müsste alle 24 Fälle testen, um das heraus zu bekommen.
zu 3) Auf jeden Fall kann man bei (3^n-3)/2 +1 Kugeln für die in den n Wägungen nicht berücksichtigte Kugel noch zusätzlich herausbekommen ob sie normal oder abweichend ist.
Unter
http://de.math.wikia.com/wiki/Waage_und_12_Kugeln%2C_L%C3%B6sung_und_Diskussion
war ein Beweis der Optimalität des 12-Kugel-Problems angegeben, obwohl natürlich auch hier über eine 13-te Kugel eine Teilaussage getroffen werden kann.
Gruß
salomeMe\(\endgroup\)
\(\begingroup\)Hallo Allerseits,
ein Paar Gedanken zur Strategie von @Trumpf:
1.) Es wird davon ausgegangen, dass sich jede der (3^n-3)/2 Kugelnummern {1, 2, 3, ... , (3^n-3)/2} eineindeutig als Summe von verschiedenen positiven oder negativen Dreierpotenzen <= 3^n darstellen lässt. Dass müsste bewiesen werden. Da es nicht meine Idee war, versuche ich es aber nicht.
2.) Die Bildungsvorschrift der n-komponentigen Vektoren zu den nummerierten Kugeln spiegelt diese eineindeutige Abbildung wieder, falls sich daraus wirklich genau die Kugelnummern ergeben (falls 1. nicht bewiesen wird, sollte wenigstens das bewiesen werden)
3.) Die Bildungsvorschrift der Vektoren zu den Kugeln macht auch klar (falls 2. gilt), dass in jeweils genau (3^n-3)/6 der Kugelnummern eine bestimmte Dreierpotenz <= 3^n entweder mit positiven oder mit negativem Vorzeichen enthalten ist. Das ist die Grundlage für die Bildung der 2n Wägemengen.
4.) Jede Kugel wird so oft gewogen, wie sie von 0 abweichende Vektorkomponenten hat. Genauer nur bei den i-ten Wägungen bei denen die entsprechenden i-ten Vektor-Komponenten der Kugel von 0 abweichen. Dabei wird auch noch entsprechend des Vorzeichens der Vektor-Komponente die Kugel bei - in die linke und bei + in die rechte Waagschale gelegt. Nur die abweichende Kugel bestimmt den Ausschlag der Waage. Damit lässt sich @Trumpf's Bestimmung der Kugelnummer eindeutig herleiten und mit Hilfe des Kugelvorzeichens (vor dem Vektor) und des Vorzeichens der Summe der Wichtungen der Wägeresultate lässt sich auch bestimmen, ob sie leichter oder schwerer ist.
Gruß
salomeMe\(\endgroup\)
\(\begingroup\)Hallo salomeMe,
ich habe im Internet einen interessanten Artikel gefunden, der anscheinend einen allg. Beweis für folg. Behauptung liefert:
Mit W Wägungen ist es möglich, aus (3^W - 3)/2 Kugeln die >falsche Kugel< zu identifizieren, incl. Gewichtsangabe.
Siehe dazu folgenden Link:
http://www.brodo.de/pub/kugelproblem.pdf
viele Grüße
JoeM
\(\endgroup\)
\(\begingroup\)Hi JoeM und salomeMe,
externe Links könnt ihr wie folgt angeben:
\sourceon html
LINK_TEXT_ZUM_ANZEIGEN
\sourceoff
Einfach unten unter Eingabehilfen auf "[Link extern]" klicken, dann erspart ihr euch auch das Schreiben des html-Codes. Die LINK_TEXT-Unterstreichung (u /u) kann man auch löschen oder entsprechend verändern.
Gruß, Slash\(\endgroup\)
\(\begingroup\)Hi Slash,
vielen Dank für Deinen Tipp.
Klingt auf den 1. Blick schwieriger, als die Aufgabe 😄
Vielleicht könntest Du mal einen weiteren Lösungsvorschlag für die Aufgabe
anbieten ?!
viele Grüße
JoeM\(\endgroup\)
\(\begingroup\)Hallo JoeM,
danke für den Link zu dem PDF von Dominik Brodowski, das dieser schon 1999 oder 2000 als Schüler verfasst hat. Wahrscheinlich war zu dieser Zeit dieses Wägeproblem in Mode. Die ersten beiden Seiten deuten darauf hin, dass Du Dir keine Gedanken mehr um die gewünschten Beweise machen musst, da sie in den 6 Seiten geführt werden - bei Gelegenheit werde ich versuchen sie zu verstehen.
Falls Du wieder mal ein Problem zum Erraten stellst, solltest Du die vollständigen und genauen Voraussetzungen nennen - in diesem Fall z.B. dass die Kugeln eindeutig an ihren Nummern zu erkennen sind. Außerdem wäre es gut, wenn Dir die Mathematik, die dahinter steckt, in möglichst eleganter und einleuchtender Form bekannt ist.
Trotzdem war diese Raterunde recht lehrreich für mich. Nur so viel Zeit wollte ich eigentlich nicht damit verbringen, zumal mir die praktische Relevanz sehr fraglich erscheint.
Viele Grüße
salomeMe\(\endgroup\)
\(\begingroup\)Hallo salomeMe,
Du schreibst:
>Falls Du wieder mal ein Problem zum Erraten stellst, solltest Du die vollständigen und genauen Voraussetzungen nennen - in diesem Fall z.B. dass die Kugeln eindeutig an ihren Nummern zu erkennen sind. Außerdem wäre es gut, wenn Dir die Mathematik, die dahinter steckt, in möglichst eleganter und einleuchtender Form bekannt ist.<
Dazu:
Geh doch nicht so streng mit mir um. 😄
Ich meine: Bei dieser Aufgabe sollte man gerade NICHT angeben, dass die Kugeln eindeutig an ihren Nummern erkennbar sind. Es ist Teil der Aufgabe, herauszufinden, ob das notwendig ist, oder nicht.
Und: Ich denke schon, dass ich die Mathematik, die hinter der Aufgabe,
beginnend mit 12, 39, 120 Kugeln, .... steckt, kenne.
Hinter den einzelnen Schritten in meiner Lösung per Rekursion von 12 auf 39, auf 120 Kugeln, usw. steckt ein System, das man auf den 1. Blick nicht sieht.
(vielleicht hast Du es erkannt ?)
Zugegeben: Dieses System habe ich in meiner Lösung nicht erläutert.
Ich habe auch in meiner >statischen Lösung< keinen Lösungsweg angegeben. Es sieht vielleicht aus, als wäre das leicht herstellbar; dem ist aber nicht so:
Meine >statische Lösung< kann man aus meiner Sicht nur herstellen, wenn man mein >Prinzip der Rekursion< konsequent anwendet; und das ist nicht >ohne<
mit besten Grüßen
JoeM
\(\endgroup\)
\(\begingroup\)Meine Lösung mit maximal 5 Wägungen
\hideon
Bedingung 1: Wenn links und rechts gleich schwer, fahre mit den Kugeln neben der Waage fort, sonst fahre mit den schwereren Kugeln fort.
1.Wägung: 40 Kugeln links, 40 Kugeln rechts, 40 Kugeln neben der Waage
2.Wägung: 13 Kugeln links, 13 Kugeln rechts, 14 Kugeln neben der Waage
3.Wägung (vorher 13 Kugeln): 4 Kugeln links, 4 Kugeln rechts, 5 neben der Waage
3.Wägung (vorher 14 Kugeln): 4 Kugeln links, 4 Kugeln rechts, 6 neben der Waage
4.Wägung (vorher 4 Kugeln): 2 Kugeln links, 2 Kugeln rechts, 0 neben der Waage
4.Wägung (vorher 5 Kugeln): 2 Kugeln links, 2 Kugeln rechts, 1 neben der Waage
4.Wägung (vorher 6 Kugeln): 2 Kugeln links, 2 Kugeln rechts, 2 neben der Waage
5.Wägung: 1 Kugel links, 1 Kugel rechts
\hideoff
Edit: Gilt nur für den Fall, dass die schwerere/leichter Kugel gesucht wird. Also wenn bekannt ist, dass die Falsche mehr/weniger wiegt!\(\endgroup\)
\(\begingroup\)Hallo Tobias_Meyer,
Du schreibst in Deiner Lösung zu Anfang:
>Bedingung 1: Wenn links und rechts gleich schwer, fahre mit den Kugeln neben der Waage fort, sonst fahre mit den schwereren Kugeln fort.
1.Wägung: 40 Kugeln links, 40 Kugeln rechts, 40 Kugeln neben der Waage.<
Dazu folgendes:
Es geht darum, die >falsche Kugel< zu identifizieren, incl. der Angabe, ob diese Kugel leichter/schwerer ist.
Fall 1:
1.Wägung: 40 Kugeln links, 40 Kugeln rechts; die Waage rechts geht nach unten.
Das bedeutet:
a) in der rechten Waagschale ist eine Kugel, die schwerer ist, oder
b) in der linken Waagschale ist eine Kugel, die leichter ist.
Es ist aber NICHT bekannt, ob die >falsche Kugel< leichter, oder schwerer ist, als alle anderen Kugeln.
Somit kannst Du NICHT >mit den schwereren Kugeln< weiterfahren.
In der anderen Waagschale könnte auch die >leichtere Kugel< sein.
Fall 2:
1.Wägung: 40 Kugeln links, 40 Kugeln rechts; Waage im Gleichgewicht.
Dann allein >mit den 40 Kugeln neben der Waage< weiterzuarbeiten, funktioniert nicht. Mit weiteren 4 Wägungen die >falsche Kugel< aus 40 Kugeln zu identifizieren, geht nicht; das geht nur mit maximal (3^4 - 3)/2 = 39 Kugeln.
viele Grüße
JoeM
\(\endgroup\)
\(\begingroup\)Ok - wer lesen kann, ist klar im Vorteil 😉
Hatte die Aufgabe nicht richtig gelesen. Wenn nur bekannt ist, dass eine Kugel ungleich dem Gewicht der anderen ist, bleibt wohl nur deine komplexere Lösung vom 23.Feb...\(\endgroup\)
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Printer-friendly version
Gegeben sind N = 120 Kugeln, die alle gleich aussehen. Eine Kugel ist schwerer, oder leichter, als alle anderen Kugeln. Mit einer Balkenwaage soll die >falsche Kugel< identifiziert werden incl. der Angabe, ob diese Kugel schwerer, oder leichter ist, als alle anderen Kugeln.
-- wie viele Wägungen W sind minimal erforderlich ?
-- wie laufen diese Wägungen ab ? 
Get link to this article
Comments
Für diesen Artikel gibt es keine pdf-Datei
Dieser Artikel ist im Verzeichnis der 
