Hemmes mathematische Rätsel: Wie viele dieser Barcodes gibt es?
Ein Barcode besteht aus schwarzen und weißen Streifen, die sich abwechseln, wobei der erste und der letzte Streifen schwarz sind. Alle Streifen haben entweder die Breite 1 oder die Breite 2, und der gesamte Code hat die Breite 12. Der Code wird von links nach rechts gelesen. Das Bild zeigt ein Beispiel. Wie viele verschiedene solcher Barcodes gibt es?
Wenn man die schwarzen und weißen Streifen der Breite 1 mit s und w bezeichnet und die der Breite 2 mit ss und ww, besteht jeder Barcode aus zwölf Buchstaben. Ein Barcode beginnt immer mit einem schwarzen und einem weißen Streifen, denen ein kürzerer Barcode folgt. Cm ist die Anzahl der Barcodes der Breite m. Beginnt ein Barcode der Breite m mit sw, können darauf Cm – 2 verschiedene Codes der Breite m – 2 folgen. Der Barcode der Breite m kann aber auch mit ssw oder sww beginnen, denen jeweils Cm – 3 verschiedene Codes der Breite m – 3 folgen können. Schließlich kann ein Barcode der Breite m auch noch mit ssww beginnen, denen Cm – 4 verschiedene Codes der Breite m – 4 folgen können. Für m > 4 folgt daraus Cm = Cm – 2 + 2Cm – 3 + Cm – 4, und für m ≤ 4 gibt es sechs Möglichkeiten s, ss, sws, ssws, swss und swws. Somit gilt C1 = C2 = C3 = 1 und C4 = 3. Daraus erhält man C5 = C3 + 2C2 + C1 = 4. Nun kann man sich über C6, C7 … weiterhangeln bis zu C12 = 116.
Schreiben Sie uns!
1 Beitrag anzeigen