Kniffliges Problem mit 8 Kugeln und einer Waage !
DelTotti
Hier das Problem:
8 Kugeln und eine Waage (so eine alte Waage wie im Sternzeichen, keine
digitale !)
Eine der 8 Kugeln ist schwerer ODER leichter als die übrigen 7. Aber
man weiß es nicht genau ! Ansonsten sehen alle Kugeln gleich aus.
Wie bekomme ich heraus, welche Kugel es ist, wobei ich nur 3 (in
Worten: DREI) mal wiegen darf !
Ich bin gespannt auf eine Lösung...(ich kenne sie selber nicht!) :-)
Thomas Mautsch
> Hier das Problem:
> 8 Kugeln und eine Waage (so eine alte Waage wie im Sternzeichen, keine
> digitale !)
> Eine der 8 Kugeln ist schwerer ODER leichter als die übrigen 7. Aber
> man weiß es nicht genau ! Ansonsten sehen alle Kugeln gleich aus.
>
> Wie bekomme ich heraus, welche Kugel es ist, wobei ich nur 3 (in
> Worten: DREI) mal wiegen darf !
Steht im F.A.Q.
http://www.informatik.uni-oldenburg.de/~tjark/dsm/
David Kastrup
Mit dreimal wiegen kriegst Du das sogar für 12 Kugeln raus.
--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
Björn Freitag
"David Kastrup" <d...@gnu.org> schrieb im Newsbeitrag
news:x5vfvbw...@lola.goethe.zz...
Stimmt nicht sogar für 15 Kugeln
David Kastrup
Angesichts dessen, das bei drei Wiegungen mit jeweils 3 möglichen
Ergebnissen 27 Kombinationen zustande kommen können, und das eine von
15 Kugeln entweder schwerere oder leichtere Kugel uns insgesamt 30 zu
differenzierende Fälle liefert, wirst Du meine Skepsis verstehen.
bigmack
die 3 Wiegungen ausreichen, man muss nur immer schön in 3 gleiche
Häufchen aufteilen und 2 davon wiegen.
David Kastrup
Ich liebe Leute, die weder in der Lage sind, eine Aufgabe zu lesen
noch einen Kommentar zu verstehen, und dennoch ihren Senf dazugeben
müssen. Mit 27 Kugeln, von denen eine leichter oder schwerer sein
kann, hast Du 54 Zustände, die du differenzieren müßtest.
Viel Spaß. Bei der ersten Wiegung senke sich die Waage auf einer
Seite. Jetzt hast Du entweder eine schwerere Kugel unter den linken
9, oder eine leichtere unter den rechten 9. Und dann? Wie wirst Du
jetzt mit zwei Wägungen 18 Zustände auseinanderhalten können?
Michael Kauffmann
> "Björn Freitag" <bjoern...@arcor.de> writes:
>
>> > delt...@hotmail.com (DelTotti) writes:
>> > > Eine der 8 Kugeln ist schwerer ODER leichter als die übrigen 7.
>> > >
>> > > Wie bekomme ich heraus, welche Kugel es ist, wobei ich nur 3 (in
>> > > Worten: DREI) mal wiegen darf !
>> >
>> sogar für 15 Kugeln
>
> Angesichts dessen, das bei drei Wiegungen mit jeweils 3 möglichen
> Ergebnissen 27 Kombinationen zustande kommen können, und das eine von
> 15 Kugeln entweder schwerere oder leichtere Kugel uns insgesamt 30 zu
> differenzierende Fälle liefert, wirst Du meine Skepsis verstehen.
Gefragt ist nur, welche Kugel abweicht, nicht wie.
Michael Kauffmann
David Kastrup
Na und? Die einzige Möglichkeit, diesen Zustand nicht unterscheiden
zu können, ist wenn ich dreimal Gleichstand an der Waage hatte.
Ansonsten weiß ich zwangsweise, _wenn_ die Kugel herausgefunden
wurde, auch ob sie leichter oder schwerer war. Das heißt, daß ich
bei 26 Wägungensergebnissen einen von 30 Zuständen bestimmt habe, und
bei einem Wägungsergebnis einen von 15 Zuständen bestimmt habe.
Damit muß ich im Schnitt aus 3 Wägungen immer noch 265/9 > 27
Zustände bestimmen.
Aber wenn Du so schlau bist, wirst Du uns ja das Schema vorführen
können.
Greiff
da was darüber?
Rainer Lachner
Greiff schrieb:
>
> Wie sieht's eigentlich mit 13 Kugeln aus? Weiß man
> da was darüber?
Wähle eine von den dreizehn aus und lege sie beiseite.
Unter den übrigen zwölf versuchst Du, eine zu finden, die abweicht.
Gelingt Dir das, bist Du fertig und weißt sogar ob sie leichter oder
schwerer ist.
Gelingt Dir das nicht, ist die 13. Kugel die Abweichlerin. In diesem
Fall weißt Du natürlich nicht ob sie leichter oder schwerer ist.
DelTotti
Vielen Dank für die rege Beteiligung !
Eigentlich ist in der Aufgabe die Rede von 8 Kugeln und leider wurde
bisher immer noch kein Schema dargestellt mit dem das Problem mit drei
Wiegungen gelöst werden könnte...Es ist nur gefragt, welche Kugel
einen Gewichtsunterschied hat, es muß nicht bestimmt werden, ob sie
leichter oder schwerer ist.
Alois Steindl
DelTotti schrieb:
>
> Vielen Dank für die rege Beteiligung !
> Eigentlich ist in der Aufgabe die Rede von 8 Kugeln und leider wurde
> bisher immer noch kein Schema dargestellt mit dem das Problem mit drei
> Wiegungen gelöst werden könnte...Es ist nur gefragt, welche Kugel
> einen Gewichtsunterschied hat, es muß nicht bestimmt werden, ob sie
> leichter oder schwerer ist.
Hallo,
auf die FAQ wurdest du ja schon verwiesen. Was hindert dich daran, die
Lösung dort zu suchen?
Alois
Michael Kauffmann
>> > Angesichts dessen, das bei drei Wiegungen mit jeweils 3 möglichen
>> > Ergebnissen 27 Kombinationen zustande kommen können, und das eine von
>> > 15 Kugeln entweder schwerere oder leichtere Kugel uns insgesamt 30 zu
>> > differenzierende Fälle liefert, wirst Du meine Skepsis verstehen.
>>
>> Gefragt ist nur, welche Kugel abweicht, nicht wie.
>
> Na und?
Das bedeutet, daß dein Unmöglichkeitsbeweis in dieser Form falsch ist.
> Aber wenn Du so schlau bist, wirst Du uns ja das Schema vorführen
> können.
Ich habe nie behauptet, daß es eine Lösung gibt oder ich sie kenne.
Und dein Tonfall ist nicht angemessen.
Michael Kauffmann
Angelos Beckmann
Naja, bei 27 Kugeln muss man halt wissen, ob es um eine schwerere oder
leichtere Kugel geht, dann geht auch dies.
Gruss Angel
Alfred Heiligenbrunner
Die Lösung in der FAQ _BRAUCHT_ 12 Kugeln! Wir haben aber nur 8.
Die FAQ-Lösung sagt
Drei Wägungen:
Links - Rechts
1. 2 3 7 12 - 4 8 9 10
2. 1 2 6 11 - 3 7 8 9
3. 1 5 10 12 - 2 6 7 8
Welche Kugeln nimmst Du dann bei der 1. Wägung? Was ist Kugel 9, 10 oder 12?
Alfred
> Alois
>
Reinhard Kronberger
Lege B zur Seite und lege jeweils 2 Kugeln der Gruppe A auf die Waage.
1 Fall:
Die Waage schlägt nicht aus -> ungleiche Kugel in B
Nehme 2 von A (alle gleich) und vergleiche sie mit 2 von B.
Fall 1.1
Die Waage schlägt nicht aus -> ungleiche in den restlichen 2 von B
Vergleiche eine aus A mit einer von den restlichen 2 aus B.
Damit ist es für diesen Fall entschieden den entweder die Waage schlägt aus
so habe ich die ungleiche aus B oder die verbleibende muß die ungleiche
sein.
Also Fall 1.1 erledigt.
Fall 1.2
Die Waage schlägt aus ->in den 2 von B liegt die Ungleiche.
Vergleiche eine aus A mit einer von den restlichen 2 aus B.
Damit ist es für diesen Fall entschieden den entweder die Waage schlägt aus
so habe ich die ungleiche aus B oder die verbleibende muß die ungleiche
sein.
Somit ist ganz Fall 1 = Fall 1.1 und Fall 1.2 entschieden.
Fall 2.
Habe also 2 mal 2 Kugeln von A auf der Waage und die Waage schlägt aus.
Vergleiche 2 von A mit 2 von B (von B alle gleich).
Argumentation wie oben.
womit für alle Fälle die ungleiche Kugel mit drei Wiegungen gefunden werden
kann.
Kronberger Reinhard
Peter Niessen
"DelTotti" <delt...@hotmail.com> schrieb im Newsbeitrag news:4f5ab7ba.03061...@posting.google.com...
Wie dem auch sei.
In der FAQ steht eine Lösung!
Wenn Du das Problem allgemein (für beliebig viele Kugeln) lösen willst:
Roll das Problem von hinten auf (also beginne mit der ungleichen Kugel) und füge
immer mehr Kugeln hinzu. Das Schema sollte schnell klar werden.
Das ist eine uralte Aufgabe die in vielen Varianten auch in einer Reihe von Büchern
behandelt wird.
mfg Peter
Alfred Pfeiffer
1. Schritt:
Lege jeweils 2 Kugeln auf jede Seite der Waage.
Danach kennen wir bereits 4 Kugeln, die das Normalgewicht haben.
(Falls die Wagge im Gleichgewicht geblieben war, sind das die
vier soeben gewogegenen Kugeln, war die Wage im Ungleichgewicht,
so sind es die vier nicht verglichenen.)
2. Schritt:
Vergleiche 3 Normalkugeln mit 3 Kugeln aus der Vierergruppe,
in der die ungleiche Kugel enthalten ist.
3. Schritt:
Fall a:
Wenn bei Schritt 2 Gleichgewicht herrschte, wissen wir bereits,
daß die verbliebene Kugel aus der Vierergruppe, die die ungleiche
Kugel enthielt, die gesuchte ist. Wir können diese im dritten
Schritt mit einer Normalkugel vergleichen und so ermitteln,
ob sie schwerer oder leichter ist.
Fall b:
Wenn bei Schritt 2 Ungleichgewicht angezeigt wurde, wissen wir
bereits, ob die abweichende Kugel schwerer oder leichter ist
(je nachdem, ob die Schale mit den Normalkugeln nach oben oder
unten ging). Um jetzt zu ermitteln, welche der drei in Betracht
kommenden Kugeln das ist, genügt es, daß im dritten Schritt zwei
beliebige aus dieser Dreiergruppe miteinander verglichen werden.
MfG,
Alfred Pfeiffer
Thomas Mautsch
>> > > >> > delt...@hotmail.com (DelTotti) writes:
>> > > >> > > Eine der 8 Kugeln ist schwerer ODER leichter als die übrigen 7.
>> > > >> > > Wie bekomme ich heraus, welche Kugel es ist, wobei ich nur 3 (in
>> > > >> > > Worten: DREI) mal wiegen darf !
>
> In der FAQ steht eine Lösung!
12 und 13 Kugeln explizit behandelt. Auch bei der passenderen Newsgroup
de.rec.denksport kann ich dazu nichts finden.
Hier noch ein netter Link zum Thema:
http://www.cs.uni-potsdam.de/~sprk/study/waegeprobleme.pdf
> Wenn Du das Problem allgemein (für beliebig viele Kugeln) lösen willst:
> Roll das Problem von hinten auf (also beginne mit der ungleichen Kugel) und füge
> immer mehr Kugeln hinzu. Das Schema sollte schnell klar werden.
> Das ist eine uralte Aufgabe die in vielen Varianten auch in einer Reihe von Büchern
> behandelt wird.
Ist es vielleicht gar nicht so, dass die Anzahl notwendiger Wägungen
mit der Kugelzahl wächst? Falls ja, kennt Ihr ein Gegenbeispiel?
David Kastrup
> Vielen Dank für die rege Beteiligung !
> Eigentlich ist in der Aufgabe die Rede von 8 Kugeln und leider wurde
> bisher immer noch kein Schema dargestellt mit dem das Problem mit drei
> Wiegungen gelöst werden könnte...Es ist nur gefragt, welche Kugel
> einen Gewichtsunterschied hat, es muß nicht bestimmt werden, ob sie
> leichter oder schwerer ist.
Du stellst Dich wirklich an. Du brauchst ja nur bei den vorgegebenen
Schemata ein paar Kugeln weglassen.
Nimm 3:3. Bei Gleichstand wiegst Du eine der ungewogenen Kugeln
gegen eine jetzt als neutral bekannte und weißt danach, welche die
üble war.
Bei Ungleichstand läßt Du zwei Kugeln die Seite wechseln, nimmst zwei
Kugeln auf der anderen Seite dafür raus und füllst links mit als
jetzt neutral bekannten Kugeln auf. Ändert sich die Richtung des
Ungleichstandes nicht, liegt das an einer der beiden
liegengebliebenen Kugeln, von denen du jetzt eine mit einer neutralen
vergleichst. Stellt sich jetzt Gleichstand ein, liegt das an einer
der zwei rausgenommenen Kugeln. Ändert sich die Richtung des
Ungleichstandes, liegt das an einer der beiden rübergenommenen Kugeln.
DelTotti
Schööööön !
Vielen Dank für die Lösungen Alfred und Reinhard !
Denn bis denn...
Alfred Heiligenbrunner
> Alternative Lösung:
>
[Lösung gesnipt]
Hallo Alfred! :-)
Ähnlich zu der Musterlösung mit 12 Kugeln gibt es auch für 8 Kugeln eine
Lösung, die ohne Fallunterscheidung _während_ der Wägungen auskommt.
Die drei Wägungen:
Links - Rechts
1. 1 3 7 - 2 6 8
2. 2 3 7 - 1 4 5
3. 4 6 7 - 1 2 8
Für diese drei Wägungen gibt es nun 17 verschiedene Ergebnisse: ,,/``
linke Seite schwerer, ,,\`` rechte Seite schwerer, ,,-`` Gleichgewicht;
,,ag`` alle gleich, ,,* l/s`` Kugel * ist zu leicht/schwer.
123
--- ag
/\\ 1s
\// 1l
\/\ 2s
/\/ 2l
//- 3s
\\- 3l
-\/ 4s
-/\ 4l
-\- 5s
-/- 5l
\-/ 6s
/-\ 6l
/// 7s
\\\ 7l
\-\ 8s
/-/ 8l
MfG
Alfred Heiligenbrunner
>
>
> MfG,
> Alfred Pfeiffer
>
Alfred Heiligenbrunner
> Lösung, die ohne Fallunterscheidung _während_ der Wägungen auskommt.
>
> Die drei Wägungen:
>
> Links - Rechts
> 1. 1 3 7 - 2 6 8
> 2. 2 3 7 - 1 4 5
> 3. 4 6 7 - 1 2 8
>
Ob es solche Lösungen z.B. auch für 5, 6, 7, bzw. 9, 10, 11 Kugeln gibt, weiß ich nicht!
MfG
Alfred
Daniel Gutekunst
>> Ähnlich zu der Musterlösung mit 12 Kugeln gibt es auch für 8 Kugeln eine
>> Lösung, die ohne Fallunterscheidung _während_ der Wägungen auskommt.
>>
>> Die drei Wägungen:
>>
>> Links - Rechts
>> 1. 1 3 7 - 2 6 8
>> 2. 2 3 7 - 1 4 5
>> 3. 4 6 7 - 1 2 8
>>
> Das habe ich übrigens gestern mit etwas Probieren gefunden.
Ich auch, mit zwei mal 3 gegen 3 und einmal 2 gegen 2 wiegen.
> Ob es solche Lösungen z.B. auch für 5, 6, 7, bzw. 9, 10, 11 Kugeln gibt,
> weiß ich nicht!
Könnte man durch ein Bruteforce-Verfahren mit dem Computer checken. Ein
System wäre jedoch eleganter.
Tschüss
Daniel Gutekunst
Alfred Pfeiffer
Noch zwei Anmerkungen dazu:
Alfred Heiligenbrunner wrote:
> ...
Schön zu wissen, daß es diese Methode auch für diesen Fall gibt.
1) Allerdings würde ich sie in der Praxis nicht bevorzugen,
(abgesehen davon, daß man dieses Schemata erst einmal finden muß
und sie dann auch noch schlecht zu merken sind) weil es mit der
Falluntescheidung schneller gehen kann:
In 1/8 der Fälle kann man die dritte Wägung einsparen, nämlich bei
| Fall a:
| Wenn bei Schritt 2 Gleichgewicht herrschte, wissen wir bereits,
| daß die verbliebene Kugel aus der Vierergruppe, die die ungleiche
| Kugel enthielt, die gesuchte ist. Wir können diese im dritten
| Schritt mit einer Normalkugel vergleichen und so ermitteln,
| ob sie schwerer oder leichter ist.
Falls die fragliche Kugel bereits in Schritt 1 auf der Waage lag,
wissen wir jetzt schon, ob sie schwerer oder leichter ist, und
können uns Schritt 3 schenken. :-)
2) Was mir bei unseren Lösungen noch auffiel ist, daß sie eine
etwas "verschärfte" Aufgabenstellung auch lösen würden, die etwa
so lauten könnte:
8 Kugeln und eine Waage
(so eine alte Waage wie im Sternzeichen, keine digitale!).
Eine der 8 Kugeln KANN schwerer oder leichter sein als die
übrigen 7. Aber man weiß es nicht genau!
Ansonsten sehen alle Kugeln gleich aus.
Wie bekomme ich heraus, ob eine solche abweichende Kugel
existiert, und falls das der Fall ist, welche Kugel es ist
und ob sie schwerer oder leichter ist, wobei ich nur 3
(in Worten: DREI) mal wiegen darf!
MfG,
Alfred Pfeiffer