Mal wieder ein Wiegerätsel [gelöst] |
04.08.2004, 01:37 | KnightMove | Auf diesen Beitrag antworten » |
Mal wieder ein Wiegerätsel [gelöst] Wieviele Münzen dürfen es dazu maximal sein? |
||
04.08.2004, 01:43 | sommer87 | Auf diesen Beitrag antworten » |
mal wichtig markier und dir ne PN schick |
||
04.08.2004, 01:46 | 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 |
||
04.08.2004, 01:51 | 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 ^^wie gesagt, wer lesen kann ist im vorteil 12 kommt dann schon eher hin |
||
04.08.2004, 01:58 | Ben Sisko | Auf diesen Beitrag antworten » |
Für die Interessierten: Mit 12 findet es sich u.a. hier Gruß vom Ben |
||
04.08.2004, 02:09 | KnightMove | Auf diesen Beitrag antworten » |
Aber 12 ist nicht die richtige Antwort! |
||
Anzeige | ||
|
||
04.08.2004, 02:10 | Ben Sisko | Auf diesen Beitrag antworten » |
Immerhin haben wir eine untere Schranke für die Lösung gefunden... |
||
09.08.2004, 13:02 | KnightMove | Auf diesen Beitrag antworten » |
Und zwar gar keine schlechte... |
||
06.09.2004, 20:54 | Omalee | Auf diesen Beitrag antworten » |
Wie wär's mit 15? |
||
06.09.2004, 22:43 | KnightMove | Auf diesen Beitrag antworten » |
Wie kommst Du auf 15? |
||
07.09.2004, 00:12 | 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...? |
||
07.09.2004, 18:41 | KnightMove | Auf diesen Beitrag antworten » |
Und wie kommst Du darauf? |
||
07.09.2004, 19:19 | 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 |
||
19.09.2004, 23:36 | 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 |
||
20.09.2004, 16:58 | 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! |
||
21.09.2004, 09:46 | juergen | Auf diesen Beitrag antworten » |
18 |
||
21.09.2004, 12:12 | 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 und ich hab den beweis das es mit 13 funktioniert also stimmt 13 aber es kann auch sein das ich da falsch liege |
||
21.09.2004, 15:15 | 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' |
||
21.09.2004, 16:55 | 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) |
||
21.09.2004, 20:50 | 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' |
||
21.09.2004, 23:34 | 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. |
||
22.09.2004, 02:02 | 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 |
||
22.09.2004, 09:27 | 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' |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|