Hallo,

anschaulich kannst du es dir überlegen, indem du versuchst das Gegenteil zu beweisen und scheiterst. Ist dir klar warum \(100\) Zahlen nicht ausreichen, um eine solche Teilfolge zu finden? 

Du kannst es dir auch erst Mal einfacher machen und dir das ganze am Beispiel 5 paarweise verschiedene ganze Zahlen und Teilfolge der Länge 3 überlegen. Du kannst 4 Zahlen nehmen, und es funktioniert nicht:

$$1,5,-5,3.$$

Aber die \(5.\) Zahl macht alles kaputt! :P

Dabei ist es am Anfang ja egal, ob man steigt oder fällt. Ohne Beschränkung der Allgemeinheit steigst du. Damit du dann nicht schon \(3\) hast, willst du unter \(5\) bleiben. Wenn du \(3\) jetzt nimmst, dann hast du im nächsten Schritt schon verloren. Aber du kannst \(-5\) nehmen, also nach ganz unten. Jetzt kannst du noch eine Zahl zwischen \(1\) und \(5\) wählen, zum Beispiel die \(3\) und du hast immer noch keine Teilfolge mit \(3\) steigenden oder fallenden Folgengliedern. Wenn du jetzt aber größer oder kleiner \(3\) bist, hast du eine steigende bzw. fallende Teilfolge: \(1, 3, 4\) oder \(5, 3, 2\) zum Beispiel. Meine Vermutung ist, dass es für \(n^2+1\) Zahlen eine Folge der Länge \(n+1\) gibt, die diese Eigenschaft hat. 

Ich hoffe du hast jetzt ein bisschen Anschauung für dein Problem. Das finde ich immer den ersten wichtigen Schritt. Vielleicht kommst du mit meinem kleinen Beispiel ja auf eine Regelmäßigkeit die etwas mit dem Schubfachprinzip zu tun hat! :)