linearkombination / ggt

Die Aufgabe war an sich ganz einfach:

ich habe 2 Eimer, einen mit 12 Litern Inhalt, den anderen mit 17 Litern.
Wie erreiche ich dass ich genau 8 Liter bekomme?

Die intuitive Lösung war gleich richtig:

Den Inhalt des großen Eimers in den kleinen, den kleinen leeren, den Rest vom großen in den kleinen und wieder von vorne.

Mich interessiert jetzt aber vielmehr:

Wieso funktioniert das ganze?

Also um es präziser zu fassen:

Welche Eigenschaften müssen die beiden Zahlen haben, dass ich jeden? beliebigen Inhalt zusammenkriege?
< Wenn a und b (17 und 12) nicht teilerfremd wären hätte die Methode ja ihre Probleme >

Funktioniert das hanze auch anders herum? also den kleinen in den großen, falls dieser nicht voll ist nochmal usw... ?

Im Moment hab ich die Vermutung dass
ich Z-Linearkombinationen der Form

(n+1) * a - n * b
darstellen kann, aber trotz einiger Übertlegungen weiß ich nicht ob ich Recht habe.

Ich bitte euch weiterhin eure Antworten auf einem geringen Niveau zu halten da ich mit allzu vielen mathematischen Fachbegriffen wahrscheinlich noch mehr Probleme hätte

Hi,

(i) zeichne ein Diagramm: Füllstand Eimer A vs. Füllstand Eimer B
(ii) zeichne Startbedingungen ein.
(iii) überlege dir, welche Übergänge möglich sind, wenn du an einem Punkt (x,y) bist:
1. Befüllen eines Eimers
2. Leeren eines Eimers
3. Umfüllen aus einem Eimer in den anderen

Wie sieht das im Diagramm aus?
Welche dieser Operationen sind wann sinnvoll?

(iv) Nun hast du eine anschauliche Darstellung der Menge aller möglichen Zustände und kannst deine Vermutung mit den in (iii) aufgestellten Regeln zeigen.

Heinzelotto

laut dem Lemma von Bezout kannst du den größten gemeinsamen Teiler (und damit auch jedes Vielfache) zweier Zahlen als Linearkombination der beiden Zahlen darstellen, in diesem Fall z.B. 1 = 17*5-12*7. Die Koeffizienten kannst du z.B. mit dem erweiterten Euklidischen Algorithmus bestimmen.

Links:
http://de.wikipedia.org/wiki/Lemma_von_Bézout
http://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus

ist klar dass ich das vielfache des ggt als linearkombination darstellen kann, allerdings stellt sich die frage
was in diesem doch recht praktischem versuch möglich ist

zu deinem beispiel

1 = 17*5 - 12*7

ich kann schlecht den einen eimer 17 mal füllen und anschliepend 12 mal mit dem kleinen abschöpfen... naja nachdem ich meine anderen aufgaben erledigt habe schau ich mir das evt nochmal an, aber falls mir doch jemand schnell die antworten auf meine fragen posten möchte: immer gern gesehn

@ligeti: danke für deinen hinweis, aber nur die lösung würde mir auch reichen, ist ja nicht so dass die aufgabe nicht schon gelöst wäre^^ es geht nur ums tiefere verständnis

shisha schrieb:

@ligeti: danke für deinen hinweis, aber nur die lösung würde mir auch reichen, ist ja nicht so dass die aufgabe nicht schon gelöst wäre^^ es geht nur ums tiefere verständnis

Zeichne das Diagramm. Dann wird dir sofort klar, wieso das Ganze einer Modulo-Multiplikation entspricht.

(B-A,A)  (B-(A-(B-3A)),A)=(2B-4A,A)
   A  +---o-----------o-----------o---o-------+
      |   |\          |\          |\   \      |
      |   | \         | \         | \   \     |
      |   |  \        |  \        |  \   \    |
      |   |   \       |   \       |   \   \   |
      |   |    \      |    \      | <---------+------- Eimer A leeren
      |   |     \     |     \     |     \   \ |                
      |   |      \    |      \    |      \   \|
      o---+-----------+-----------+-----------o  (B,B-3A)
      |\  |        \  |   ^    \  |        \  |
      | \ |         \ |    \    \ |         \ |
      |  \|          \|    |     \|          \|
      +---o-----------o-----\-----o-----------o
        (B-3A,0)            |    (B-A,0)         (B,0)
                             \                 B
                             |
                              \
                              |
                               \
                               |
                                \
                                  Eimer B befüllen