Wägungen um fälsche Münze zu finden

Neue Frage »

Babe Auf diesen Beitrag antworten »
Wägungen um fälsche Münze zu finden
Hallo Leute!
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!!! Prost
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?
 
 
smalldiver Auf diesen Beitrag antworten »

Das thema ist auch schon vorhanden nur mit anderen Zahlen. Guck mal unter
Wieviele Fragen um Zahl zu erraten?
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.
riwe Auf diesen Beitrag antworten »

kugeln usw.
von einem, der schon weiß, wie man einen link einfügt
werner
Ben Sisko Auf diesen Beitrag antworten »

Zitat:
Original von LOED
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.


Kann ich auch... Big Laugh

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...
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....
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 Big Laugh
JochenX Auf diesen Beitrag antworten »

Zitat:
Original von Ben Sisko
Wenn ungleich, mach mit den restlichen 7 2 vs. 2.

wenn die ersten 4vs4 ungleich sind, dann ist die andere unter ihnen
warum also mit den restlichen 7 weiterarbeiten??
Ben Sisko Auf diesen Beitrag antworten »

Ungleich und gleich verwechselt, so ist's richtig:

Zitat:
Original von Ben Sisko
OK, fang auch mit 4 vs. 4 an. Wenn ungleich ist, ist klar wie's weitergeht, oder?
Wenn gleich, 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...


Da hättest du aber jetzt von allein drauf kommen können... Forum Kloppe Augenzwinkern
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
Ben Sisko Auf diesen Beitrag antworten »

Zitat:
Original von LOED
fall a) gleich
dann bleiben 3 kugeln, von denen eine unterschiedlich schwer ist (unbekannt ob leichter oder schwerer); und dann?


"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.

Zitat:
Original von LOED
fall b) ungleich:
dann sind entweder eine von zwei leichter; oder eine von den anderen beiden schwerer; und dann?


Eine Seite ist schwerer, also ist die schwerere Kugel eine dieser beiden. Wiege nach, welche es ist!
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:
Zitat:
eine unterscheide sich von den übrigen durch ihr Gewicht.

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 Augenzwinkern
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 Hammer

Zitat:
Original von LOED
schau dir den link oben an, den werner, der inzwischen links posten kann *g*, gepostet hat.....
das rätsel ist der hammer Augenzwinkern


Übrigens: Ich hab's ihm erklärt Big Laugh
JochenX Auf diesen Beitrag antworten »

Zitat:
Original von Ben Sisko
Und ich wunder mich schon, warum du heute so begriffsstutzig bist Hammer

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. smile
Ben Sisko Auf diesen Beitrag antworten »

Zitat:
Original von LOED
so deswegen könnte das durchaus sein.


Ne warum, war doch mein Fehler...
Bzw. wir haben nicht von der gleichen Aufgabe gesprochen...
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 smile

EDIT: Mit 4 geht es sicher; ich hab das Gefühl, dass es irgendwie mit 3 Wägungen geht.
JochenX Auf diesen Beitrag antworten »

Zitat:
Wenn man weiß, dass eine Kugel schwerer als die anderen ist, geht es mit 15 Kugeln und 3 Wägungen.


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 smile
die einschränkung so ist wirklich ENORM
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 smile
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?
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*
smalldiver Auf diesen Beitrag antworten »

Ok , die Lösung ist einleuchtend
JochenX Auf diesen Beitrag antworten »

schau die den link an, schau dir abakus lösung an

Zitat:
Wenn 9 und 10 ungleich ist

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?
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?
JochenX Auf diesen Beitrag antworten »

Zitat:
Original von smalldiver
Und wie ist das jetzt mit 13 Kugeln/Münzen? Ist das dann eine Wägung mehr?

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
Ben Sisko Auf diesen Beitrag antworten »

Zitat:
Original von LOED
aber wie man das beweist, dass es nicht in 3 gehen kann, weiß ich nicht


Wie beweist man, dass es nicht in einer geht? "Ist offensichtlich"?? Augenzwinkern
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 smile
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.
Poff Auf diesen Beitrag antworten »

Zitat:
Original von Abakus

Bei 12 Kugeln ohne die Information, ob die Kugel schwerer ist oder nicht, brauch ich wohl 4 Wägungen *überleg*.

Grüße Abakus smile



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.
JochenX Auf diesen Beitrag antworten »

hallo poff
schau mal, abakus hats schon selbst gefunden! smile

Zitat:
Original von Abakus
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 smile
Poff Auf diesen Beitrag antworten »

gg

wie gesagt, Riesenbogen
ich hab das hier nicht durchgelesen ...
Ben Sisko Auf diesen Beitrag antworten »

Zitat:
Original von Arthur Dent
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...


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... unglücklich
AD Auf diesen Beitrag antworten »

Nochmal rekapitulieren - wie lautet die Aufgabenstellung:

Zitat:
Original von Babe
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 ?
Wenn wir m Münzen 1..m haben und zusätzlich feststellen müssen, ob die eine andersgewichtige Münze leichter (L) oder schwerer (S) als die anderen Münzen ist, dann gilt es die 2m Situationen

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.
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...
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.
Ben Sisko Auf diesen Beitrag antworten »

Danke für deine Erklärung, Arthur,jetzt ist's auch bei mir angekommen smile
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 smile
Neue Frage »
Antworten »



Verwandte Themen

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