Das Räuberproblem

RoToR · Apr 28, 2009

Hallo Leuts,
Ich brauch mal Hilfe bei einer Aufgabe, die wir im Informatikuntericht aufbekommen haben. Aufgabe lautet folgendermaßen:

Es geht um fünf Räuber, die einen Schatz erbeutet haben. Der eine Räuber will Nachts den Schatz gerecht unter allen 5 aufteilen, damit er sich nicht betrogen fühlt. Er verteilt das Geld also auf 5 Haufen, aber ein Taler bleibt übrig. Er nimmt sich dann einfach einen Haufen + den übrigen Taler. Dann erwacht ein 2. Räuber und macht das gleiche mit dem übrigen Geld. Auch bei ihm bleibt bei 5 Haufen ein Taler übrig. Das machen alle 5 und nehmen sich so immer ihren vermeintlichen Anteil. Am nächsten Morgen teilen sie dann das restliche Geld in der Truhe was ohne Rest möglich ist.

So nun die Frage: Wie viele Taler erhielten die Räuber, wenn die Truhe maximal 10000 Taler fasste?

Es geht mir also darum, dass mir jemand bei dieser Aufgabe hilft, da ich es in Javascript darstellen soll, aber dafür muss ich erstmal einen Ansatz beim mathematischen Teil haben.

Wäre sehr glücklich wenn mir jemand helfen könnte,
MFG RoToR

James · Apr 28, 2009

Hmm, ich kann dir jetzt grad nur soviel sagen, dass der Gesamtbetrag dann wohl aus x*5+1 Talern besteht für x € IN

Macht Räuber 2 dann nur noch 4 Stapel oder doch 5?

Osbes · Apr 29, 2009

James_Bond said:
Hmm, ich kann dir jetzt grad nur soviel sagen, dass der Gesamtbetrag dann wohl aus x*5+1 Talern besteht für x € IN

Macht Räuber 2 dann nur noch 4 Stapel oder doch 5?

Der 2. Räuber teilt den Rest wieder in 5 Stapel auf.

####

@RoToR
Das ist ein sehr sehr simples Problem, wenn man die Galoistheorie kennt oder ein wenig über die Anzahl irreduzibler Polynome über endlichen Ringen weiß (Algebra I, man kann aber auch über die Zahlentheorie rangehen). So ist die Lösung nämlich gleich der (Anzahl der normierten irreduziblen Polynome vom Grad 5 im Restklassenring 5) * 5 + 1.
Aber ich glaube dieses Vorwissen ist nicht vorhanden, daher erkläre ich es anders.

Zunächst sollten wir eine andere Frage bentworten, nämlich wieviele Münzen min. notwendig sind, damit dies geht.

Sei nun r die Anzahl der Münzen die am Ende noch da sind, dann hat der letzte Räuber

Code:

5
- r + 1
4

Münzen gehabt.

Somit hat der vorletzte Räuber

Code:

5   5
- ( - r + 1 ) + 1
4   4

Münzen gehabt.

usw.... bis zum 1. Räuber, bei dem waren es

Code:

5   5   5   5   5
- ( - ( - ( - ( - r + 1 ) + 1 ) + 1 ) + 1 ) + 1
4   4   4   4   4

Münzen.

Wenn wir dies einmal ausrechnen erhalten wir

Code:

3125 * r + 8404
---------------
      1024

Münzen.

Nun soll dies ja eine ganze Zahl sein, also muss 3125 * r + 8404 durch 1024 teilbar sein.

Dies können wir auch schreiben als

Code:

(3072 + 53) * r + (8192 + 212)

Da 3072 und 8192 schon durch 1024 teilbar sind ist die Lösung äquivalent zur Frage wann 53 * r + 212 durch 1024 teilbar ist.
Dies schreiben wir jetzt wieder etwas anders:

Code:

53 * r + (4 * 53)

Aufgrund der Primfaktorzerlegung von 1024 spielt die 53 für uns keine Rolle, da die 53 selbst eine Primzahl ist (wir können also alles durch 53 teilen ohne die Frage zu verändern) und somit müssen wir jetzt nur noch fragen, wann folgendes durch 1024 teilbar ist:

Code:

r + 4

und dies geht natürlich ab r = 1024 - 4 = 1020.

Somit müssen zum Schluss mindestens 1020 Münzen da gewesen sein und zum Anfang müssen es min. 3121 gewesen sein.

Ferner kann man auch sagen, dass bei gleicher Aufgabe und n Räubern immer min.
n^n - n + 1 Münzen vorhanden sein müssen und zum Schluss (n-1)^n - (n-1) Münzen übrig sind.

Code:

Räuber | Anfang | Schluss
-------------------------
  1    |      1 |      0
  2    |      3 |      2
  3    |     26 |      6
  4    |    253 |     78
  5    |   3121 |   1020
  6    |  46651 |  15620
  7    | 823537 | 279930
 ...   |   ...  |   ...

Deine Aufgabe wäre es jetzt zu zeigen, für welche weiteren Zahlen es geht (schließlich können es ja auch mehr Münzen gewesen sein)

