8 Lösung / Solution

[lukas]

Teilt hier gerne eure Lösung zu Aufgabe 8

---

Feel free to share your solution to challenge 8

[Noname_MM]

Ich habe Lösung 10.
Aus meiner Sicht braucht es 100 Elfen. Wenn nämlich die Zeichen 101 bis 199 rückwärts und das erste Zeichen an der hundertsten Stelle gewählt werden, braucht es einen Versuch, bei dem nur das erste Zeichen blau leuchtet. Dann wird das erste Zeichen eine Stelle weitergerückt und die anderen Zeichen 101 bis 199 eingegeben. (Alle leuchten blau)
In jeder darauffolgenden Runde wandert ein Zeichen, beginnend mit der 199 an seinen Platz und das erste Zeichen wandert bis zum 100. Platz. Somit haben die Elfen nach 100 Versuchen (gerade noch rechtzeitig) den Code erraten.
Klar fehlt hier ein Beweis, dass dies der ungünstigste Fall ist, aber beim Versuch mit kleineren Werten, kam ich auch auf „die Hälfte plus 1“

[mbert]

Wenn z. B. die ersten 99 Zeichen und das letzte Zeichen auf der Liste im Code vorkommen, sind 100 Versuche nötig, aber nicht mehr, da nach spätestens 99 Verschiebungen jedes Zeichen an seinem richtigen Platz ist.

[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.

[Kosakenzipfel]

Ich hab auch 10. Auf magische Weise reduzieren sich die möglichen Plätze für später dazukommende Symbole so, dass sie mit weniger Verschiebungen an den richtigen Platz kommen. Als wenn ein Symbol erst in Runde n dazukommt, braucht es maximal N-n Verschiebungen, und N ist 100.

[st1974]

Ich schließe mich der Lösung m=100 an. 
Dass sie mindestens nötig sind,beweist der Code (1,2,3,...,99,199). Hier wären die ersten 99 Stellen immer grün, während für die letzte Stelle alle Möglichkeiten durchprobiert werden müssen. 
Einen formalen Beweis, dass die 100 auch das Maximum sind, habe ich zwar nicht, aber es es ist plausibel, denn
- jedes grüne Zeichen fixiert eine Postiion, so dass sich die Anzahl der Positionen, die die anderen Zeichen durchprobieren müssen, um eins reduziert.
- jedes nicht markiertes Zeichen wird durch ein neues ersetzt, so dass spätestens imm 100. Versuch das letze Zeichen genommen wird.
- für jedes blaue Zeichen werden alle Postitionen, die nicht grün markiert sind durchprobiert.

[MatheJuergen]

Ich bin ähnlich vorgegangen wie st1974. Mein "worst case" war die ersten 99 Positionen stimmen zufällig schon beim ersten Versuch. Mit der gewählten Strategie benötigt man jetzt noch weitere 99 Versuche um 100% save zu sein.
Also benötigt man mindestens 100 Versuche. (Mit einer anderen Strategie, würde man bei obigen Szenario allerdings nur noch zwei weitere Versuche benötigen.   Eine Strategie sollte immer flexibel auf den jeweiligen Fall reagieren können)
Dann habe ich überlegt, ob es ein Szenario mit 101 Versuchen gibt. Von den ersten 100 eingegebenen Zeichen ist ja mindestens eins blau (oder grün). Um dieses Zeichen 100% grün zu bekommen benötigt man höchstens 99 weitere Versuche. Sobald dies geschieht sind für die anderen 99 Zeichen nur noch 99 Positionen relevant und somit findet man auch deren Positionen nach spätestens 99 Versuchen.
Man das ganze ja auch mal mit einer kleineren Anzahl "modellieren" (z.B. mit 9 Zeichen und einem 5 stelligen Code). Da erhält man den code spätestens nach 5 Versuchen. 

[LuckytoBee]

Ich habe 109 Elfen, die es mindestens braucht also Antwort 9. Mein Worstcase sind 90 richtige an der falschen Position in Runde 1. Diese sind dann in Runde Hundert alle richtig. Die restlichen 10 rotieren dann noch bis in Runde 109 alle an der richtigen Position sind. Für weniger richtige wird es nicht schlimmer, aber das kann ich schlecht beschreiben.

[MarcoS]

Ich habe 109 Elfen, die es mindestens braucht also Antwort 9. Mein Worstcase sind 90 richtige an der falschen Position in Runde 1. Diese sind dann in Runde Hundert alle richtig. Die restlichen 10 rotieren dann noch bis in Runde 109 alle an der richtigen Position sind. Für weniger richtige wird es nicht schlimmer, aber das kann ich schlecht beschreiben.

Was meinst du mit "Die restlichen 10 rotieren noch..."? Kannst du den Worstcase bitte mal an einem Beispiel beschreiben? Angenommen, die verfügbaren Zeichen sind die natürlichen Zahlen von 1 bis 199 und der korrekte Code verwendet die natürlichen Zahlen von 1 bis 100 in ihrer natürlichen Reihenfolge. Wie sieht dann der von dir beschriebene Worstcase aus?