Mal wieder ein Wiegerätsel [gelöst]

Neue Frage »

KnightMove Auf diesen Beitrag antworten »
Mal wieder ein Wiegerätsel [gelöst]
In einem Häufchen von n Münzen ist eine mit einem geringfügig anderen Gewicht (leichter oder schwerer). Mit nur drei Wägungen auf einer Balkenwaage soll man sie finden.

Wieviele Münzen dürfen es dazu maximal sein?
sommer87 Auf diesen Beitrag antworten »

mal wichtig markier und dir ne PN schick smile
fakultaet Auf diesen Beitrag antworten »

Ich kenne das Rätsel mit einer Anzahl von 12. Und das war schon ein riesen Aufwand so rauszufinden welche ein anderes Gewicht hat.
Deshalb würde ich mal sagen n = max. 12

mfg
sommer87 Auf diesen Beitrag antworten »

ok, die PN schnell wieder vergess :P

ich hab nur größer oder nur kleiner gedacht, dann hätte ich 27 gesagt geschockt
^^wie gesagt, wer lesen kann ist im vorteil smile

12 kommt dann schon eher hin verwirrt
Ben Sisko Auf diesen Beitrag antworten »

Für die Interessierten: Mit 12 findet es sich u.a. hier

Gruß vom Ben
KnightMove Auf diesen Beitrag antworten »

Aber 12 ist nicht die richtige Antwort! unglücklich
 
 
Ben Sisko Auf diesen Beitrag antworten »

Immerhin haben wir eine untere Schranke für die Lösung gefunden... Augenzwinkern
KnightMove Auf diesen Beitrag antworten »

Und zwar gar keine schlechte...
Omalee Auf diesen Beitrag antworten »

Wie wär's mit 15?
KnightMove Auf diesen Beitrag antworten »

Wie kommst Du auf 15?
cob-2000 Auf diesen Beitrag antworten »

Bin mir nicht sicher, aber ich bin auf eine Anzahl von 13,5 gekommen. Also dürfen es höchstens 13 sein...?
KnightMove Auf diesen Beitrag antworten »

Und wie kommst Du darauf?
ligako Auf diesen Beitrag antworten »

also ich schraub die minorante auf 13 weil so hab ichs geschaft aber ich hab noch keine ahnung wie ich beweisen soll das es das maximum ist was ich allerdings glaube. mich interresiert allerdings wie cob auf ne komma zahl kommt
cob-2000 Auf diesen Beitrag antworten »

Ich habe versucht, das Ganze über den Informationsgehalt zu berechnen, bin mir aber nicht ganz sicher, ob ich das richtig gemacht habe:

Eine Wägung kann 3 verschiedene Ergebnisse liefern:
- links schwerer
- rechts schwerer
- gleich schwer

Damit kann man den Informationgehalt einer Wägung berechnen:

I = ld (3) = 1,5849 bit

Da wir aber 3 Wägungen haben, haben wir einen Gesamtinformationsgehalt von 3*I = 4,7548 bit

Wenn bei einer Anzahl von n Münzen eine Münze leichter oder schwerer ist, dann gibt es 2*n verschiedene Kombinationsmöglichkeiten und das entspricht wieder dem Informationsgehalt

I = ld (2n)

--> ld (2n) = 3*ld (3) = 4,7548 bit

löst man diese Gleichung nach n auf, erhält man n=13,5.
14 Münzen sind also zu viel. Deshalb mein Ergebnis: n=13
KnightMove Auf diesen Beitrag antworten »

Ich lasse offen, ob 13 stimmt oder nicht. Aber Dein Beweis funktioniert nur, wenn Münzen kontinuierlich sind - Du kannst 13 Münzen nicht dritteln!
juergen Auf diesen Beitrag antworten »

18 verwirrt
ligako2 Auf diesen Beitrag antworten »
ich denke der cob hat doch irgendwie recht
servus
so da mein alter name nicht mehr geht jetzt die version 2

ich kenn mich mit der informationsgehaltsrechnung nicht aus aber das lustige ist bei meiner lösung könnte man bei einer wägung eine kugel mehr nehmen wenn man sie halbieren könnte somit komm ich auch auf 13.5 also entweder ist das nur zufall oder das ergebniss stimmt tatsächlich ich denke ich kuck mir mal im laufe der nächsten tage was zur informationsrechnung an und versuch das dann mal mit der einschränkung das nur ganze werte gelten zu rechnen
fazit ich bin der meinung das cob die theorethische obere schranke gefunden hat Gott
und ich hab den beweis das es mit 13 funktioniert also stimmt 13 smile
aber es kann auch sein das ich da falsch liege Augenzwinkern
szlfrz Auf diesen Beitrag antworten »

Hiho,

n kann maximal 12 sein. Da es dafür ein Verfahren gibt, ist 12 optimale Schranke.

Darum geht 13 nicht:

Ein Wägeverfahren läuft immer wie folgt ab.
Bei der ersten Wägung werden Kugeln für die linke und die rechte Seite der Waage
ausgewählt. Das Wägungsergebnis kann sein:
linke Seite schwerer, rechte Seite schwerer oder beide gleich schwer
Abhängig vom Ergebnis werden erneut Kugeln für linke/rechte Seite ausgewählt, usw.

