Nelius/Nöcker

9. Übungsblatt

MATHEMATIK FÜR INFORMATIKER I (WS 2000/01)

Abgabe: Montag, 8.1.2001 bis 13.00 Uhr !!!

Internet–Adresse der Vorlesung:

http://math–www.uni–paderborn.de/~chris/index9.html

33. Aufgabe: Weihnachten naht, und damit gibt es für den Weihnachtsmann und seine Gehilfen besonders viel zu tun. Leider geht das nicht ganz ohne Köpfchen ab. Insbesondere das Auswählen, Verpacken und Ausliefern der Geschenke bereitet großes Kopfzerbrechen.

a) Ein lieber Studi hat eine Liste mit 30 Geschenkvorschlägen an den Weihnachtsmann gemailt. Dieser beschließt, dem Studi 4 Geschenke aus dieser Liste an Weihnachten unter den Baum zu legen. Wieviele Möglichkeiten hat der Weihnachtsmann, seine Auswahl zu treffen?

b) Der Schlitten des Weihnachtsmanns wird nach einer amerikanischen Überlieferung von 8 Rentieren gezogen. Alle 8 Rentiere haben natürlich Namen und sind unterscheidbar. Der Schlitten hat ein Geschirr mit genau 8 Plätzen. Auf wieviele Arten kann der Oberstallmeister des Weihnachtsmannes den Schlitten bespannen, wenn das rotnasige Rentier Rudolph immer an den Geschirrplatz mit der Nummer 1 kommt (vorne rechts)?

c) Der Schlitten ist gepackt, die Rentiere sind angespannt, der Weihnachtsabend ist da. Zuerst besucht der Weihnachtsmann 30 Studis. Dabei gibt es jeweils zwei Möglichkeiten. Ein fauler Studi bekommt kein Geschenk, ein fleißiger Studi aber ein Geschenk. Wieviele verschiedene Geschenkverteilszenarien sind möglich, wenn die 30 Studis in einer festen Reihenfolge beschert werden?

d) Und schon ist der Weihnachtsmann in Manhattan unterwegs. Der Stadtplan von Manhattan ist ungefähr wie folgt, wobei jede Linie eine Straße ist:

[figure: Weihnachtsmann; Schlitten]

Der Weihnachtsmann hat seinen Schlitten abgestellt. Jetzt muss er zu Fuß zurück durch die Straßen von Manhattan. Auf wievielen (kürzesten) Wegen kann der Weihnachtsmann von seinem aktuellen Standpunkt zu seinem Schlitten kommen? e) Am Weihnachtsmorgen haben wir die Bescherung. Kevin findet einen Teller randvoll (also

jeweils mindestens 10 Stück) mit Mandarinen, Nüssen und Plätzchen. Da Weihnachten ist, darf seine Schwester sich insgesamt 10 Teile vom Teller nehmen. Auf wieviele Arten geht das? Dabei sei angenommen, daß Leckereien einer Sorte (z.B. Plätzchen) nicht unterscheidbar sind.

(9)

34. Aufgabe: Auf der Menge A = {a, b, c, …, y, z} der Buchstaben des Alphabets ist durch die übliche Reihenfolge der Buchstaben eine linerae Ordnung ⪯ definiert (z.B. gilt a ⪯ a , c ⪯ r aber y ⪯̸ n). Wir nennen ein Wort w = w_{1}w_{2} … w_{k} aus den Buchstaben w_{1}, …, w_{k} ∈ A monoton steigend, wenn gilt: ∀ i, j ∈ {1, 2, … k} : i < j ⟹ w_{i} ⪯ w_{j} (z.B. ist das Wort “aber“ monoton steigend, nicht aber das Wort “nein“). Es bezeichne a_{k} die Anzahl der monoton steigenden Wörter der Länge k (also aus A^{k}) für k ∈ IN.

a) Bestimme a_{k} für k = 1, 2, 3 jeweils durch eine explizite Überlegung.

b) Bestimme allgemein a_{k} für ein beliebiges k ∈ IN. Lassen sich die Ergebnisse aus a) wiederfinden? (7)

⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆

Aufgaben vom Weihnachtsmann Damit die kommende trostlose Zeit ohne Mathematik– Veranstaltungen etwas leichter ertragen werden kann, hat uns der Weihnachtsmann noch einige Anregungen beschert (nur so zum Spaß !):

(⋆) Wer gerne noch etwas mit dem Turm von Hanoi spielen möchte, kann folgende Erschwernisse einbauen, wobei die alten Spielregeln gültig bleiben:

a) Jeder Zug muß über die Säule B verlaufen (d.h. dort enden oder dort beginnen)

b) Beim “Doppel–Turm von Hanoi“ gibt es von jeder Größe 2 Scheiben, also insgesamt 2n, und zwar in 2 Varianten:

1) Scheiben gleicher Größe werden nicht unterschieden

2) Scheiben gleicher Größe werden unterschieden

In allen 3 Varianten ist jeweils nach der (minimalen) Anzahl der Spielzüge gefragt.

(⋆⋆) Läßt sich in Aufg. 29a) eine allgemeine Formel für ∑_{k=0}^{n} k\binom{n}{k} finden und vielleicht sogar

beweisen?

⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆

Allen ein frohes Weihnachtsfest und ein erfolgreiches Neues Jahr!

Dies wünschen:

M.Ackermann, P.Birkner, P.Horn, P.Mihailescu, M.L. Modjo Kamneng, Chr. Nelius, M.Nöcker, V.Winzenick, A.Wolf

⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