8 Lösung / Solution

[marac]

Dass man mindestens 100 Versuche braucht, ist schnell klar, reicht ja, ein Beispiel zu finden, für das 100 Versuche nötig sind (z.B. 1-100 um eins nach rechts versetzt). Aber dass es wirklich keinen worst-case gibt, bei dem man mehr als 100 Versuche braucht, kann ich nicht so recht beweisen. Nachdem ich aber auch kein Beispiel gefunden habe, bei dem ich mehr als 100 Versuche brauche, habe ich mich schließlich auch für die 10 entschieden.