Eine Waage, fuenf Kugeln
g.j.wo...@math.utwente.nl
Vor Dir liegen fuenf Kugeln mit paarweise verschiedenem Gewicht,
und eine Balkenwaage.
Du sollst die Kugeln nach steigendem Gewicht anordnen,
und dazu moeglichst wenige Waegevorgaenge durchfuehren.
[Es gilt die Timwi-Klausel]
--
GJ Woeginger, University of Twente
Gerhard Woeginger
Vor Dir liegen fuenf Kugeln mit paarweise verschiedenem Gewicht,
und eine Balkenwaage.
Du sollst die Kugeln nach steigendem Gewicht anordnen,
und dazu moeglichst wenige Waegevorgaenge durchfuehren.
[Es gilt die Timwi-Klausel]
_____________________________________________________________
Gerhard J. Woeginger http://www.math.utwente.nl/~woeginge/
Matthias Gietl
>
> Vor Dir liegen fuenf Kugeln mit paarweise verschiedenem Gewicht,
> und eine Balkenwaage.
>
> Du sollst die Kugeln nach steigendem Gewicht anordnen,
> und dazu moeglichst wenige Waegevorgaenge durchfuehren.
>
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
also rein vom gefühl her würde ich erst kugeln 1 und 2 wiegen, dann die
schwerere der beiden gegen 3. wenn 3 schwerer ist, dann 3 gegen 4, sonst
1/2 gegen 4. wenn 4 schwerer ist, 4 gegen 5, wenn 1/2/3 schwerer ist als
4 dann 1/2/3 gegen 5. dann habe ich nach 4 wägevorgängen schonmal die
schwerste kugel eliminiert. bleiben noch 4 kugeln, für die ich 3 versuche
brauche um die schwerste zu finden. dann noch 3 kugeln mit 2 versuchen
und 2 kugeln mit 1. macht summa summarum 10 wägevorgänge. aber das war
jetzt ganz unmathematisch und mit boolscher algebra geht sicherlich mit
3,5 versuchen :-).
matthias
Burkart Venzke
>Gerhard Woeginger <gwo...@figipc56.tu-graz.ac.at> wrote:
>
>>
>> Vor Dir liegen fuenf Kugeln mit paarweise verschiedenem Gewicht,
>> und eine Balkenwaage.
>>
>> Du sollst die Kugeln nach steigendem Gewicht anordnen,
>> und dazu moeglichst wenige Waegevorgaenge durchfuehren.
>>
>..
>..
>..
>..
>..
>..
>..
>..
>..
>..
>
>..
>..
>..
>..
>..
>..
>..
>...
>
>..
>..
>..
>also rein vom gefühl her würde ich erst kugeln 1 und 2 wiegen, dann die
>schwerere der beiden gegen 3. wenn 3 schwerer ist, dann 3 gegen 4, sonst
>1/2 gegen 4. wenn 4 schwerer ist, 4 gegen 5, wenn 1/2/3 schwerer ist als
>4 dann 1/2/3 gegen 5. dann habe ich nach 4 wägevorgängen schonmal die
>schwerste kugel eliminiert. bleiben noch 4 kugeln, für die ich 3 versuche
>brauche um die schwerste zu finden. dann noch 3 kugeln mit 2 versuchen
>und 2 kugeln mit 1. macht summa summarum 10 wägevorgänge. aber das war
>jetzt ganz unmathematisch und mit boolscher algebra geht sicherlich mit
>3,5 versuchen :-).
Also unter 7 Versuche geht's sicher nicht:
Bei 5 Kugel haben wir 5! = 120 Reihenfolgen.
Die Waage zeigt uns leichter oder schwerer an (gleich ist ein
zufälliger/uninteressanter(?) Ausnahmefall), so daß man mit 7 Wägungen auf 128
Möglichkeiten kommt.
Bleibt nur die Frage, wie man diese möglichst gut nutzt.
Mehrere Kugeln gleichzeitig macht wohl keinen Sinn, weil eine
Kugel alle anderen dominieren kann; also einzeln...
Das ganze erinnert mich sehr an Sortieren von Zahlen, bei dem ein Baum i.a.
optimal ist. Binäres Einfügen klingt hier recht schnell. Also...
[1. Wägung] 1. gegen 2.: Eine ist schwerer.
A>B [stellt eine Möglichkeit bzw. das Wissen um eine ">"-Beziehung dar]
[2] 3. gegen A und
[3] notfalls auch gegen B =>
A>B>C
[4] 4. gegen B und
[5] 4. gegen A oder C =>
A>B>C>D
[6] 5. gegen B
[7] 5. gegen A oder C und
[8] 5. notfalls gegen D
=> So komme ich auf 8 Wägungen. Hm, ob auch 7 gehen?
Versuch:
[1] A>B [noch 60 Möglichkeiten]
[2] C>D [noch 30 Möglichkeiten(?)]
[3] B>E oder E>B
[4] und ggf. E>A
Wir haben jetzt A>B>E und C>D, das sind noch 10 Möglichkeiten und damit zu viel
für 3 Versuche.
Also so gehen 7 nicht. Mit einem Programm könnte man checken, ob es vielleicht
doch eine 7-er-Möglichkeit gibt, aber lieber lasse ich mir die Auflösung sagen.
:)
Und??
Viele Grüße,
Burkart
--
__________________________________________________________
News suchen, lesen, schreiben mit http://newsgroups.web.de
Frank Weinberg
>Also unter 7 Versuche geht's sicher nicht:
>Bei 5 Kugel haben wir 5! = 120 Reihenfolgen.
>Die Waage zeigt uns leichter oder schwerer an (gleich ist ein
>zufälliger/uninteressanter(?) Ausnahmefall), so daß man mit 7 Wägungen auf 128
>Möglichkeiten kommt.
>
>Bleibt nur die Frage, wie man diese möglichst gut nutzt.
>Mehrere Kugeln gleichzeitig macht wohl keinen Sinn, weil eine
>Kugel alle anderen dominieren kann; also einzeln...
>Das ganze erinnert mich sehr an Sortieren von Zahlen, bei dem ein Baum i.a.
>optimal ist. Binäres Einfügen klingt hier recht schnell. Also...
Mit binärem Einfügen liegt der ungünstigste Fall vor, wenn die Kugeln schon
sortiert sind. Dann hast Du 10 Vergleiche.
Mit einem Tournament-Sort kann man die 7 Versuche anscheinend einhalten,
aber ich habe gerade keine Zeit, das im Detail zu überprüfen.
Frank
--
ACK. Es gibt wohl Leute, die nichts anderes mehr tun, als vor dem Bildschirm
zu sitzen. Genau diese Leute sollten den Rechner mal ausknipsen und sich mal
draussen (dahin kommt man durch die sogenannte Haustuere, das ist dort, wo
der Mann vom Pizza-Service immer klingelt) umzuschauen. Frank Künzel in dag°
Uwe Weiss
"Gerhard Woeginger" <gwo...@figipc56.tu-graz.ac.at> wrote in message
news:9pa9sq$d48$1...@fstgss02.tu-graz.ac.at...
>
> Vor Dir liegen fuenf Kugeln mit paarweise verschiedenem Gewicht,
> und eine Balkenwaage.
>
> Du sollst die Kugeln nach steigendem Gewicht anordnen,
> und dazu moeglichst wenige Waegevorgaenge durchfuehren.
>
das Rätsel ist eigentlich sehr interessant. Dass bisher kein Lösungsversuch
erfolgt ist, liegt wohl daran, dass es auch recht schwierig ist?
Ich glaube nicht, dass ich eine optimale Lösung gefunden habe; die Lösung
würde mich aber brennend interessieren. Nunja, eins steht - für den
Informatiker - definitiv fest: jedes Verfahren benötigt mindestens
O(n*log(n)) Vergleiche; was konkret nix aussagt.
Naiver - und deshalb wenig Erfolg versprechender Ansatz:
bei 1 Kugel ist die Lösung trivial: 0 Waegevorgaenge
bei 2 Kugeln: 1 Vorgang
bei 3 Kugeln a,b,c: a/b -> a<b; b/c -> b<c (worst case); c/b liefert
Gewissheit
bei 4 Kugeln:
1. a/b -> a<b
2. c/d -> c<d
also: leichteste Kugel ist a oder c, schwerste b oder d
3. a/c -> a<c
4. b/d -> b<d
5. leichteste und schwerste Kugel sind bekannt: axxd; die 5. Waegung (c/d)
liefert endgültige Gewissheit.
Wir halten fest: 1 Kugel: 0, 2:1, 3:3, 4:5, 5:???
7 drängt sich auf ;) (Oder 8?)...
Mit 8 Waegungen krieg ich's immer hin. Erstmal 4 beliebige Kugeln ordnen,
und dann die 5. mit maximal 3 weiteren Wiegevorgaengen ("binaere Suche")
einordnen.
Geht aber _bestimmt_ schneller, oder?
Ein gespannter
-Uwe-
Gerhard Woeginger
#
# "Gerhard Woeginger" <gwo...@figipc56.tu-graz.ac.at> wrote in message
# news:9pa9sq$d48$1...@fstgss02.tu-graz.ac.at...
#>
#> Vor Dir liegen fuenf Kugeln mit paarweise verschiedenem Gewicht,
#> und eine Balkenwaage.
#>
#> Du sollst die Kugeln nach steigendem Gewicht anordnen,
#> und dazu moeglichst wenige Waegevorgaenge durchfuehren.
#>
# Hallo Gerhard,
#
# das Rätsel ist eigentlich sehr interessant. Dass bisher kein Lösungsversuch
# erfolgt ist, liegt wohl daran, dass es auch recht schwierig ist?
# Ich glaube nicht, dass ich eine optimale Lösung gefunden habe; die Lösung
# würde mich aber brennend interessieren. Nunja, eins steht - für den
# Informatiker - definitiv fest: jedes Verfahren benötigt mindestens
# O(n*log(n)) Vergleiche; was konkret nix aussagt.
#
# Naiver - und deshalb wenig Erfolg versprechender Ansatz:
# bei 1 Kugel ist die Lösung trivial: 0 Waegevorgaenge
# bei 2 Kugeln: 1 Vorgang
# bei 3 Kugeln a,b,c: a/b -> a<b; b/c -> b<c (worst case); c/b liefert
# Gewissheit
# bei 4 Kugeln:
# 1. a/b -> a<b
# 2. c/d -> c<d
# also: leichteste Kugel ist a oder c, schwerste b oder d
# 3. a/c -> a<c
# 4. b/d -> b<d
# 5. leichteste und schwerste Kugel sind bekannt: axxd; die 5. Waegung (c/d)
# liefert endgültige Gewissheit.
#
# Wir halten fest: 1 Kugel: 0, 2:1, 3:3, 4:5, 5:???
# 7 drängt sich auf ;) (Oder 8?)...
# Mit 8 Waegungen krieg ich's immer hin. Erstmal 4 beliebige Kugeln ordnen,
# und dann die 5. mit maximal 3 weiteren Wiegevorgaengen ("binaere Suche")
# einordnen.
# Geht aber _bestimmt_ schneller, oder?
Ja, es geht noch (ein wenig) besser.
Kurt Stege
wesentliche gesagt.
Burkhart hat nachgewiesen, daß jede Strategie
im ungünstigsten Fall mindestens 7 Wägungen
braucht: Jede Wägung bringt nur 1 Bit Ergebnis;
die Gewichte sind paarweise verschieden, so daß
ein Gleichgewicht nicht eintritt, und es gibt
120 verschiedene Ausgangssituationen, mit 6 Wägungen
kann man aber nur 2^6 = 64 Situationen unterscheiden.
Burkhart hat auch darauf hingewiesen, daß die auf
dem zweiten Blick naheliegende Strategie, mehrere
Kugeln zusammen auf eine Waagschale zu legen,
nicht weiterhilft (dies wird übrigends auch schon
in obiger Argumentation benötigt, da sonst doch
Gleichgewichte auftreten können).
Und Uwe festgestellt, daß die ganze Aufgabe
identisch zu einem wohlbekannten Problem der
Informatik ist, nämlich dem Sortieren eines
Arrays mit in diesem Fall 5 Elementen.
Dann war er allerdings nicht mehr konsequent
genug und hat etwas ähnliches wie Mergesort
beschrieben, und kamm auf 8 Vergleiche/Wägungen.
Quicksort allerdings braucht, glaube ich,
im worst-case auch mehr als 7 Wägungen.
Hier ist ein Sortierverfahren, daß bei genau
fünf Kugeln mit höchstens sieben Wägungen auskommt:
Vergleiche a mit b. ObdA sei a < b.
Vergleiche d mit e. ObdA sei d < e.
Vergleiche a mit d. ObdA sei a < d.
(Für Leser, die "oBdA", "ohne Beschränkung der
Allgemeinheit", nicht mögen: Nimm zwei Kugeln
und bestimme die leichtere. Nimm zwei weitere Kugeln
und bestimme von denen die leichtere. Vergleiche
dann die beiden leichteren Kugeln. Die leichtere
davon nenne ich a, die schwerere von den leichten
nenne ich d. Die Kugel, die schwerer als d war,
heißt e. Die Kugel, die schwerer als a war, heißt
d. Die letzte Kugel, die noch gar nicht gewogen
wurde, heißt c.)
Nun ist also a < d < e. Und wir benötigen für
später noch: a < b. Und das ganze mit nur drei
Wägungen.
Nun sortieren wir c in die Liste ein. Wir vergleichen
also c mit dem mittleren Element d, und je nach
Ergebnis anschließend noch mit a bzw. e. Das waren
fünf Wägungen.
Wir haben also die vier Kugeln a, c, d und e nach
Gewicht sortiert.
Nun haben wir noch die Kugel b, von der wir aber
schon wissen, daß sie schwerer als a ist. Es sind
(außer b) noch zwei oder drei Kugeln schwerer als
a, nämlich auf jeden Fall d und e, womöglich auch c.
Von diesen drei Kugeln suchen wir uns die
"mittelschwere" aus, vergleichen diese mit b, und
je nach Ergebnis danach mit der danebenliegenden.
Nund ist auch b eingereiht, und alle fünf Kugeln
sind nach Gewicht sortiert.
Wenn man zweimal Glück hatte, nämlich wenn c noch
leichter als a war (1/5 aller Fälle), und wenn
die sechste Wägung richtig rum war (1/3 aller Fälle),
kommt man sogar mit sechs Wägungen aus (1/15 aller Fälle).
Die durchschnittliche Anzahl aller Wägungen mit dieser
Strategie liegt also bei 7 - 1/15 = 6.9333 Wägungen.
(Wird die Forderung, maximal 7 Wägungen aufgehoben,
könnte die optimale Strategie mit durchschnittlich
log2(120) = 6.9069 Wägungen auskommen, aber danach
war ja nicht mehr gefragt.)
Gruß,
Kurt.
Gerhard Woeginger
# Eigentlich haben Burkart und Uwe schon alles
# wesentliche gesagt.
#
# Burkhart hat nachgewiesen, daß jede Strategie
# im ungünstigsten Fall mindestens 7 Wägungen
# braucht: Jede Wägung bringt nur 1 Bit Ergebnis;
# die Gewichte sind paarweise verschieden, so daß
# ein Gleichgewicht nicht eintritt, und es gibt
# 120 verschiedene Ausgangssituationen, mit 6 Wägungen
# kann man aber nur 2^6 = 64 Situationen unterscheiden.
[... deleted ...]
# Wenn man zweimal Glück hatte, nämlich wenn c noch
# leichter als a war (1/5 aller Fälle), und wenn
# die sechste Wägung richtig rum war (1/3 aller Fälle),
# kommt man sogar mit sechs Wägungen aus (1/15 aller Fälle).
# Die durchschnittliche Anzahl aller Wägungen mit dieser
# Strategie liegt also bei 7 - 1/15 = 6.9333 Wägungen.
#
# (Wird die Forderung, maximal 7 Wägungen aufgehoben,
# könnte die optimale Strategie mit durchschnittlich
# log2(120) = 6.9069 Wägungen auskommen, aber danach
# war ja nicht mehr gefragt.)
Ja, das ist die korrekte Loesung.
Ich glaub nicht, dass die bestmoegliche durchschnittliche
Anzahl bekannt ist.
Die untere Schranke log_2(120) = 6.9069 impliziert, dass
die durchschnittliche Anzahl mindestens 829/120 = 6.90833
ist.
Deine Strategie verwendet 832/120 = 6.93333 Waegungen.
Es bleiben also noch die vier Moeglichkeiten 829/120,
830/120, 831/120, 832/120 uebrig.
-Gerhard