Kleiner Tip, falls du nicht weiterkommst:

RoToR · Apr 29, 2009

Vielen Dank, das ist extrem Hilfreich und wirklich ausführlich beschrieben. Dickes Lob :top

Jetzt kann ich mich endlich an Javascript machen, ma sehen wie weit ich da komme ^^'

Osbes · Apr 29, 2009

Du kannst deinen Quelltext ja ebenfalls hier posten

Es fehlt halt nocht die Antwort auf die Frage für welche weiteren Zahlen es geht, wenn man nämlich max. 10.000 Münzen hat geht es bei 5 Räubern für 3 verschiedene Zahlen.

Wenn man z.b. max. 10^9 Münzen hat geht es für 320.000 Zahlen

RoToR · Apr 29, 2009

Ok Quelltext werde ich posten, kann aber noch ne Weile dauern, weil noch bis nächste Woche Zeit.
Wie das mit den weiteren Zahlen ist, weiß ich jetzt leider nicht wirklich, da muss ich erst mal gucken :/

James · Apr 29, 2009

Anzahl irreduzibler Polynome über endlichen Ringen

oO

Was ist das?

Todesgeist · Apr 29, 2009

Osbes is mathelehrer^^ hmm die konnt ich sogar lösen und ich bin nich mathebagabt -> böser RoToR

kennst du polynommathematik? das is das

eine immerwiedergehende "schleife" is das ganz grop ausgedrückt

SO gemeint:
- ( - ( - ( - ( - r + 1 ) + 1 ) + 1 ) + 1 ) + 1

so ähnlich is das in der chemi bei den polynomen bei ethen wenn es zu polyethelen(im volksmunde) plastik wird

Code:

Formel:
 {  h }
 {  | }
-{ -c-}-
 {  | }
 {  h }n

