Aufgabe:
Fourier-Motzkin-Elimination über Anzahl der entstehenden Ungleichungen
Zeigen Sie, dass nach Anwendung der Fourier-Motzkin-Methode auf ein Ungleichungssystem mit n Variablen und m Ungleichungen bis zu
\( \frac{1}{2^{2^{n}-2}} (\frac{m}{2})^{2^{n}} \)
Ungleichungen entstanden sein können. Dabei werden eventuell auftretende redundante Ungleichungen nicht entfernt.
(Hinweis: Überlegen Sie zuerst, wie viele Ungleichungen maximal während einer Elimination entstehen können).
Problem/Ansatz:
Meine Idee ist dabei eine Induktion über die Anzahl der Variablen n zu machen.
Der erste Schritt - Induktionsanfang mit n=1 - ist klar.
Dann nehme ich an, dass es ein System mit n+1 Variablen gibt, bei dem ich eine Variable streiche, um auf n Variablen zu kommen und die Induktionsvoraussetzung zu benutzen.
Nun muss die gelöschte Variable wieder eingefügt und gezeigt werden, dass die gegebene Formel jetzt für n+1 gilt.
An diesem Punkt weiss ich aber nicht mehr weiter, kann mir jemand
einen Tipp geben, wie weiter vorzugehen ist?
mfg