In jedem Schritt können bestimmte Kugeln als "falsche" Kugeln ausgeschlossen werden.
Nach dem dritten Schritt muß ein einzelne Kugel als "falsche" Kugel bestimmt sein und
ermittelt worden sein, ob sie leichter oder schwerer ist.

Zu jedem beliebigen Wägeverfahren kann man einen sogenannten Entscheidungsbaum
aufstellen. Dessen Knoten symbolisieren die Wägungen. Je nach Versuchsausgang verzweigt
das Verfahren zu einem Nachfolgeknoten. Bis man schließlich an einem Blatt ankommt.
Schreibt man nun an jeden Knoten die Menge der Kugeln, die als "falsche" in Frage kommen
(zusammen mit der Information leichter/schwerer), muß an jedem Blattknoten ein eindeutiges
Ergebnis stehen. Es gibt also mindestens 26 Blätter (13 Kugeln *2 Zustände).

Da der Verzweigungsfaktor pro Knoten maximal 3 ist, ist die minimale Tiefe eines solchen
Baumes log_3 (26).
Dies ist knapp kleiner als 3, was noch keinen Widerspruch darstellt (schließlich können wir
dreimal wiegen).

Schaut man etwas genauer hin, sieht man daß 13 nicht ordentlich teilbar ist.
Folgendes kann passieren:
1. Wir legen bei der ersten Wägung maximal 4 Kugeln auf jede Seite.
Sind beide Seiten gleichschwer, so befindet sich die falsche Kugel unter den verbleibenden 5.
Da nicht bekannt ist, ob diese leichter oder schwerer ist, hat der entsprechende Teilbaum
noch mindestens 10 Blätter.
2. Wir legen bei der ersten Wägung mindestens 5 Kugeln auf jede Seite.
Ist die linke Seite leichter, so ist die falsche Kugel links und leichter oder rechts und schwerer.
Wieder 10 verbleibende Möglichkeiten.
Analog, wenn die rechte Seite leichter ist.

Egal, wie die erste Wägung aussieht, gibt es also stets einen Unterbaum mit mindestens 10 Blättern.
In diesem Unterbaum haben wir noch 2 Wägungen übrig.
Will man in einem Baum mit Verzweigungsfaktor <= 3 10 Blätter unterbringen, so gibt es
stets ein Blatt in Tiefe 3 des Unterbaums (wegen log_3(10)>2), also in Tiefe 4 des Ursprungsbaumes.

Dieses Blatt kann nicht mit 3 Wägungen erreicht werden, damit gibt es für jedes Verfahren eine
Anordnung der Kugeln, so daß es versagt.

Ich hoffe, daß der ganze Kram eineigermaßen verständlich ist.

Grüße
Andre'
ligako2 Auf diesen Beitrag antworten »

hiho zurück
also ich erklär mal schnell wie ich mir das mit 13 kugeln gedacht habe
1. mal wiegen
4 kugeln auf beide seiten und sie sind gleich schwer somit ist kugel 6-13 neutra
nun bleiben kugel 1-5 hier ist die böse kugel
2.mal wiegen
1,2,3 vs. 3 kugeln aus neutralem haufen
hier kann man drei fälle unterscheiden entweder schwerer(A), leichter(B) oder gleich(C)
3A
1 vs. 2
wieder 3 fälle
1 schwerer 2 => 1 ist böse
2 schwerer 1 => 2 ist böse
1 gleich 2 => 3 ist böse

3B
dann ist genau umgekeht wie bei 3A


3C
4 vs. 1 kugel aus dem neutralen haufen
wieder 3 fälle
4 schwerer n => 4 ist böse
n schwerer 4 => 4 ist böse
4 gleich n => 5 ist böse


somit gehen 13 kugeln auf jeden fall ich weiß zwar in dem fall das 5 das schwarze schaf ist nicht ob schwerer oder leichter aber das interresiert ja auch nicht (somit gibt es ein blatt auf dem steht nur falsch und dieses blatt ersetzt die beiden letzten s und w blätter , also nur 9 blätter und die sind mit 2 knoten zu erreichen die frage lieber szlfrz ist also wieviel blätter sind es tatsächlich)
szlfrz Auf diesen Beitrag antworten »

Hallo Ligako2,

du hast recht, die Aufgabe war ja nur, zu bestimmen welche Kugel es ist.
Daher ist mein Argumentation nicht sauber. Sorry.

Nun würde mich trotzdem interessieren, wie Du verfährst, wenn bei der
ersten Wägung kein Gleichgewicht eintritt.

Grüße
Andre'
KnightMove Auf diesen Beitrag antworten »

ligako hat es korrekt gelöst. szlfrz: Die Erklärung findest Du im Link von Ben Sisko auf der ersten Seite.
ligako2 Auf diesen Beitrag antworten »

so ich komm gerade vom oktoberfest heim und wollte nur sagen ich habs etwas anderst gemacht als in dem link aber dazu bin ich jetzt zu betrunnken des weite en bin ich nicht sicher das ich es gelöst habe ich denke ich hab nicht bewiesen das 14 nicht geht da mus man in die richtung rechnen wie cob es getahn hat also ozapt is
szlfrz Auf diesen Beitrag antworten »

Hi,

aber geht cob nicht auch davon aus, daß der Informationsgehalt 2*n ist?
Wenn man jedoch nicht daran interessiert ist, ob die Kugel leichter oder schwerer ist,
ist das vielleicht etwas zu großzügig.

Ciao
Andre'
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »