+ Antworten
Seite 1 von 2 12 LetzteLetzte
Ergebnis 1 bis 20 von 26

Das Räuberproblem

Eine Diskussion über Das Räuberproblem im Forum Hausaufgaben. Teil des Reallife-Bereichs; Hallo Leuts, Ich brauch mal Hilfe bei einer Aufgabe, die wir im Informatikuntericht aufbekommen haben. Aufgabe lautet folgendermaßen: Es geht ...

  1. #1
    Mainforum-Moderator
    Avatar von RoToR
    Registriert seit
    21.02.2008
    Ort
    Wartenburg
    Alter
    24
    Beiträge
    5.775
    Name
    Julian
    Nick
    RoToRone
    Clans
    tbR*

    Das Räuberproblem

    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

  2. #2
    Braunbär
    Avatar von James
    Registriert seit
    09.03.2007
    Ort
    Rhoihesse
    Beiträge
    18.635
    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?

  3. #3
    Zitat Zitat von James_Bond Beitrag anzeigen
    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:
    Spoiler:
    Paar Zahlen für die es geht (dazwischen fehlen einige für die es auch geht)
    ..., 12496, ..., 31246, ..., 9999999996

  4. #4
    Mainforum-Moderator
    Avatar von RoToR
    Registriert seit
    21.02.2008
    Ort
    Wartenburg
    Alter
    24
    Beiträge
    5.775
    Name
    Julian
    Nick
    RoToRone
    Clans
    tbR*
    Vielen Dank, das ist extrem Hilfreich und wirklich ausführlich beschrieben. Dickes Lob

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

  5. #5
    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

  6. #6
    Mainforum-Moderator
    Avatar von RoToR
    Registriert seit
    21.02.2008
    Ort
    Wartenburg
    Alter
    24
    Beiträge
    5.775
    Name
    Julian
    Nick
    RoToRone
    Clans
    tbR*
    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 :/

  7. #7
    Braunbär
    Avatar von James
    Registriert seit
    09.03.2007
    Ort
    Rhoihesse
    Beiträge
    18.635
    Anzahl irreduzibler Polynome über endlichen Ringen
    oO

    Was ist das?

  8. #8
    freezy's Rechte Hand
    Avatar von Todesgeist
    Registriert seit
    07.02.2009
    Alter
    23
    Beiträge
    4.676
    Name
    Florian
    Nick
    Todesgeist
    Clans
    SoDsW
    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^^
    Geändert von Todesgeist (29.04.2009 um 21:52 Uhr)

  9. #9
    Mainforum-Moderator
    Avatar von RoToR
    Registriert seit
    21.02.2008
    Ort
    Wartenburg
    Alter
    24
    Beiträge
    5.775
    Name
    Julian
    Nick
    RoToRone
    Clans
    tbR*
    Zitat Zitat von Todesgeist Beitrag anzeigen
    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

  10. #10
    freezy's Rechte Hand
    Avatar von Todesgeist
    Registriert seit
    07.02.2009
    Alter
    23
    Beiträge
    4.676
    Name
    Florian
    Nick
    Todesgeist
    Clans
    SoDsW
    hmmm ne is nich meine ha also lass mal^^
    und noch ne dummmmmmmmmmmmmmmme frage von miiiiiiiir was isn javascript?^^
    *mich dumm fühl*
    Geändert von Todesgeist (29.04.2009 um 21:44 Uhr)

  11. #11
    Zitat Zitat von Todesgeist Beitrag anzeigen
    Osbes is mathelehrer^^
    Nein, ich studiere aber Mathematik - und ganz bestimmt NICHT auf Lehramt ^^

    Zitat Zitat von James_Bond Beitrag anzeigen
    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.

  12. #12
    freezy's Rechte Hand
    Avatar von Todesgeist
    Registriert seit
    07.02.2009
    Alter
    23
    Beiträge
    4.676
    Name
    Florian
    Nick
    Todesgeist
    Clans
    SoDsW
    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^^

  13. #13
    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

  14. #14
    freezy's Rechte Hand
    Avatar von Todesgeist
    Registriert seit
    07.02.2009
    Alter
    23
    Beiträge
    4.676
    Name
    Florian
    Nick
    Todesgeist
    Clans
    SoDsW
    Zitat Zitat von Osbes Beitrag anzeigen
    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?^^

  15. #15
    Gefreiter
    Avatar von Megumi
    Registriert seit
    11.06.2006
    Ort
    nähe Mainz
    Alter
    27
    Beiträge
    126
    Zitat Zitat von Osbes Beitrag anzeigen
    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.
    Geändert von Megumi (04.05.2009 um 01:43 Uhr)

  16. #16
    Zitat Zitat von Ingoneur Beitrag anzeigen
    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

  17. #17
    Gefreiter
    Avatar von Megumi
    Registriert seit
    11.06.2006
    Ort
    nähe Mainz
    Alter
    27
    Beiträge
    126
    2044 / 5 = 408,8.. am Ende soll es ja aufgehen, du hast einfach die weitere Bedingung übersehen.

  18. #18
    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
     ...   |      ...     |      ...

  19. #19
    it's me
    Avatar von neosid'jan'
    Registriert seit
    14.02.2008
    Ort
    Kaarst
    Alter
    32
    Beiträge
    2.918
    Name
    Jan
    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!!!
    Erfolg ist freiwillig

  20. #20
    Gefreiter
    Avatar von Megumi
    Registriert seit
    11.06.2006
    Ort
    nähe Mainz
    Alter
    27
    Beiträge
    126
    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)

+ Antworten
Seite 1 von 2 12 LetzteLetzte

Ähnliche Themen

  1. yo wie geht das mit dne sternchen hier
    Von patrick im Forum United Talk
    Antworten: 19
    Letzter Beitrag: 26.08.2001, 02:20
  2. Das schlimmste an RA2
    Von Dragon im Forum United Talk
    Antworten: 8
    Letzter Beitrag: 19.08.2001, 15:44
  3. Kann es sein das in RA2 am meisten...
    Von Dragon im Forum United Talk
    Antworten: 7
    Letzter Beitrag: 12.08.2001, 01:00
  4. Was soll das ? Ich finds mächtig übertrieben !!!
    Von Dragon im Forum United Talk
    Antworten: 2
    Letzter Beitrag: 08.08.2001, 19:17
  5. Geht das...?
    Von aklvirus im Forum United Talk
    Antworten: 7
    Letzter Beitrag: 07.08.2001, 01:10

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •