Wägungen um fälsche Münze zu finden |
| 20.01.2006, 11:46 | Babe | Auf diesen Beitrag antworten » | ||||
| Wägungen um fälsche Münze zu finden Ich habe Probleme mit ner Aufgabe. Weiß gar nicht, wie ich da anfangen soll... Bitte, helft mir!!! Also.... Es seien 12 scheinbar gleiche Münzen vorhanden, von denen 11 das gleiche Gewicht besitzen; eine unterscheide sich von den übrigen durch ihr Gewicht. a) Wie viele Wägungen müssen Sie auf einer Schalenwaage ohne Gewichte mindestens durchführen, um die falsche Münze herauszufinden und um gleichzeitig festzustellen, ob sie leichter oder schwerer ist als die übrigen? b) Formulieren Sie eine optimale Strategie zur Bestimmung der falschen Münze, ohne die Gewichtsvergleiche im Einzelnen zu beschreiben. c) Wie viele Gewichtsvergleiche benötigen Sie mindestens, wenn statt der 12 scheinbar gleichen Münzen 13 gegeben sind? Hoffe, mir hilft jemand. Euch ein schönes Wochenende!!! 
|
||||||
| 20.01.2006, 12:50 | gargyl | Auf diesen Beitrag antworten » | ||||
Lege aus die eine Schale 6 Münzen und auf die andere 6 Müzen. Was geschied? Was kann man daraus folgern? |
||||||
| 20.01.2006, 15:06 | smalldiver | Auf diesen Beitrag antworten » | ||||
Das thema ist auch schon vorhanden nur mit anderen Zahlen. Guck mal unter Wieviele Fragen um Zahl zu erraten? |
||||||
| 20.01.2006, 15:07 | JochenX | Auf diesen Beitrag antworten » | ||||
hallo, wenn ich es richtig sehe ist das ganze trickreich ein rätsel, dass du hier im forum findest. tatsächlich geht es (bei 12 kugeln) durch 3 wägungen, allerdings mit enormem denkaufwand. mit 13 münzen benötigst du, denke ich, mind. 4 wägungen, allerdings bin ich mir da weder sicher, zumal letztens ein gast das rätselforum mit "ich kann das mit 15 kugeln und 3 wägungen" zugespammt hat. einen beweis hat er auf aufforderung aber nicht gezeigt. also nutz auf jeden fall mal die suche, das hilft. |
||||||
| 20.01.2006, 15:38 | riwe | Auf diesen Beitrag antworten » | ||||
kugeln usw. von einem, der schon weiß, wie man einen link einfügt werner |
||||||
| 20.01.2006, 16:13 | Ben Sisko | Auf diesen Beitrag antworten » | ||||
Kann ich auch... 
Wiege 12 Kugeln und leg 3 zur Seite. Ist die Waage im Gleichgewicht, genügt eine weitere Wägung (heisst das wirklich so??), ansonsten weiter wie bei 12... |
||||||
| Anzeige | ||||||
|
|
||||||
| 20.01.2006, 19:32 | JochenX | Auf diesen Beitrag antworten » | ||||
hehe, ben, dadurch hast du aber schon eine wägung verbraten, die dir zwar schon weitere information gegeben hat, aber nicht genug. der 12-kugel trick fängt glaube ich mit 4 vs 4 an.... |
||||||
| 20.01.2006, 20:23 | Ben Sisko | Auf diesen Beitrag antworten » | ||||
OK, fang auch mit 4 vs. 4 an. Wenn gleich ist, ist klar wie's weitergeht, oder? Wenn ungleich, mach mit den restlichen 7 2 vs. 2. Wenn ungleich =>klar, wenn gleich hast du noch 3 und hier ist mit einem Wiegen auch kein Problem... Edit: Der Spammer hat vielleicht gespammt, aber nicht gelogen
|
||||||
| 20.01.2006, 22:28 | JochenX | Auf diesen Beitrag antworten » | ||||
wenn die ersten 4vs4 ungleich sind, dann ist die andere unter ihnen warum also mit den restlichen 7 weiterarbeiten?? |
||||||
| 20.01.2006, 22:38 | Ben Sisko | Auf diesen Beitrag antworten » | ||||
Ungleich und gleich verwechselt, so ist's richtig:
Da hättest du aber jetzt von allein drauf kommen können... 
|
||||||
| 20.01.2006, 22:40 | JochenX | Auf diesen Beitrag antworten » | ||||
es sei gleich ich nehme nach deinem ansatz von den restlichen 7 kugeln 4 raus und mache 2vs2 fall a) gleich dann bleiben 3 kugeln, von denen eine unterschiedlich schwer ist (unbekannt ob leichter oder schwerer); und dann? fall b) ungleich: dann sind entweder eine von zwei leichter; oder eine von den anderen beiden schwerer; und dann? mfg jochen ps: sorry fürs offtoic, aber ich sehe hier klärungsbedarf |
||||||
| 20.01.2006, 22:52 | Ben Sisko | Auf diesen Beitrag antworten » | ||||
"Mache 1 vs. 1" wie sich hier so schön als Vokabel eingebürgert hat. Entweder siehst du die schwere oder die übrig gebliebene ist es.
Eine Seite ist schwerer, also ist die schwerere Kugel eine dieser beiden. Wiege nach, welche es ist! |
||||||
| 20.01.2006, 22:58 | JochenX | Auf diesen Beitrag antworten » | ||||
das dachte ich mir, ben hätte vermutlich ähnlich gedacht, wenn ich nicht das rätsel an sich kennen würde mit einer schwereren kugel kann ich aus 3^n kugeln mit n mal wiegen rausfinden, welche.... aber:
sie muss nicht schwerer sein, in dem rätsel weißt du das nicht! sie unterscheidet sich, kann also auch leichter sein! und ich vermute (grad wegen der zahl 12), dass das hier entsprechend ist dann musst du also in 3 wiegungen rausfinden: welche kugel ist anders und wie ist sie anders schau dir den link oben an, den werner, der inzwischen links posten kann *g*, gepostet hat..... das rätsel ist der hammer
|
||||||
| 20.01.2006, 23:03 | Ben Sisko | Auf diesen Beitrag antworten » | ||||
Ah, ok, darauf hab ich nicht geachtet, dachte es wäre das mir bekannte Rätsel. Das macht es natürlich ungleich schwerer. Und ich wunder mich schon, warum du heute so begriffsstutzig bist 
Übrigens: Ich hab's ihm erklärt
|
||||||
| 20.01.2006, 23:07 | JochenX | Auf diesen Beitrag antworten » | ||||
schlecht geschlafen, dann zweistunden-wahlschicht an der urne geschoben (StuPa-Wahl), dann Wohung aufräumen, dann Auszählen geholfen, dann noch spät abends über 'ne Stunde Bahn gefahren, jetzt auf das Ergebnis der Wahlen warten...... immer noch müde..... aber vermutlich muss ich heute nacht noch minigolfen und skypen oder sogar noch weggehen..... so deswegen könnte das durchaus sein. aber das war jetzt wirklich Offtopic. 
|
||||||
| 20.01.2006, 23:14 | Ben Sisko | Auf diesen Beitrag antworten » | ||||
Ne warum, war doch mein Fehler... Bzw. wir haben nicht von der gleichen Aufgabe gesprochen... |
||||||
| 20.01.2006, 23:24 | Abakus | Auf diesen Beitrag antworten » | ||||
Wenn man weiß, dass eine Kugel schwerer als die anderen ist, geht es mit 15 Kugeln und 3 Wägungen. Nehme 5 vs. 5 und schaue, was passiert. Sind sie gleich, ist die schwerere Kugel in den nicht gewogenen 5 Kugeln drinne, ansonsten in den 5, wo die Waage schwerer anzeigt. Das wird dann mit 2 vs. 2 wiederholt und beim nächsten Mal mit 1 vs. 1. Hat man diese Information nicht, ob die Kugel schwerer oder leichter ist als die anderen, sehe ich jedoch keine Möglichkeit, es mit 3 Wägungen zu schaffen. ---------------------------------------------------------------------------------------------------------- Bei 12 Kugeln ohne die Information, ob die Kugel schwerer ist oder nicht, brauch ich wohl 4 Wägungen *überleg*. Grüße Abakus
EDIT: Mit 4 geht es sicher; ich hab das Gefühl, dass es irgendwie mit 3 Wägungen geht. |
||||||
| 20.01.2006, 23:47 | JochenX | Auf diesen Beitrag antworten » | ||||
wie oben gesagt; mit einer eindeutig schwereren kugeln kannst du mit n wägungen 3^n kugeln in den griff kriegen 3 wägungen also 27 kugeln dazu zeigt man induktiv: zerlege deine menge 3^n in 3 gleich große mengen, vergleiche zwei mit einer wägung danach weißt du, in welcher de insg. 3^(n-1) großen mengen die schwere drin ist und hast noch n-1 wägungen aber das ist viel einfacher
die einschränkung so ist wirklich ENORM |
||||||
| 21.01.2006, 10:54 | Abakus | Auf diesen Beitrag antworten » | ||||
So gehts mit 3 Wägungen, also die Kugeln seien nummeriert: 1 ... 12. Es ergeben sich einige Fallunterscheidungen: 1. Wägung: 1234 vs 5678 1A.: beides ist gleich, dann: 2-te Wägung: 9+10 vs 2+11, dann: "=" vergleiche 12 vs. 1: "<": 12 leichter, ">": 12 schwerer, "=": nicht möglich ">" vergleiche 9 vs 10: "=": 11 leichter, ">": 9 schwerer, "<": 10 schwerer "<" vergleiche 9 vs. 10: "=": 11 schwerer, ">": 10 leichter, "<": 9 leichter 1B.: 1234 > 5678, dann: 2-te Wägung: 125 vs 369, dann: "=" vergleiche 7 vs. 8: "=": 4 schwerer, ">": 8 leichter, "<": 7 leichter ">" vergleiche 1 vs. 2: "=": 6 leichter, ">": 1 schwerer, "<": 2 schwerer "<" vergleiche 5 vs. 9: "=": 3 schwerer, "<": 5 leichter, ">": nicht möglich 1C.: 1234 < 5678, dann: analog zu 1B Grüße Abakus
|
||||||
| 21.01.2006, 18:10 | smalldiver | Auf diesen Beitrag antworten » | ||||
Ich habe das Problem wie Folgt gelöst: Es werden 3 Haufen mit jeweils 4 Münzen gemacht. Mit maximal 2 mal wiegen kann man sagen, welche beiden Haufen gleich sind. Der Haufen, der sich von den anderen unterscheidet wird. Von den restlichen 4 Münzen werden 3 gegen einander abgewogen. Was dann erneut 2 mal wiegen ergibt. Entweder unterscheidet sich eine von den Münzen von den anderen beiden, dann ist klar welche Münze falsch ist und ob sie schwerer oder leichter ist. Oder alle drei Münzen sind gleich und man weis das die vierte Münze falsch ist. Wobei man dann aber nicht weiß ob sie schwerer oder leichter ist, was man ja eigentlich auch heraus kriegen soll. Das heißt man benötigt in diesem Fall 5 Wägungen. Kann man dieses Problem auch rechnerisch irgendwie Lösen? |
||||||
| 21.01.2006, 18:13 | JochenX | Auf diesen Beitrag antworten » | ||||
wenn 5 die antwort auf a) sein soll "a) Wie viele Wägungen müssen Sie auf einer Schalenwaage ohne Gewichte mindestens durchführen, um die falsche Münze herauszufinden und um gleichzeitig festzustellen, ob sie leichter oder schwerer ist als die übrigen?" dann ist es falsch; antwort ist und bleibt 3, siehe werners link oder abakus lösung (habe davon aber nur den ersten teil durchgepüft) mfg jochen ps: respekt abakus, lange nacht, oder? *duck* |
||||||
| 21.01.2006, 18:24 | smalldiver | Auf diesen Beitrag antworten » | ||||
Ok , die Lösung ist einleuchtend |
||||||
| 21.01.2006, 18:27 | JochenX | Auf diesen Beitrag antworten » | ||||
schau die den link an, schau dir abakus lösung an
in welchem fall von abakus denn? kannst du das GENAUER schreiben? edit nach edit: ah, okay nach deinem edit korrigiere ich den beitrag auch noch: ist damit die a geklärt? |
||||||
| 21.01.2006, 18:30 | smalldiver | Auf diesen Beitrag antworten » | ||||
Jepp. Das passt dann auch mit meiner Rechnung da hab ich nämlich auch drei raus. Und wie ist das jetzt mit 13 Kugeln/Münzen? Ist das dann eine Wägung mehr? |
||||||
| 21.01.2006, 18:41 | JochenX | Auf diesen Beitrag antworten » | ||||
meine meinung steht oben - ich denke mindestens eine mehr, aber wie man das beweist, dass es nicht in 3 gehen kann, weiß ich nicht dass es dann in 4 geht, liefert wieder eine angabe eines möglichen algos die frageformulierung von b) verstehe ich nicht, ich hoffe, da kann wer anders weiterhelfen |
||||||
| 22.01.2006, 22:27 | Ben Sisko | Auf diesen Beitrag antworten » | ||||
Wie beweist man, dass es nicht in einer geht? "Ist offensichtlich"??
|
||||||
| 22.01.2006, 23:32 | Abakus | Auf diesen Beitrag antworten » | ||||
Die Mindestanzahl der Kugeln/Münzen bei diesem Problem ist 3. Bei 2 ließe sich nicht entscheiden, welche jetzt die falsche ist. Mit nur einer Wägung lässt sich nichts feststellen. Bei 2 Wägungen schafft man gerade mal 3 Kugeln. Angenommen bei 3 Wägungen wären 12 Kugeln maximal. Wieviele Kugeln schafft man dann mit 4 oder n Wägungen? Klar ist, dass bei 4 Wägungen mindestens 36 Kugeln zu schaffen sind. Grüße Abakus
|
||||||
| 23.01.2006, 00:07 | AD | Auf diesen Beitrag antworten » | ||||
Da will ich auch mal noch meinen Senf beisteuern, und zwar zum Beweis der Unmöglichkeit - allerdings erst ab 14 Münzen: Jede Wägung kann drei mögliche Zustände (kleiner, gleich, größer) anzeigen, also können Wägungen maximal Situationen voneinander unterscheiden. Macht bei drei Wägungen also 27 Situationen. Bei mindestens 14 Münzen UND der Ungewissheit, ob die andersgewichtige Münze leichter oder schwerer ist, hat man mindestens 2*14=28 Situationen zu unterscheiden... Einfachste Kombinatorik - leider klappt der Beweis für 13 Münzen nicht. |
||||||
| 23.01.2006, 00:15 | Poff | Auf diesen Beitrag antworten » | ||||
Nein, das geht mit 3, hab ich als Kind schon mal gelöst. Hier müsste auch ein Thread sein in dem Lösungsweg steht. Heute mach ich Riesenbogen um solche Dinge. |
||||||
| 23.01.2006, 00:24 | JochenX | Auf diesen Beitrag antworten » | ||||
hallo poff schau mal, abakus hats schon selbst gefunden!
|
||||||
| 23.01.2006, 00:28 | Poff | Auf diesen Beitrag antworten » | ||||
gg wie gesagt, Riesenbogen ich hab das hier nicht durchgelesen ... |
||||||
| 23.01.2006, 03:48 | Ben Sisko | Auf diesen Beitrag antworten » | ||||
Also irgendwie bin ich zu begriffsstutzig für diesen Beweis, jedenfalls versteh ich ihn nicht. Wie geht denn hier ein, dass ich die Münzen/Kugeln sinnvoll gruppieren kann? Und pro Wägung tritt doch dann eine Situation ein, nehmen wir mal n=1. Was sagt es dann aus, dass diese Wägung maximal 3 Situationen voneinander unterscheiden kann? Zumindest geh ich mal davon aus, dass mein Unverständnis für diesen Beweis auch daran schuld ist, dass ich aber auch gar keine Idee hatte, wie man das beweisen soll... 
|
||||||
| 23.01.2006, 09:03 | AD | Auf diesen Beitrag antworten » | ||||
Nochmal rekapitulieren - wie lautet die Aufgabenstellung:
1L, 1S, 2L, 2S, ... , mL, mS durch n Wägungen auseinanderzuhalten. Ist nun aber , dann gibt es bei jeder Wägestrategie nach Schubfachprinzip mindestens ein Wägeergebnis, dem mehrere dieser Situationen angehören müssen - oder anders formuliert: Bei diesem Wägeergebnis kann man nicht zweifelsfrei sagen, welche Münze wie andersgewichtig als die anderen ist! Die Gruppierung der Münzen ist für diesen Beweis völlig belanglos, es handelt sich hier lediglich um eine Maximalabschätzung. D.h., es ist kein konstruktiver Beweis für die Machbarkeit einer Wägestrategie, sondern lediglich ein Beweis für die Unmöglichkeit einer solchen Strategie. Für m=13 und n=3 ist damit allerdings kein Blumentopf zu gewinnen, falls das unmöglich sein sollte, dann müssen feinere Methoden für den Unmöglichkeitsbeweis ran. |
||||||
| 23.01.2006, 09:09 | SimMew2(1) | Auf diesen Beitrag antworten » | ||||
wie wäre es denn mit der unterteilung in 4;4;5 1. Wägung: 4v4 Waage schlägt aus: o.b.d.A sei es die linke seite, welche leichter ist. nun nimmt man die 4 kugeln der linken seite und wiegt 2v2: kein ausschlag: gewissheit, dass eine der 13 kugeln schwerer ist als die anderen und die ges. kugel befindet sich im 2. Haufen ausschlag: eine der 13 kugeln ist leichter als die anderen, und diese kugel ist im 1. haufen falls aber bei der ersten wägung kein ausschlag zu verzeichnen ist, ist die kugel im 5er haufen 2. Wägung: 2v2(bei 5er haufen 2v2, 1 bleibt draussen) 3. Wägung: 1v1 (entfällt, falls bei 5er wägung 2v2 keinen ausschlag zeigt) siehe da, 3 wägungen @all: wie lange braucht die anmeldungsmail? hab gestern nachmittag ca 16 uhr registriert, aber noch keine antwort bekommen... |
||||||
| 23.01.2006, 09:55 | AD | Auf diesen Beitrag antworten » | ||||
@SimMew2 OK, betrachten wir den Fall, dass die erste Wägung Gleichstand ergibt, dann ist die gesuchte Kugel im Fünferhaufen, und wir wissen nicht, ob sie leichter oder schwerer als die anderen vier ist. Ohne mir deine restlichen, sehr kurzen Betrachtungen anzusehen, kann ich sofort sagen, dass es mit zwei verbleibenden Wägungen nicht klappt, die Sache in diesem Teilfall zu klären: Siehe meinen letzten Beitrag, diesmal mit . P.S.: Zur Anmeldungssache: Manche e-mail-Adressen machen hier Probleme Anmeldung web.de vielleicht liegt es daran. EDIT: Nach reiflicher Überlegung weiß ich jetzt, warum 13 auch unmöglich ist: An der ersten Wägung müssen mindestens 9 Kugeln beteiligt sein (siehe Anfang des Beitrags). Es ergibt sich auch, dass es nur sinnvoll ist, in beiden Waagschalen jeweils gleichviele Kugeln zu haben (der Informationsgewinn bei ungleichen Anzahlen ist einfach zu gering, bei geringen Gewichtsunterschieden der "anderen" Kugel sogar Null Informationsgewinn), bei der ersten Wägung also mindestens jeweils 5. Die erste Wägung möge nun das Ergebnis haben, dass der erste Haufen mit 1..5 leichter als der Haufen 6..10 sei. Dann gilt es mit zwei verbleibenden Wägungen die Situationen 1L, ... , 5L, 6S, ... , 10S auseinanderzuhalten, was mit der gleichen Argumentation wie oben unmöglich ist. Also ist die Sache mit 13 Kugeln und 3 Wägungen nicht möglich. |
||||||
| 23.01.2006, 14:32 | Ben Sisko | Auf diesen Beitrag antworten » | ||||
Danke für deine Erklärung, Arthur,jetzt ist's auch bei mir angekommen
|
||||||
| 23.01.2006, 16:53 | Abakus | Auf diesen Beitrag antworten » | ||||
Mit Arthurs Argumentation lässt sich die Frage, wieviele Kugeln mit 4 Wägungen zu schaffen sind, nun auch beantworten: es sind genau 36. Grüße Abakus
|
||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
