Bananenproblem |
| 31.12.2010, 19:03 | Tschey | Auf diesen Beitrag antworten » |
| Bananenproblem Folgende Aufgabe: Einige Gorillas wollen sich einen Haufen Bananen teilen. Als jedoch 3 Bananen übrig bleiben streiten sich die Gorillas, wobei einer zu Tode kommt. Die übrigen 16 Gorillas wollen erneut Teilen... Diesmal bleiben jedoch 10 Bananen übrig. Nachdem nun wieder ein Gorilla das Leben lassen musste geht das Teilen endlich auf. Wie viele Bananen haben die Gorillas bekommen? Meine Ideen: Alles Andere als offensichtlich 
Viel Spaß damit! |
||
| 31.12.2010, 20:25 | Grouser | Auf diesen Beitrag antworten » |
Auf die Lösung komme ich schon. Allerdings durch besseres Raten. Nicht gerade mathematisch. Wobei ich mich frage, ob es eine elegante mathematische Lösung gibt, die ohne irgendwelche Entwicklungen auskommt. Irgendwie erinnert mich das Ganze sehr an die trapdoor im RSA Algorithmus, wobei hier die andere Seite des Problems beleuchtet wird. Da ich mich allerdings bisher mit dem Rechnen mit Restklassen (oder dem euklidischen Algorithmus) noch nicht wirklich auseinandergesetzt habe, mag es natürlich durchaus eine elegante Lösung des Problems geben. Spätestens wenn ich mich mal in irgend einem Bus oder Wartezimmer langweile, werde ich dieses Problem weiter durchdenken...
|
||
| 01.01.2011, 13:14 | Gualtiero | Auf diesen Beitrag antworten » |
Hab eine Lösung, sollte die niedrigst mögliche sein: 3930? (Zeile markieren) Bin aber nur mithilfe einer selbst geschriebenen Routine draufgekommen; wie Grouser schon sagte, seeehr unmathematisch. 
|
||
| 01.01.2011, 16:10 | lgrizu | Auf diesen Beitrag antworten » |
Sooo "unmathematisch" finde ich das gar nicht (ist nicht besonders schwer, aber man muss nicht "rumprobieren"). Gesucht ist die kleinste positive Lösung des Systems Und das kann man dann lösen. |
||
| 15.07.2011, 14:47 | GRiM | Auf diesen Beitrag antworten » |
Das Schlagwort hinzu ist der chinesische Restsatz. Dieser liefert, im Beweis, eine konstruktive Methode, dieses Problem zu lösen. Wir stellen als ersten fest, dass 15, 16 und 17 teilerfremd sind. Damit sind auch 15 und 16*17 = 272, etc teilerfremd. Damit gibt es a1, a2 in den ganzen Zahlen, so dass wir schreiben können: 1 = a1 * 272 + a2 * 15 etc. Diese Zahlen finden wir mit dem euklidischen Algorithmus: 1 = -8* 240 + 113 * 17 1 = -1 * 255 + 16 * 16 1 = -7 * 272 + 127 * 15 Nun definieren wir: x1 = -8 * 240, x2 = -1 * 255 und x3 = -7 * 272. Diese Zahlen haben nun folgende Eigenschaft (am Beispiel von x1): x1 ist durch 15 und 16 teilbar, hat aber beim Teilen durch 17 den Rest 1. Nun setzten wir die gewuenschten Reste ein und erhalten als Loesung die Zahl: 3*x1 + 10*x2 + 0*x3 = -8310. Da die Affen bestimmt eine positive Anzahl von Bananen bekommen haben, addieren wir solange 15*16*17 = 4080 bis wir eine positive Zahl Bananen haben. Das ist dann die schon oben erwähnt 3930. |
||
|
|