Ist diese Mathe-Aufgabe wirklich so easy?
Ein Vater schickt seinen Sohn zum Einkaufen.
Er gibt ihm genau 100 Euro mit.
Ein Blumenstrauß kostet 10 Euro.
Ein Salat kostet 3 Euro.
Ein Brötchen kostet 0,50 Euro.
Der Sohn soll die 100 Euro genau ausgeben und dafür 100 Teile besorgen.
Wie viele Blumensträuße, Salate und Brötchen muss der Sohn kaufen?
Ist ne ganz nette Denkaufgabe :) Kann mir bitte jemand den Lösungsweg sowie die Lösung erklären?
4 Antworten
Ich würde das als lineares Gleichungssystem sehen.
x = Anzahl der Blumensträuße
y = Anzahl der Salate
z = Anzahl der Brötchen
Bedingung 1 (100 Teile): x + y + z = 100
Bedingung 2 (100 Euro): 10 * x + 3 * y + 0.5 * z = 100
Allerdings ist das Gleichungssystem unterdefiniert. (Zwei Gleichungen, drei Unbekannte.) Die Lösung wird also nicht eindeutig sein.
Sofern man nur ganzzahlige Lösungen sucht, kann man mit dem Computer den Lösungsraum vollständig absuchen, weil er nur 1 Mio. Kombinationen umfasst, z. B. in Python 2.
for x in range(0, 101):
for y in range(0, 101):
for z in range(0, 101):
if ((x + y + z) == 100) & (((10 * x) + (3 * y) + (0.5 * z)) == 100):
print (x, y, z)
(Die obere Grenze ist exklusiv, deswegen 101.)
Die Ausgabe dieses Programms lautet wie folgt.
(0, 20, 80)
(5, 1, 94)
Also entweder 0 Blumensträuße, 20 Salate, 80 Brötchen oder 5 Blumensträuße, 1 Salat, 94 Brötchen.
Was ich mich allerdings frage: Was macht der Vater mit so vielen Brötchen? ;-)
Ich nehme an, das Problem ist np-vollständig.
Wenn das Gleichungssystem nichtlinear wäre (z. B. ein Polynomsystem), dann wäre es NP-vollständig. Bei einem LGS habe ich meine Zweifel. LGS lassen sich eigentlich so gut wie immer effizient lösen.
Die eingeschränkte Menge (nur ganze Zahlen) sollte das Problem nicht "schwerer" (im Sinne der Komplexitätstheorie) machen. So kann man lineare Gleichungssysteme beispielsweise auch über endlichen Körpern effizient mit dem Gauss-Verfahren (also in O(n^3)) lösen, zumindest, solange das Gleichungssystem nicht unterdefiniert ist.
Wird die Lösung eines LGS plötzlich zu einem NP-vollständigen Problem, nur weil das LGS unterdefiniert ist? Das finde ich zumindest eine starke Behauptung, kann es allerdings auch nicht widerlegen.
Meine Vermutung kommt daher, dass das Problem diesem hier verwandt ist:
Ah, das Rucksackproblem!
Stimmt, das hast gut erkannt. ;-)
Ja, da gibt es einige kryptographische Primitive, die es nutzen.
Das Teilsummenproblem dürfte auch verwandt sein und ist auch NP-vollständig.
Als "3. Gleichung" kann man - wie du es ja gemacht hast - die Definitionsmenge eingrenzen: x,y,z müssen natürliche Zahlen aus dem Bereich 1 bis 98 sein (Annahme: es wird von jedem mindestens eins gekauft - deine erste Lösung wäre da also nicht dabei) und z muß eine gerade Zahl sein (da ein Brötchen € 0,50 kostet, muß man zB 2 kaufen, damit der Gesamtbetrag eine natürliche Zahl ergibt) → jetzt einfach durchprobieren (da die Brötchen das bei weitem billigste ist, empfiehlt es sich mit z=98 zu beginnen; dann bist du schon beim 3. Versuch bei der richtigen Lösung)
Es müsste im Grunde doch mit einer Schleife möglich sein, da das Fixieren einer Variablen ja die anderen beiden definiert.
Also eine Variable (z. B. x) variieren, dann y und z bestimmen (muss eindeutig sein) und prüfen, ob sie größer Null und ganzzahlig sind.
Allerdings wird das auch nicht effizienter sein, weil "dann y und z bestimmen" wieder auf "LGS lösen" hinausläuft.
Mich stört irgendwie, dass ich das "größer Null und ganzzahlig" schon in den Algorithmus hineinstecke, denn im Grunde ist diese Bedingung ja gewissermaßen "untergeordnet". Sie steckt ja im Grunde nicht im LGS.
Doch, es geht natürlich effizienter.
Ich kann ja einfach eine [0.0, 0.0, 1.0] an die Matrix anfügen, sie dann invertieren (das muss ich nur einmal machen) und dann den Spaltenvektor rechts in der letzten Komponente variieren. Damit variiere ich z.
Dann jeweils den Spaltenvektor (der Form [100.0, 100.0, z]) von rechts an die inverse Matrix dran multiplizieren. Multiplikation mit einem Spaltenvektor ist eine O(n^2)-Operation. Das gibt mir dann die (eindeutigen) Werte für x und y für jedes gewählte z. Das ganze für jedes z machen und prüfen, ob x und y ganzzahlig und im richtigen Intervall sind.
(Letzteres wird eventuell "schwierig", weil die inverse Matrix vermutlich nicht ganzzahlig sein wird und die Maschinengenauigkeit hier zuschlagen wird. Aber prinzipiell, also gewissermaßen "unter Missachtung von Architektur- und Implementierungedetails", sollte es funktionieren.)
Dann bin ich sozusagen bei "O(k * n^2)", mit n als Größe der Matrix (hier: 3), sowie k als Anzahl der möglichen Belegungen einer der Variablen (hier: 101).
Das ist zwar immer noch exponentiell in der Länge der Eingabe (Anzahl der Ziffern), aber zumindest linear (und nicht kubisch) im Betrag von n, mit einer möglicherweise großen additiven "Konstante" (die hängt ja nur von der Größe des LGS ab, nicht vom Wertebereich der einzelnen Variablen) zum Invertieren der Matrix.
Ok, danke für eure Antworten. Vor allem für deine (NoHumanBeing)! Leuchtet wirklich ein.
Stell ein lineares Gleichungssystem auf (mit 3 unbekannten) und such die Nullstellen der Vektorebene, die du erhalten hast.
Gibt allerdings unendlich viele. Das Gleichungssystem ist unterbestimmt, wodurch Gauss-Elimination und ähnliche Verfahren nicht funktionieren dürften.
es ist klar, dass es unendlich viele Lösungen gibt. Allerdings hat auch eien Ebene unendlich viele Nullstellen.
Dies ist ein Problem der ganzzahligen linearen Optimierung.
Solche Aufgaben werden entweder entweder mit dem Simplex Verfahren gelöst oder per Heuristik.
Dafür gibts online Solver z.B: http://www.simplexme.com/de/
Also ich konnte die folgenden Gleichungen aufstellen:
x + y + z = 100
10x + 3y + 0.5z = 100
Irfendwie fehlt da noch ne dritte Gleichung, wahrscheinlich gibt's auch einen anderen Lösungsweg. Vielleicht fällt es mir später noch ein...
Ein Mathematiker, der heutzutage nicht versteht, einen Computer zur Lösung mathematischer Probleme heranzuziehen, ist kein richtiger Mathematiker.
Das ist nicht "gecheated". Hast nicht den geringsten Grund, dich zu schämen, NoHumanBeing. Im Gegenteil. ;-)
Ok. :-)
Aber die Lösung ist schon ziemlich "brute force". ;-)
Allerdings ist der Suchraum eben auch relativ klein.
Aber die Lösung ist schon ziemlich "brute force".
...das haben NP Probleme so an sich.
Allerdings ist der Suchraum eben auch relativ klein.
Es sind ja auch nur 3 Parameter und zwei Nebenbedingungen.
Stell dir mal vor, es wären 10.000.
;-)
Handelt es sich denn hier tatsächlich um ein NP-Problem? Das Problem ist schließlich vollkommen linear.
Wenn das Gleichungssystem nicht unterdefiniert wäre, würde es sich in O(n^3) per Gauss-Elimination lösen lassen.
Macht die Tatsache, dass das LGS unterdefiniert ist, das Problem so viel schwerer? Das scheint zunächst kontraintuitiv, schließlich hat man mehr Freiheitsgrade (und mehr Lösungen).
Das gleichungssystem ist nur bedingt unterdefiniert - siehe meinen anderen Kommentar!
Das Gleichungssystem von der Form A * x = b mit ...
[x]
[ 1.0, 1.0, 1.0] * [y] = [100.0]
[10.0, 3.0, 0.5] [z] [100.0]
... ist notwendigerweise unterdefiniert, weil die Matrix A nicht invertierbar ist. A ist ja nicht einmal quadratisch.
Weniger Gleichungen als Unbekannte ist notwendigerweise unterdefiniert. Gleich viele Gleichungen wie Unbekannte kann immer noch unterdefiniert sein, wenn die Zeilenvektoren der Matrix nicht linear unabhängig voneinander sind.
Dass Du trotzdem eine eindeutige Lösung findest, liegt daran, dass Du zusätzliche (gewissermaßen "künstliche") Einschränkungen (Randbedingungen) machst.
- x, y, z müssen ganze Zahlen sein.
- x, y, z müssen positiv sein.
Dabei handelt es sich aber, wie gesagt, um Randbedingungen.
Das Gleichungssystem an sich ist selbstverständlich unterdefiniert. Ich kann zumindest eine Variable vollkommen frei wählen und die anderen beiden dann bestimmen.
Im Prinzip füge ich der Matrix dadurch eine Zeile der Form [a, 0.0, 0.0], [0.0, b, 0.0] oder [0.0, 0.0, c], sowie dem Lösungsvektor ein zusätzliches letztes Element hinzu. Dann kann ich die Matrix invertieren und das Gleichungssystem eindeutig lösen.
So löst der Vektor (-9, 3.5, 373) beispielsweise das Gleichungssystem. Ich könnte beliebig viele solcher Vektoren finden. Genauer gesagt könnte ich sogar überabzählbar unendlich viele Lösungen finden, denn ich kann ja jede beliebige Variable auf jeden beliebigen Wert aus R fixieren. Da die Matrix keine Zeile enthält, in der nur ein einzelner Koeffizient ungleich null ist, wird eine Zeile, die nur eine einzige Variable definiert, niemals von einer anderen Zeile in der Matrix linear abhängig sein. Somit wird die Matrix, nach dieser Vorschrift gebildet, niemals singulär werden und somit für jeden fixierten Wert jeder der Variablen immer notwendigerweise genau eine eindeutige Lösung gefunden werden, insgesamt also überabzählbar unendlich viele Lösungen.
Die Komplexität dieser Art von Problemen beträgt nicht O(n^3) (polynomial) sondern O(2^p(n)) (exponential).
Nur der Umstand, daß gerade in diesem konkreten Fall n=3 beträgt, läßt dich ersteres annehmen.
Es ist exponentiell in der Anzahl der Variablen, aber polynomiell in der Größe des Intervalls, in dem die Koeffizienten gesucht werden.
Es kommt sozusagen darauf an, welche Deiner Größen Du in der Landau-Notation zu Deinem "n" machst. ;-)
Vermutlich geht es auch nicht einfacher. Ich nehme an, das Problem ist np-vollständig.