DieManager von Morgen WiWi-TReFF.de - Zeitung & Forum für Wirtschaftsstudium & Karriere
BrainteaserLogikrätsel

Mal wieder Kugeln...

Autor
Beitrag
WiWi Gast

Mal wieder Kugeln...

Aber noch verzwickter als das 12-Kugelproblem (finde ich).

Fünf Kugeln mit unterschiedlichem Gewicht. Balkenwaage, gewogen (also verglichen) werden jeweils genau zwei Kugeln (also pro Waagschale genau eine Kugel). Die Kugeln sind nach Gewicht zu sortieren. Wieviele Vergleiche benötigt man höchstens?

;-) Karl

antworten
WiWi Gast

Re: Mal wieder Kugeln...

WiWi Gast

Re: Mal wieder Kugeln...

Sorry für die verstrichene Zeit, es kam ein längerer Urlaub dazwischen :-)

3??? Wie soll das gehen? Soviel braucht Du schon für drei Kugeln, zur Verdeutlichung:

Die Kugeln seien a,b und c benannt.
1 a --*-- b a sei leichter als b (andernfalls werden sie schnell umbenannt).
2 c --*-- a , falls ca: c --*-- b, falls c>b Lösung a b c, sonst a c b

Bei 4 Kugeln würde wohl (im Fall a b c) folgen
4 d --*-- b
5 wenn d>b: d --*-- c . wenn d>c Lösung a b c d, sonst a b d c
5 wenn da Lösung a d b c, sonst d a b c

Also: Wieviele Wägungen bei 5 Kugeln maximal (!!) (die optimale Strategie natürlich vorrausgesetzt)?

Karl

antworten
WiWi Gast

Re: Mal wieder Kugeln...

10 ... 4+3+2+1

antworten
WiWi Gast

Re: Mal wieder Kugeln...

10 ... 4+3+2+1

Wie kommst Du darauf?

Theoretische Abschätzung dazu: 5 verschieden schwere Kugeln können 120 Permutationen bilden (5!, 1*2*3*4*5). Das System
kann also 120 Zustände einnehmen, man benötigt also
Informationen von ld 120= 6,9 Bit. Die Waage liefert pro Wägung
1 Bit ( a < b oder a>b, Entscheidung zwischen 2 Zuständen, ld 2=1). Also könnten 7 Wägungen (7*1 Bit) ausreichen.
"Könnten" weil die Informationsabschätzung zwar notwendige, aber nicht hinreichende Ergebnisse liefert. Das 12-Kugelproblem (eine leichter oder schwerer) z.B. müsste über die Abschätzung alleine auch mit 13 Kugelen lösbar sein.

Beim Kugelsortieren kommt man aber tatsächlich mit 7 Wägungen hin. Später werden ich mal den zugehörigen Entscheidungsbaum posten, vielleicht wollen es ja noch der eine oder andere selbst versuchen!

antworten
WiWi Gast

Re: Mal wieder Kugeln...

also diesen bit-kram versteh ich kein bisschen, aber pro kugel mehr braucht man bei n anzahl der kugeln n-1 versuche mehr dachte ich?

antworten
WiWi Gast

Re: Mal wieder Kugeln...

n anzahl der kugeln n-1 versuche mehr dachte ich?

Ach, jetzt verstehe ich. Du denkst an teilsortierte Listen,
in die Du jeweils die nächste Kugel durch paarweisen Vergleich
einsortierst und berücksichtigst den worst case.
Das geht aber effektiver, wenn die neue Kugel nicht "vom Rand aus"
einsortiert wird sondern von der Mitte her - so braucht es z.B. nur
zwei Vergleiche, um die vierte Kugel in die *sortierte* 3er Liste
einzusortieren: Ist sie schwerer als die Mittlere, muss nur noch
gegen die Leichteste gewogen werden (und gegen die Schwerste im
anderen Fall).

Aber bei dieser Aufgabenstellung kommst Du aber mit dem
"teilsortierte Listen" - Konzept auf bestenfalls 8 Versuche ;-)

antworten
WiWi Gast

Re: Mal wieder Kugeln...

Ist sie schwerer als die Mittlere, muss nur noch gegen die Leichteste gewogen werden

Quatsch, umgekehrt natürlich!

antworten
WiWi Gast

Re: Mal wieder Kugeln...

gib mal n konkretes beispiel, wie es bei dir mit 7 geht?

antworten
WiWi Gast

Re: Mal wieder Kugeln...

Die Frage war, wieviele Waegungen man hoechstens braucht.
Und das sind nicht sieben, sondern zehn. Mit wievielen man "hinkommt" ist egal.
Und wie kommt man auf die 6,9 Bit?

antworten
WiWi Gast

