Emil beschreibt Folgen von blauen und roten Bällen nur mit 0en und 1en.
Das macht er auf ganz besondere Weise und zeigt das an einem Beispiel:

example

Im ersten Schritt zählt Emil für jeden Ball, wie viele blaue Bälle sich rechts davon befinden,
und zählt den Ball selbst mit, wenn der blau ist.
Diese Anzahlen schreibt er als Zwischenfolge auf:

3, 3, 2, 1, 1, 1

Im zweiten und letzten Schritt formt er die Zwischenfolge so um:
Wenn die Zahl gerade ist, wird sie zu 0, wenn sie ungerade ist, zu 1.
0 gilt als gerade Zahl. Emil beschreibt die obige Bälle-Folge also so:

1, 1, 0, 1, 1, 1

Eine andere Bälle-Folge beschreibt Emil so:

0, 1, 1, 1, 0, 1, 0, 0

Erstelle diese Bälle-Folge!

Erklärung

So ist es richtig:

answer

Es gibt mehrere Wege, die richtige Bälle-Folge zu bestimmen. Ein Weg besteht darin, die Beschreibung von rechts nach links durchzugehen und dabei jeweils zu überlegen, ob der Ball an der entsprechenden Position der Bälle-Folge rot oder blau sein muss.

  1. Wir beginnen ganz rechts. Die 0 an dieser Stelle legt fest, dass der Ball rot sein muss: Nur bei einem roten Ball bleibt die Anzahl der blauen Bälle rechts ab dieser Stelle gerade (nämlich 0).
0 1 1 1 0 1 0 0
? ? ? ? ? ? ? rot
  1. An der zweiten Stelle von rechts steht wieder eine 0. Auch hier gilt: Nur bei einem roten Ball bleibt die Anzahl der blauen Bälle rechts ab dieser Stelle gerade.
0 1 1 1 0 1 0 0
? ? ? ? ? ? rot rot
  1. An der dritten Stelle von rechts steht eine 1. Der Ball an dieser Stelle muss blau sein, um von einer geraden (0) zu einer ungeraden (1) Anzahl blauer Bälle rechts ab dieser Stelle zu kommen.
0 1 1 1 0 1 0 0
? ? ? ? ? blau rot rot
  1. An der vierten Stelle von rechts steht eine 0. Der Ball an dieser Stelle muss blau sein, um von der bisherigen ungeraden (1) zu einer geraden (2) Anzahl blauer Bälle rechts ab dieser Stelle zu kommen.´
0 1 1 1 0 1 0 0
? ? ? ? blau blau rot rot
  1. An der fünften Stelle von rechts steht eine 1. Der Ball an dieser Stelle muss blau sein, um von der bisherigen geraden (2) zu einer ungeraden (3) Anzahl blauer Bälle rechts ab dieser Stelle zu kommen.
0 1 1 1 0 1 0 0
? ? ? blau blau blau rot rot
  1. An der sechsten Stelle von rechts steht eine 1. Der Ball an dieser Stelle muss rot sein, damit die Anzahl blauer Bälle rechts ab dieser Stelle ungerade (3) bleibt.
0 1 1 1 0 1 0 0
? ? rot blau blau blau rot rot
  1. An der siebten Stelle von rechts steht erneut eine 1. Der Ball an dieser Stelle muss rot sein, damit die Anzahl blauer Bälle rechts ab dieser Stelle ungerade (3) bleibt.
0 1 1 1 0 1 0 0
? rot rot blau blau blau rot rot
  1. An der achten Stelle von rechts (erste Stelle von links) steht eine 0. Der Ball an dieser Stelle muss blau sein, um von der bisherigen ungeraden (3) zu einer geraden (4) Anzahl blauer Bälle rechts ab dieser Stelle zu kommen.
0 1 1 1 0 1 0 0
blau rot rot blau blau blau rot rot

Zusammenfassend lässt sich sagen: Wenn es bei einem Schritt nach links einen Wechsel von einer 0 zu einer 1 oder von einer 1 zu einer 0 gibt, dann muss ein blauer Ball hinzukommen. Gibt es keinen Wechsel, ändert sich die Parität (also die Eigenschaft einer Zahl, gerade oder ungerade zu sein) der Anzahl blauer Bälle rechts ab der Stelle nicht, so dass dort ein roter Ball liegen muss.

0 1 1 1 0 1 0 0
4 blau 3 blau 3 blau 3 blau 2 blau 1 blau 0 blau 0 blau

Zusatzinformation

Emil beschreibt die Bälle-Folge mit den Ziffern 0 und 1, und zwar so, dass man aus der Beschreibung die Bälle-Folge wieder erstellen kann. Eine Bälle-Folge und ihre Beschreibung sind also eindeutig einander zugeordnet. Für die Informatik sind solche eindeutigen Zuordnungen zwischen Folgen aus verschiedenen Elementemengen essenziell und heißen Kodierungen. Weil die technischen Bausteine der Computerhardware mit binären Werten arbeiten (0 und 1, „wahr“ und „falsch“, … ), muss es für jede Information, die von Computern verarbeitet werden soll, eine Kodierung mit binären Werten geben.

Bei der Kodierung von Information für die Speicherung in Informatiksystemen kann man versuchen, die Darstellung in binären Werten so kompakt wie möglich zu halten, um Speicherplatz zu sparen. Dann kann aus der Kodierung eine Kompression von Daten werden. Wenn aus dem Ergebnis der Kompression die Ausgangsinformation komplett und exakt wieder rekonstruiert werden kann, wird die Kompression als verlustfrei bezeichnet. In vielen Fällen sind aber auch verlustbehaftete Kompressionen akzeptabel. Bekannte Beispiele sind die Datenformate MP3, eine (mittlerweile veraltete) Kompression von Ton-Daten, und JPEG, eine Kompression von Bilddaten. In beiden Formaten wird unwichtige Information reduziert, nämlich vom Menschen ohnehin schlecht wahrgenommene Frequenzbereiche oder Farbwerte.

Emil bestimmt für jede Bälle-Folge eine (verlustfreie) Kodierung in binären Werten. Wäre es ihm nur darum gegangen, Folgen von roten und blauen Bällen mit binären Werten zu kodieren, hätte er einfach für die roten Bälle eine 0 und für die blauen eine 1 schreiben können. Aber dann wäre diese Biberaufgabe deutlich weniger interessant gewesen, nicht wahr?