Die N.E.R.D.-Aufgabe für den Monat Oktober 2021! Lösung!

Die in der Grafik zu sehenden Gebiete A, B, C, D und E sollen so gefärbt werden,

dass benachbarte Gebiete verschiedene Farben haben. Auf wie viele Arten kann

man dies tun, wenn man

a) 4 verschiedene Farben zur Auswahl hat?

b) 5 verschiedene Farben zur Auswahl hat?

c) n verschiedene Farben zur Auswahl hat?

Hinweis: Es ist nicht erforderlich, alle Farben zu benutzen.

Wer möchte, kann mir seine Überlegungen per Mail schicken.

Wie immer gibt es neben Ruhm und Ehre viele N.E.R.D.-Punkte zu ergattern.

Lösung

A, B und C können auf n untere Faktorielle 3 = n(n-1)(n-2)= n!/(n-3)! Arten eingefärbt werden. Dann muss man zwei Fälle unterscheiden.

i) Hat D dieselbe Farbe wie B, so hat E (n-3) verbleibende Farben + die Farbe von C zur Verfügung, also insgesamt (n-2).

ii) hat D eine andere Farbe als B, so hat D (n-3) Möglichkeiten und E (n-4+1), also ebenfalls (n-3). Daraus ergeben sich (n-3)2 Kombinationen.

Insgesamt erhalten wir also für die Zahl der Färbungen

n!/(n-3)!(n-2+(n-3)2) = (n3-3n2+2n)(n2-5n+7)= n5-8n4+24n3-31n2+14n

Setzen wir n=4, so erhalten wir 72 Möglichkeiten, für n=5 sind es 420.

0 Kommentare

Hinterlasse einen Kommentar

An der Diskussion beteiligen?
Hinterlasse uns deinen Kommentar!

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.