(**)Wir beginnen mit einem (klassischen) Beispiel: Ein Bauer bekommt die Aufgabe, auf dem Markt für 1000 Taler Ferkel, Enten und Tauben zu kaufen; und zwar genau 1000 Tiere. Ein Ferkel kostet 10 Taler, eine Ente 3 Taler und eine Taube einen halben Taler. Bestimme alle Möglichkeiten - natürlich sollen die Tier lebendig und vollständig sein.
Mit Einführung der Variablen f, e und t erhalten wir das folgende mathematische Modell:
10f+3e+0,5t=1000 ï×
2
f + e + t =1000
19f + 5e =1000 (*)
Wir suchen nun alle ganzzahligen positive Lösungen dieser Gleichung (*). Gleichungen, deren Lösungen man nur in Z sucht, heißen nach dem griechischen Mathematiker Diophant (3. Jh. nach Chr.) "diophantische Gleichungen" (hier speziell lineare diophantische Gleichungen). Wir stellen hier ein erstes Verfahren vor, solche Gleichungen zu lösen. Zur Unterscheidung von späteren Verfahren sprechen wir vom D-Algorithmus (auch Eulersches Reduktionsverfahren).
Der Trick besteht darin, die Gleichung immer wieder nach dem Glied mit dem kleinsten Koeffizienten aufzulösen:
(*) Û
(**)
Damit e ganzzahlig ist, muss f Vielfaches von 5 sein. Wir setzen also f=5k und setzen dies in (**) ein: e=200-15k-4k=200-19k
Diese Gleichung macht es aber nun einfach, alle Lösungen des Problems zu überschauen:
|
k |
1 |
2 |
3 |
4 |
5 |
.... |
10 |
|
f |
5 |
10 |
15 |
20 |
25 |
.... |
50 |
|
e |
181 |
162 |
143 |
124 |
105 |
.... |
10 |
|
t |
814 |
828 |
842 |
856 |
870 |
.... |
940 |
Es gibt also 10 korrekte Lösungen des Problems!
AUFGABE 2.1
Löse das Marktproblem für 100 Taler und 100 Tiere (dieselben Preise).
AUFGABE 2.2
Löse in Z und gib jeweils drei Lösungen an:
a) 29x-13y=17 b) 187x-104y=41 c) 47x+24y=79
d) 111x+5y=433 e) 67x-33y=547 f) 401x+101y=-301
Übrigens sind nicht alle linearen diophantischen Gleichungen lösbar! Ein Lösbarkeitskriterium wird in 2.3 erarbeitet.
Einen ganz anderen Zugang zum Problem erhält man, wenn man die Gleichung (*) als Gerade interpretiert.
g: e=-
f+200 - gesucht alle Punkte PÎ
Z2 mit PÎg.
Einfacher erkennt man die linearen Funktionen, wenn man e in y und f in x umbenennt. Dann wird die Gleichung zu g: y=-x+200
Ist P0(x0ï
y0) ein Punkt von g, so liegen sicher auch alle Punkte Pk(x0-5kï
y0+19k) auf g, denn
-×
(x0-5k)+200=-x0+19k+200=(-x0+200)+19k=y0+19k (Steigungsdreieck: Man geht von einem Gitterpunkt um 5 Einheiten nach links und um 19 Einheiten nach oben.). Andererseits ist mit kÎ
Z auch PkÎ
Z2, so daß sich das Problem darauf reduziert, eine einzige konkrete Lösung von (*) anzugeben. Diese findet man aber sicherlich mit f=5 und damit e=181. Auf diese Art erhält man die Lösungsmenge also mit den Paaren (5-5kï
181+19k) für kÎ
Z. Für k=0, -1, -2,..., -9 erhält man so ebenfalls die Lösungen aus der oben angegebenen Tabelle.
AUFGABE 2.3
Versuche, die Aufgabe 2.2 mit diesem Verfahren zu lösen.
Schwieriger wird’s, wenn man es mit mehr Variablen zu tun hat. Starten wir auch hier mit einem Beispiel:
2x+3y+4z=9 soll in ganzen Zahlen gelöst werden. Wir lösen auf:
(1) x=-y-2z+4+
und setzen x1:= Û
y=-2x1+1
Dies liefert für alle x1Î
Z ganzzahlige y. Wir ersetzen wieder x1 durch k und erhalten:
y=-2k+1 in (1): x=3k-2z+3 und damit die zweiparametrige Lösungsmenge:
L={(xï
yï
z)ï
x=3k-2z+3 und y=-2k+1 und zÎ
Z} . Einige Lösungen
| k | 0 | 0 | 0 | 1 | 1 | 7 | -5 |
| z | 0 | 1 | -1 | 0 | 1 | -5 | 3 |
| x | 3 | 1 | 5 | 6 | 4 | 34 | -18 |
| y | 1 | 1 | 1 | -1 | -1 | 13 | 11 |
AUFGABE 2.4
Löse die folgenden linearen diophantischen Gleichungen allgemein und gib jeweils 5 verschiedenen Lösungen an:
a) 
b) 135x-22y+89z=100 c) 12x-5y+7z=1
AUFGABE 2.5
a) Bestimme Zahlen x und y mit: 
ebenso:
b) Ein Betrieb kauft in unterschiedlicher Stückzahl drei verschiedene Einzelteile, die 52 DM, 29 DM bzw. 3 DM kosten. Es wurden insgesamt 100 Einzelteile gekauft, die Gesamtkosten betrugen 2500 DM. Wieviel Stücke wurden von jedem Teil gekauft.
Download Kap_2 (63 KB)
