Diophantische Gleichung

Hallo Zusammen. Ich habe hier eine auf den ersten Blick einfache Knobelaufgabe, bei der ich einfach nicht weiterkomme...

Man soll für 999 Euro 1000 Tiere kaufen. Dabei soll man mindestens einen Hund, eine Katze, ein Huhn und ein Küken kaufen. Weitere Bedingung ist, dass man mehr Hunde als Katzen und mehr Katzen als Hühner kaufen soll. Ein Hund kostet 25Euro, eine Katze 6 Euro, ein Huhn 4 Euro und ein Küken 25 Cent. Soweit die Aufgabenstellung. (Achso: Es sollen natürlich nur ganze Tiere gekauft werden... )

Mein erster Ansatz war:
a + b + c + d = 1000 //Zahl der Tiere soll 1000 ergeben
25a + 6b + 4c + (1/4)d = 999 //Kosten der Tiere soll 999 Euro betragen

Wie man schon sieht, hat man vier Unbekannte bei zwei Gleichungen. Man könnte dann denken, dass die Aufgabe also unendlich viele Lösungen oder überhaupt keine hat, aber es gibt tatsächlich nur eine Lösung (mit dem Computer geprüft) , was mit den beiden Bedingungen a>b und b>c zusammenhängt...

Nach ein paar Umformungen hat man dann nur noch eine Gleichung:
99a + 23b + 15c = 2996

Wenn man diese diophantische Gleichung löst erhält man:
a = 6 - 7p - 8q
b = -6 + 6p + 9q
c = 236 + 37p + 39q
wobei p und q Parameter sind, die aus den Ganzen Zahlen gewählt werden können.

Wie kann ich jetzt diese beiden Parameter bestimmen sodass gilt a>b und b>c ???

Ich habe zwar schon rausgefunden, dass p<0 und q>0 sein muss, aber jetzt komm ich nicht mehr weiter...

Hat Niemand eine Idee???

PeterTheMaster

ich versteh das problem nicht. setz doch in die ungleichung ein und seh, was es fuer bedingungen gibt.

PeterTheMaster schrieb:

ich versteh das problem nicht. setz doch in die ungleichung ein und seh, was es fuer bedingungen gibt.

Das Problem ist, dass man zwei Unbekannte in den Ungleichungen hat....

PeterTheMaster

warum ist das ein problem? man hat doch auch mehrere ungleichungen.

Naja, kann man denn lineare Ungleichungssysteme denn so ohne weiteres lösen??? Ich bin nicht so der Mathematiker...

knivil

Nennt sich lineare Optimierung. Aber das Problem ist NP-hart (zumindestens im Bereich der ganzen Zahlen). Dein Beispiel ist aber relativ gutartig.

Genau das wars, das hat super funktioniert. Danke knivil...