Re: Mal wieder Kugeln...

Und das sind nicht sieben, sondern zehn.

Nein. Als Beispiel das gleiche Rätesel mit nur 4 Kugeln. Nach Deiner Logik wären es 1+2+3 = 6 Wägungen, richtig? Und ich behaupte, nach folgendem Verfahren sind es *immer* *höchstens* 5.

  1. Wägung: b und c, soll b < c ergeben. Reihenfolge: bc
  2. Wägung: a und c, ergibt a
antworten
WiWi Gast

Re: Mal wieder Kugeln...

oops- es gibt hier inzwischen Ptzbeschränkungen..-(

  1. Wägung: a und b, ergibt, wenn a b, wird d mit c verglichen. Es ergibt sich die endgültige Reihenfolge abcd bezw. abdc!
    War (in der 4. Wägung) d 6,9 Bit?
    In der Informationstheorie ist ein Bit als negativer dualer Logarithmus der Auftretenswahrscheinlichkeit definiert. Die 5 Kugeln können in 120 verschiedene Anordnungen gebracht werden, somit hat (bei Gleichwahrscheinlichkeit der Zustände) ein System den Informationsgehalt -ld(1/120) = ld 120 = 6,9.
    In diesem Fall kann man das auch einfacher betrachten, es kommt mathematisch auf das gleiche hinaus: Es gibt 120 Möglichkeiten, die Kugeln anzuordnen. Es gibt 128 Möglichkeiten, wie sich die Waage bei 7 Wägungen jeweils verhält: 2*2*2*2*2*2*2 = 2^7 = 128, das sind *mehr* Möglichkeiten als die der Kugeln, *grundsätzlich* spricht also nichts gegen ein Machbarkeit mit 7 Wägungen.
antworten
WiWi Gast

Re: Mal wieder Kugeln...

nochmal..

  1. Wägung: a und b, ergibt, wenn a b, wird d mit c verglichen. Es ergibt sich die endgültige Reihenfolge abcd bezw. abdc!
    War (in der 4. Wägung) d
antworten
WiWi Gast

Re: Mal wieder Kugeln...

...ich geb's auf

antworten
Moderator Jörg

Re: Mal wieder Kugeln...

Hi,

du scheinst ein Sonderzeichen zu verwenden, das als html-Code interpretiert wird. Versuchs nochmal ohne das Zeichen oder schick mir dein Posting per Mail, dann ergänze ich das.

Sorry

Jörg

[%sig%]

antworten
WiWi Gast

Re: Mal wieder Kugeln...

Hallo Jörg, könnt ein < mit direkt folgendem Bustaben sein.
Kannst Du den entstandenen Müll rausschmeissen?

Und das sind nicht sieben, sondern zehn.

Nein. Als Beispiel das gleiche Rätesel mit nur 4 Kugeln. Nach Deiner Logik wären es 1+2+3 = 6 Wägungen, richtig? Und ich behaupte, nach folgendem Verfahren sind es *immer* *höchstens* 5.

  1. Wägung: b und c, soll b < c ergeben. Reihenfolge: bc
  2. Wägung: a und c, ergibt a < c (also der *schlechte* Fall)
  3. Wägung: a und b, ergibt, wenn a < b ist abc, sonst bac
    Annahme: abc
  4. Wägung: d wird mit **b** verglichen (es ist hier _nicht_ egal, mit welcher verglichen wird,"angefangen" wird immer in der Mitte).
  5. Wägung: War d > b, wird d mit c verglichen. Es ergibt sich die endgültige Reihenfolge abcd bezw. abdc!
    War (in der 4. Wägung) d < b, wird d mit a verglichen. Es ergibt sich die endgültige Reihenfolge dabc bezw. adbc!
    q.e.d

6,9 Bit?
In der Informationstheorie ist ein Bit als negativer dualer Logarithmus der Auftretenswahrscheinlichkeit definiert. Die 5 Kugeln können in 120 verschiedene Anordnungen gebracht werden, somit hat (bei Gleichwahrscheinlichkeit der Zustände) ein System den Informationsgehalt -ld(1/120) = ld 120 = 6,9.
In diesem Fall kann man das auch einfacher betrachten, es kommt mathematisch auf das gleiche hinaus: Es gibt 120 Möglichkeiten, die Kugeln anzuordnen. Es gibt 128 Möglichkeiten, wie sich die Waage bei 7 Wägungen jeweils verhält: 2*2*2*2*2*2*2 = 2^7 = 128, das sind *mehr* Möglichkeiten als die der Kugeln, *grundsätzlich* spricht also nichts gegen ein Machbarkeit mit 7 Wägungen.

antworten

Artikel zu Logikrätsel

Einstein Rätsel: »Für 98 Prozent der Weltbevölkerung unlösbar«

Ein im Wasser schwimmender Goldfisch.

Das Einstein Rätsel lautet: »Wer hat einen Fisch als Haustier?« Für 98 Prozent der Weltbevölkerung soll das von Albert Einstein erdachte Rätsel angeblich unlösbar sein.

Logikrätsel: Entschärfe die Bombe

Stirb langsam! Oder denke schnell und entschärfe die Bombe!

Logikrätsel: Neun Kugeln und die Balkenwaage

Vor dir steht eine Balkenwaage. Des weiteren liegen vor dir 9 Kugeln, die alle die gleiche Größe und dasselbe Aussehen besitzen. Eine dieser 9 Kugeln ist etwas schwerer als die anderen 8 Kugeln.

Logikrätsel: Sammlung optischer Täuschungen

Eine Person mit Regenschirm spiegelt sich im Wasser.

Prof. Dr. Michael Bach von der Uni Freiburg präsentiert auf seiner Homepage eine Sammlung optischer Täuschungen und erläutert, wie sie funktionieren.

Logikrätsel: Schachbrettaufgaben

Ein mit Kreide gezeichnetes Schachbild mit Pferd und König in schwarz-weiß.

Mit einem Schachbrett kann man hervorragend spielen. Schach natürlich, aber nicht nur das. Die Mathematikseite Mathe-Online hat eine Reihe interessanter Aufgaben zusammengetragen.

Die Magische Zauberkugel

Eine Glaskugel spiegelt sich mit ihrem kunstvollen, spiralförmigen Inneren in der Sonne.

Kaum zu glauben: Die Magische Zauberkugel kann Gedanken lesen und errät jede zweistellige Zahl, die man sich ausdenkt. Probiert es einmal aus - Ihr werdet überrascht sein!

Defekte Glühbirne - Alternative Lösungsansätze

Eine nackte Glühbirne mit schwarzer Fassung hängt von der Zimmerdecke.

In der Firma ist eine Glühlampe defekt. Es werden von den verschiedenen Abteilungen Vorschläge alternativer Lösungsansätze eingeholt.

Logikrätsel: Das Testament und die 10 Manager

Das Testament und die 10 Manager (ne extrem harte Nuss).

Logikrätsel: Das Schwert des Henkers

Die Silouette eines asiatischen Mannes mit einem Kampfschwert.

Ein Manager träumte, dass er von einem König zum Tod durch das Schwert verurteilt worden sei. Gefesselt wurde der Manager auf den Hinrichtungsplatz geführt.

Logikrätsel: Kugel-Rätsel

Das folgende Kugel-Rätsel mit 12 Kugeln ist eine echte Herausforderung.

Logikrätsel: Das geometrische Dreiecks-Paradoxon

Rätsel

Das zweite Dreieck auf dem Bild scheint paradox. Kann das stimmen?

Logikrätsel: Cowboy in der Kirche - Die wundersame Geldvermehrung

Ein Cowboy kehrt vom Viehtrieb einer Rinderherde zurück. Er geht nach dem langen und harten Ritt in die Kirche und betet: »O Herr, bitte verdopple die Summe des Geldes, das ich bei mir habe! Als Dank werde ich auch 10 Dollar spenden!«

Logikrätsel: Kniffliges Münzenrätsel

Eine englische Münze von 1996 lehnt an einem leeren Kaffeeglas mit der Aufschrift: in god we trust.

Ein etwas kniffligeres Münzenrätsel aus unserem Forum von Speedy!

Logikrätsel: Die Goldbarren in Schweizer Banken

Ein kleiner, roter Reisewecker mit einem Kreuz und der Innschrift Switzerland.

Ein nicht genannt sein wollender Vorsitzender einer nicht genannt sein wollenden staatstragenden Partei eines nicht genannt sein wollenden Nachbarlands, nennen wir ihn K., begibt sich in den wohlverdienten Ruhestand. Auf einer bestimmten Zahl von Schweizer Banken hat er jeweils wiederum die gleiche Zahl von Schliessfächern gemietet und in jedes dieser Schliessfächer hat er drei Goldbarren von je einem Kilogramm gelegt.

Logikrätsel: Schnur um den Äquator

Afrika, Africa, Kontinent, Armut, Asyl, Flüchtlinge,

Angenommen, der Äquator wäre 40.000km lang und ein perfekter Kreis. Nun wickeln wir eine Schnur um den Äquator.

Antworten auf Mal wieder Kugeln...

Als WiWi Gast oder Login

Forenfunktionen

Kommentare 16 Beiträge

Diskussionen zu Logikrätsel

Weitere Themen aus Brainteaser