Aufgabe: Beweis durch Schubfachprinzip
Lemma 3: Seien \( P, T \in \Sigma^{*} \). Angenommen, \( P \) und \( T \) matchen mit \( k \geq 0 \) Fehlern. Des Weiteren sei \( p^{1} \circ p^{2} \circ \cdots \circ p^{j}=P \) eine beliebige Zerlegung von \( P \) in \( 1 \leq j \leq|P| \) Teilstrings. Seien \( a_{1}, \ldots, a_{j} \geq 0 \) mit
\( \alpha:=\sum \limits_{i=1}^{j} a_{i}>0 \)
vorgegeben. Dann existiert ein \( i \in\{1, \ldots, j\} \), so dass \( T \) einen Infix enthält, welches \( p^{i} \) mit höchstens \( \left\lfloor a_{i} \cdot k / \alpha\right\rfloor \) Fehlern matcht.
Problem/Ansatz: Meine Idee war Beweis durch Widerspruch mit es existiert kein i sodass höchstes so viele Fehler gemacht werden. Aber ich bin mir danach unschlüssig, was ich aus dieser Annahme folgen kann/muss. Kann mir jemand helfen?
