| Autor |
Beitrag |
    
helmut (Hoocker)
| | Veröffentlicht am Mittwoch, den 06. Februar, 2002 - 22:30: | 
|
hallo,
hab da mal wieder ein tolles rätsel entdeckt:
Ein Abenteurer findet einen Goldschatz bestehend aus 10 Säcken, prall gefüllten mit
Goldmünzen. Jede Goldmünze wiegt 10 g. Ein oder mehrere Säcke sind aber mit
Imitationen gefüllt, wobei eine "falsche" Münze 9,9 g wiegt. Die echten Münzen sind
von den falschen äußerlich nicht zu unterscheiden.
Wie kann man unter einmaliger Verwendung einer digitalen Waage herausfinden,
welche Säcke komplett mit echten und welche mit falschen Münzen gefüllt sind?
(Beachte: Ein Sack enthält entweder nur Goldmünzen oder nur Imitationen.)
wenn nur ein sack imitationen enthalten würde, hätte ich die lösung, aber da ein oder mehrere säcke imitationen enthalten können ???????
hat jemand einen ansatz zur lösung ??
mfg helmut |
funhh
| | Veröffentlicht am Mittwoch, den 06. Februar, 2002 - 23:51: |
|
ich versuchs mal so zu schreiben, das möglichst keiner es versteht, der noch keinen ansatz für das "einfachere" problem hat:
ich denke, dein bisheriger ansatz ist da so eine sache mit "immer plus 1". wenn du es statt dessen mal mit potenzieren versuchst (2^(i-1) dürfte es tun), müsste es klappen.
...mmmhhh, wirklich kapieren tu ich meinen text da nicht, aber vielleicht ist das ja ganz gut so...:-) |
SKotty
| | Veröffentlicht am Donnerstag, den 07. Februar, 2002 - 05:45: |
|
Hi funhh,
Dein Ansatz ist richtig, problematisch nur, wenn die Säcke jeweils maximal 500 Münzen enthalten *fG
Gruß SKotty |
funhh
| | Veröffentlicht am Donnerstag, den 07. Februar, 2002 - 14:54: |
|
grummel...irgendwie wußte ich, dass dieser einwand kommen würde...
allerdings finde ich, das ist eine frage, die man mal näher betrachten sollte:
ist es auch möglich, das ganze mit kleineren zahlen zu lösen?
damit auch eine diskussionsgrundlage da ist, schreibe ich jetzt nochmal die lösung genau auf:
nimm 2^0=1e münze aus dem ersten sack, 2=2^1 münzen aus dem zweiten,..., 512=2^9 münzen aus dem zehnten. aus der abweichung dieses gewichts von dem, das 1023 echte münzen hätten, lässt sich dann alles weitere folgern. das tolle an diesem vorgehen ist ja, dass jede positive zahl eindeutig als summe von verschiedenen 2erpotenzen darstellbar ist.
die frage ist also: muß ich wirklich mindestens 512 münzen in einem der goldsäcke haben, oder geht es auch mit weniger...?
vielleicht gibt es aber auch eine ganz andere strategie, um das ganze herauszufinden.
ciao, euer fun |
hd
Unregistrierter Gast
| | Veröffentlicht am Mittwoch, den 01. Mai, 2002 - 16:18: |
|
309. Soviele Münzen muss man mindestens in einem der Goldsäcke haben.
Sehr schönes Rätsel (hab's leider zu spät entdeckt)
|
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1001
Registriert: 07-2000
| | Veröffentlicht am Mittwoch, den 01. Mai, 2002 - 20:23: |
|
funhh's Strategie finde ich ziemlich einleuchtend. Wie kommst du auf 309?? |
helmut (hoocker)
Mitglied
Benutzername: hoocker
Nummer des Beitrags: 23
Registriert: 12-2001
| | Veröffentlicht am Mittwoch, den 01. Mai, 2002 - 20:31: |
|
hi,
die lösung "512 münzen" ist die einzig richtige.
ich frag mich auch, wie hd auf 309 münzen kommt.
vielleicht zeigt er uns mal seinen rechenweg und erklärt ihn uns ;-)
mfg helmut |
hd
Unregistrierter Gast
| | Veröffentlicht am Donnerstag, den 02. Mai, 2002 - 07:27: |
|
Die Aufgabe (allerdings nicht mit 10 Goldsäcken) erscheint bereits 1838 in der Literatur: Ein gewisser Herr M. A. Stern veröffentlichte sie im angesehenen Journal für Reine und Angewandte Mathematik. Im 20. Jh. hat einer der ganz Großen - Paul Erdös (1913–1996) - das Problem wieder zur Diskussion gestellt und es ist in die Kombinatorik-Literatur als "Sum Packing Problem of Erdös" eingegangen. Also das Problem, eine n-elementige Menge von natürlichen Zahlen zu finden, sodass alle Teilmengen verschiedene Summen ergeben und das größte Element der Menge möglichst klein ist.
Conway (ja, der mit dem Game of Life) and Guy konstruierten 1967 eine rekursive Lösung mit der man aus der Lösung für n "Goldsäcke" auf (n+1) schließen kann, Krewas bewies 1983 die Minimalität.
Und hier die Lösung für 10 Goldsäcke:
148 Münzen aus Sack 1,
225 Münzen aus Sack 2,
265 Münzen aus Sack 3,
285 Münzen aus Sack 4,
296 Münzen aus Sack 5,
302 Münzen aus Sack 6,
305 Münzen aus Sack 7,
307 Münzen aus Sack 8,
308 Münzen aus Sack 9,
309 Münzen aus Sack 10.
Es ist übrigens nur 309 minimal. Die anderen Zahlen ergeben sich aus der bequemen Rekursion. Sie könnten auf verschiedene Weise variiert werden, es geht also etwa auch mit wesentlich weniger Münzen aus Sack 1; diese Varianten kann man aber nur durch Probieren herausfinden.
PS: Lieber Helmut, sei bitte etwas vorsichtiger mit "einzig richtigen" Behauptungen.
|
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1005
Registriert: 07-2000
| | Veröffentlicht am Donnerstag, den 02. Mai, 2002 - 19:23: |
|
Wow, bin beeindruckt! Wie die Intuition doch manchmal täuschen kann ... Ja, mit seinen Äußerungen sollte man manchmal vorsichtig sein! |
helmut (hoocker)
Mitglied
Benutzername: hoocker
Nummer des Beitrags: 24
Registriert: 12-2001
| | Veröffentlicht am Donnerstag, den 02. Mai, 2002 - 19:48: |
|
hi,
sorry, werde mich in zukunft mit solchen äusserungen zurückhalten.
viele leute haben diese aufgabe berechnet, alle kamen auf 512 münzen. scheinbar haben wir uns alle doch gewaltig getäuscht :-((
mfg helmut |
hd
Unregistrierter Gast
| | Veröffentlicht am Freitag, den 03. Mai, 2002 - 14:26: |
|
Hallo Zaph, hallo Helmut!
Ihr habt euch wahrscheinlich gefragt: "Warum nennt der Kerl das ein schönes Rätsel, wenn es eh nur drum geht, ob man die Arbeiten von Krewas und Conway kennt oder nicht?" - Nun, das ist eben nicht so!
funhh hat die Kernfrage gestellt, es fehlte ihm nur noch die Initialzündung: der Schlüssel zum Ganzen ist die Beobachtung, dass man in dem Rätsel die 10 durch eine beliebige natürliche Zahl ersetzen kann, ohne den Sinn des Rätsels irgendwie zu verändern. Und das riecht untrüglich nach Rekursion: Löse die Aufgabe für n=1,2,3... und du wirst ein Schema erkennen! Und auf den verschlungenen Pfaden von Versuch und Irrtum wird man dabei durch immer neue Einsichten und Erkenntnisse belohnt.
n=1, n=2: Der Anfang.
Alles klar, eindeutige Minimallösungen (1), (1,2).
n=3: Der erste Hoffnungsschimmer.
4 als Minimum wird sofort klar, aber (1,2,4) ist nicht die einzige Lösung - (2,3,4) heißt die Alternative!
n=4: Der Durchbruch.
Nach einigem Probieren (noch mit Zettel und Bleistift) findet man neben (1,2,4,8) die Lösung (3,5,6,7) - der Bann ist gebrochen, es muss keine Zweierpotenz sein!
n=5, n=6, n=7: Die Rekursion?
Viel Glück/Erfahrung/Instinkt/was-auch-immer ist nötig: Als Werkzeug muss zumindest ein programmierbarer Taschenrechner her sonst wird's zu mühsam. Doch nun schlägt das Imperium zurück; man findet immer neue Varianten, viel zu viele Möglichkeiten - wo ist das Schema? Mit genügend Ausdauer und sicher auch mit der richtigen Idee unbewusst im Hinterkopf hat man (irgendwann) die Schlüssel-Folge vor Augen:
(1), (1,2), (2,3,4), (3,5,6,7), (6,9,11,12,13), (11,17,20,22,23,24), (20,31,37,40,42,43,44)
Na? Nichts Auffälliges?
Immer eine gute Idee: Differenzenfolge!
(-), (1), (1,1), (2,1,1), (3,2,1,1), (6,3,2,1,1), (11,6,3,2,1,1)
Aber jetzt! So 'ne Art verkehrt hingeschriebene Fibonacci-Folge (Summe der Vorgänger, zuerst 2, dann 3 Vorgänger).
Der weitere Weg führt dann über diese sogenannte Stern-Folge direkt zur Conway-Rekursion. Der Beweis von Krewas steht natürlich auf einem ganz anderen Blatt geschrieben!
Aber zumindest bis zum Durchbruch bei n=4 kann sicher jeder kommen - wenn, ja wenn, er die Initialzündung erhält.
In diesem Sinne: ein sehr schönes Rätsel!
|
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1015
Registriert: 07-2000
| | Veröffentlicht am Freitag, den 03. Mai, 2002 - 18:50: |
|
Ja, vielen Dank, sehr interessant!
Aber wenn ich die Folge nach deiner Regel weiterbilde:
125, 68, 37, 20, 11, 6, 3, 2, 1, 1
komme ich auf:
125, 193, 230, 250, 261, 267, 270, 272, 273, 274
Das Bildungsgesetz der Differenzenfolge wird also für größere Werte wohl nocht etwas komplizierter werden. Ist die Differenzenfolge die "Stern-Folge"?
In der Tat, eine sehr interessante Fragestellung, obwohl es eigentlich gar nicht Bestandteil von helmuts Rätsel war. |
hd
Unregistrierter Gast
| | Veröffentlicht am Freitag, den 03. Mai, 2002 - 19:50: |
|
Ja, die Stern-Folge ist die Differenzenfolge und sie wird in der Tat komplizierter. Aber das Prinzip bleibt: Summe einiger Vorgänger; die Anzahl der Summanden ist der aufgerundete Wert von (wurzel(8*n-7)-1)/2.
Für n=10 erhält man so: (148,77,40,20,11,6,3,2,1,1)
Aber ich wollt ja nur zeigen: Wer einmal die Lösung für n=4, (3,5,6,7), mit elementaren Mitteln gefunden hat, wird nie und nimmer glauben, dass 512 das Minimum für n=10 sein könnte!
|
|