h= wasserstoff
c= kohlenstoff
n=anzahl der polyethenmolekühle
die 4 untereinanderstehenden { sollten eine große klammer sein 
die normal eckig is aber ecksig sie blöd aus^^

RoToR · Apr 29, 2009

Todesgeist said:
Osbes is mathelehrer^^ hmm die konnt ich sogar lösen und ich bin nich mathebagabt -> böser RoToR

Das kann ja jeder behaupten, nachdem hier die Lösung gepostet wurde

Du kannst ja dann die Lösung für Javascript posten, wenn du möchtest

Todesgeist · Apr 29, 2009

hmmm ne is nich meine ha also lass mal^^
und noch ne dummmmmmmmmmmmmmmme frage von miiiiiiiir was isn javascript?^^
*mich dumm fühl*

Osbes · Apr 29, 2009

Todesgeist said:
Osbes is mathelehrer^^

Nein, ich studiere aber Mathematik - und ganz bestimmt NICHT auf Lehramt ^^

James_Bond said:
oO

Was ist das?

Grob gesagt sind Ringe mathm. "Gebilde" in denen bestimmte Rechengesetze gelten müssen.
Die ganzen Zahlen mit der normalen Multiplikation und Addition bilden z.b. einen Ring (sogar einen Integritätsring, also einen abelschen und nullteilerfreien Ring).

Irreduzible Polynome über R sind Polynome die man nicht mehr zerlegen kann und somit in R keine weiteren Nullstellen besitzen.

Und ein Polynom vom Grad n über R sieht immer so aus:
a_n * x^n + ... + a_1 * x + a_0 mit a_n Element aus R und a_n =!= 0

So ist z.b. x^3 + 1 ein Polynom in den reelen Zahlen, welches aus den irreduziblen Polynomen x + 1 und x^2 - x + 1 besteht.
Ferner besitzt also x^2 - x + 1 keine Nullstelle in den reelen Zahlen.

Todesgeist · Apr 29, 2009

n= natürliche zahlen
R= reele zahlen
...
vermut ich mal^^
hmm is fürne 10te klasse zu hoch naja in 3 jahren kappier ich das auch (will ich hoffen dann hab ich hoff ichs abbi) zu hoch^^

Osbes · Apr 29, 2009

R ist irgendein Ring
n ist eine natürliche Zahl, ja
Generell ist das dort oben aber sehr unsauber definiert, was aber auch daran liegt, dass ich sonst erst andere mathematische Begriffe einführen müsste.

Naja, sofern du nichts studieren willst was tiefer in die Mathematik eingeht muss man es nicht verstehen.
Und wenn doch, muss du es erst im Studium lernen

Todesgeist · Apr 29, 2009

Osbes said:
R ist irgendein Ring
n ist eine natürliche Zahl, ja
Generell ist das dort oben aber sehr unsauber definiert, was aber auch daran liegt, dass ich sonst erst andere mathematische Begriffe einführen müsste.

Naja, sofern du nichts studieren willst was tiefer in die Mathematik eingeht muss man es nicht verstehen.
Und wenn doch, muss du es erst im Studium lernen

jaja schon verstanden^^ naja glaub ich wart mla auf sein quelltest ah und was is nun nen javascript?^^

Megumi · May 4, 2009

Osbes said:
Du kannst deinen Quelltext ja ebenfalls hier posten
Es fehlt halt nocht die Antwort auf die Frage für welche weiteren Zahlen es geht, wenn man nämlich max. 10.000 Münzen hat geht es bei 5 Räubern für 3 verschiedene Zahlen.[...]

Das ist komisch da ich es mit RoToR duchgegangen bin und den javascript code dafür geschrieben habe. Mit 3121 hast du recht aber die nächste Anzahl Münzen danach mit der es geht ist erst 18746.

Osbes · May 4, 2009

Ingoneur said:
Das ist komisch da ich es mit RoToR duchgegangen bin und den javascript code dafür geschrieben habe. Mit 3121 hast du recht aber die nächste Anzahl Münzen danach mit der es geht ist erst 18746.

Das ist ziemlich falsch, dass dort nichts dazwischen kommt.
Aber das zeigt eigentlich nur, dass ihr euch die Konstruktion dieser Zahl nochmal anschauen müsst, bzw. ihr dies nicht richtig verstanden habt (nicht negativ gemeint, nur da liegt mMn das Problem).

Bsp.:
Anfang: 6246
Nach 1. Räuber: (6246 - 1) * 4/5 = 4996
Nach 2. Räuber: (4996 - 1) * 4/5 = 3996
Nach 3. Räuber: (3996 - 1) * 4/5 = 3196
Nach 4. Räuber: (3196 - 1) * 4/5 = 2556
Nach 5. Räuber: (2556 - 1) * 4/5 = 2044

läuft also auch mit anderen Zahlen kleiner als 10.000

Megumi · May 4, 2009

2044 / 5 = 408,8.. am Ende soll es ja aufgehen, du hast einfach die weitere Bedingung übersehen.

Osbes · May 4, 2009

Oh, das habe ich in der Tat gar nicht beachtet, darauf bin ich in der Konstruktion auch gar nicht eingegangen ^^.

Dann gilt es in dem konkreten Fall natürlich immer nur für jede 5. Zahl, für die obiges gilt (und da nur 3 Zahlen < 10.000 drin sind dann auch für keine andere als 3121) und der Fehler liegt dann natürlich bei mir, dass ich dies nicht beachtet habe.

Wenn man diese Zusatzbedingung einbaut müsste man natürlich auch die entsprechende Startformel ändern.
Die Startwerte + diese Bedingung wären dann übrigens: (lässt sich mit einer geänderten Formel leicht bestimmen)

Code:

Räuber |    Anfang    |    Schluss
------------------------------------
   1   |            1 |            0
   2   |            3 |            2
   3   |           26 |            6
   4   |          765 |          240
   5   |         3121 |         1020
   6   |       233275 |        78120
   7   |       823537 |       279930
   8   |    117440505 |     40353600
   9   |    387420481 |    134217720
  10   |  89999999991 |  31381059600
  11   | 285311670601 |  99999999990
 ...   |      ...     |      ...

Die Formel für die obige Tabelle wäre dann

Anfang: c * n^n - (n-1)
Schluss: c * (n-1)^n - (n-1)

Wobei zwischen n und c folgender Zusammenhang gilt:

Code:

  n  |  c
----------
   1 |  1
   2 |  1
   3 |  1
   4 |  3
   5 |  1
   6 |  5
   7 |  1
   8 |  7
   9 |  1
  10 |  9
  11 |  1
  12 | 11
 ... | ...

Man muss also für die geraden Zahlen immer n-1 als c nehmen und sonst 1

Und dann gilt es des Weiteren immer für die Zahlen

Anfang: (c + x * n) * n^n - (n-1)
Schluss: (c + x * n) * (n-1)^n - (n-1)

Wobei x = 0,1,2,3,4,5, .. ist

Im Fall von 5 sind es dann also die Zahlen

Code:

   x    |    Anfang    |    Schluss
------------------------------------
   0   |         3121 |         1020
   1   |        18746 |         6140
   2   |        34371 |        11260
   3   |        49996 |        16380
   4   |        65621 |        21500
   5   |        81246 |        26620
   6   |        96871 |        31740
   7   |       112496 |        36860
 ...   |      ...     |      ...

neosid'jan' · May 4, 2009

Kennt ihr das wenn sich Leute unterhalten, ihr steht daneben und wisst nicht mal welche Sprache gesprochen wird?
So ähnlich geht es mir hier gerade..

DAS KANN MAN DOCH GAR NICHT VERSTEHEN!!!

Megumi · May 4, 2009

Für die Aufgabe an sich brauch man es auch nicht zu verstehen, es gibt nen anderen Lösungsweg mit ausprobieren der relativ einfach zu implementieren ist und ich denke, dass die Lehrerin dies von RoToR wollte da sie meinte man bräuchte nicht viel Mathe dafür. (Ausserdem wer in der 11. Klasse kennt sich schon mit Ringen etc aus)
(Anzahl Goldmünzen modulo Anzahl Räuber und dann das Ergebniss überprüfen, dann kann man das quasi so runterschreiben wie die Aufgabe gestellt ist ohne viel nachzudenken)

Das Räuberproblem

Similar threads