Inklusion & Exklusion < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:43 Do 18.12.2008 | | Autor: | Squanto |
| Aufgabe | | Auf wie viele Arten kann man die 4 Wände eines rechteckigen Zimmers mit 5 verschiedenen zur Verfügung stehenden Farben streichen, wenn an jeder Zimmerecke verschiedene Farben aneinander stoßen sollen? |
Als Hinweis wurde uns gesagt, wir sollen es mithilfe von Inklusion und Exklusion lösen können. Allerdings verstehe ich nicht ganz das Prinzip, welches dahinter steht.
Ich würde nun zuerst alle Möglichkeiten berechnen die Wände zu streichen, egal ob Farben aneinander treffen. Dies wären dann [mm] 5^{4} [/mm] = 625.
Davon würde ich nun zunächst die Möglichkeit abziehen alle 4 Wände gleich zu streichen, also 625-5 = 620.
Nun kämen die Möglichkeiten 3 Wände gleich zu streichen 4*4*1*1 = 16 ==> 620-16 = 604. Nun sind doch da noch immer die Fälle enthalten, in denen zwei aneinanderstoßende Wände die gleich Farbe haben. Glaube dafür gibt es 5*1*4*1 = 20 Möglichkeiten ==> 604-20 = 584. Damit wäre 584 meine Lösung.
Habe ich etwas übersehen? Irgendwie kommt mir das recht komisch vor. Danke für eure Hilfe!
Und da dies mein Erster Beitrag ist:
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> Nun kämen die Möglichkeiten 3 Wände gleich zu streichen
> 4*4*1*1 = 16 ==> 620-16 = 604.
Allein dafür gibt es schon mehr Möglichkeiten: 5 Farben für 3 Wände, 4 Farben für die verbleibende Wand und 4 Möglichkeiten, welche Wand in abweichender Farbe gestrichen wird. Sind 5*4*4=80 Möglichkeiten zum Abziehen.
Bei 2 Wänden wirds noch komplizierter...
Ich würde nicht die falschen Lösungen aussortieren, sondern die richtigen addieren:
Du hast 5 Farben für die Nord-Wand, 4 Farben für die Ost-Wand, 4 Farben für die Süd-wand und je nachdem 3 oder 4 Farben für die West-Wand zur Auswahl.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:32 Do 18.12.2008 | | Autor: | Squanto |
Hm, sähe dies dann nicht wie folgt aus:
Man kann alle 5 Farben für die Nord-Wand nehmen: 5
Für die Ost-Wand kann man alle minus der einen von der Nord Wand benutzen: 4
An der Süd-Wand kann man wiederum alle benutzen, außer der Farbe von der Ost-Wand: 4
Nun kommt noch die West-Wand. Dort kann man alle nutzen, außer der von der Nord- und Süd-Wand. Wären ja nun 3. Was ist allerdings wenn die Nord- und Süd-Wand dieselbe Farbe haben, dann wären es 4 (glaube das meintest du in deinem Post auch).
Müsste ich jetzt nicht erstmal davon ausgehen, dass die Nord- und Süd-Wand unterschiedlich Farben haben? Dies wäre dann 5*4*4*3 = 240. Allerdings fehlen da die Fälle, wenn Nord- und Süd-Wand die gleiche Farbe haben. Wenn die dies haben, hätte man 5*4*4*4 = 320. Dies beinhaltet aber auch die Fälle aus meiner 1. Gleichung, also müssen die da wieder raus ==> 320 - 240 = 80.
Insgesamt also: 240 + (320 - 240) = 320 Hmmm, sieht ebenfalls komisch aus ^^
|
|
|
| |
|
Hallo Squanto,
Zu allererst: Gibt es nicht insgesammt [mm] 4^{5} [/mm] Möglichkeiten, wenn keine Restriktiionen gegeben wären, weil jede der 4 Wände mit einer beliebigen von 5 Farben gestrichen werden?
Und nun zum Aussortieren.
Ich finde es gibt da 2 herangensweisen.
Geh mal davon aus, wir betrachten zuerst 2 gegenüberliegende Seiten.
Die beinflussen sich ja gegenseitig nicht, d.h. auf jede Wand können eine von 5 Farben ---> 5*5 Möglichkeiten!
Nun unterscheiden wir 2 Fälle.
In 5 der obigen Szenarien sind die beiden gegenüberliegenden Wände mit der selben Farbe gestrichen. [mm] \bruch{5}{25} [/mm] Fällen entspricht 20% der Fälle. In diesen 20% gibt es für die 2 restlichen Seiten jeweils 4 Möglichkeiten ---> 0,2*5*5*4*4
Im anderen Szenario haben die beiden Seiten unterschiedliche Farben abbekommen. In diesen 80% der Fälle gibt es daher für die restlichen Seiten 3 Möglichkeiten, da weder die eine noch die andere der beiden zuerst gestrichenen Seiten drauf darf. ---> 0,8*5*5*3*3
0,2*5*5*4*4+0,8*5*5*3*3=80+160=240 Möglichkeiten.
Ich bin mir nicht 100prozentig sicher, ob das stimmt, aber so hätte ich diese Aufgabe gelöst!
lg Kai
|
|
|
| |
|
Es gibt zahlreiche Wege. Ich skizziere mal ein paar, und Du suchst danach aus, ob Inklusion oder Exklusion oder beide enthalten sind. Erstmal Dein Vorschlag:
1)
Du färbst die Wände in der Reihenfolge Nord, Ost, Süd, West. Schwieriger Ansatz, aber natürlich möglich.
> Man kann alle 5 Farben für die Nord-Wand nehmen: 5
> Für die Ost-Wand kann man alle minus der einen von der
> Nord Wand benutzen: 4
> An der Süd-Wand kann man wiederum alle benutzen, außer der
> Farbe von der Ost-Wand: 4 darunter auch die Farbe Nord
> Nun kommt noch die West-Wand. Dort kann man alle nutzen,
> außer der von der Nord- und Süd-Wand. Wären ja nun 3. Was
> ist allerdings wenn die Nord- und Süd-Wand dieselbe Farbe
> haben, dann wären es 4 (glaube das meintest du in deinem
> Post auch).
Richtig beobachtet, aber dann nicht konsequent angewandt.
> Müsste ich jetzt nicht erstmal davon ausgehen, dass die
> Nord- und Süd-Wand unterschiedlich Farben haben? Dies wäre
> dann 5*4*4*3 = 240. Allerdings fehlen da die Fälle, wenn
> Nord- und Süd-Wand die gleiche Farbe haben.
Nicht ganz. Du hast alle Fälle mit Nord=Süd, aber West dann auf drei Farben beschränkt. Der für Nord=Süd mögliche Fall Ost=West muss noch hinzugezählt werden. Du gehst aber anders vor:
> Wenn die dies
> haben, hätte man 5*4*4*4 = 320.
Falsch: 5 Möglichkeiten Nord, 1 (!) Süd (muss gleich sein wie Nord), also:
5*1*4*4=80
> Dies beinhaltet aber auch
> die Fälle aus meiner 1. Gleichung,
ja, aber welche? Offenbar alle, in denen Ost und West unterschiedliche Farben haben, insgesamt [mm] 5_N*1_S*4_O*3_W=60
[/mm]
> also müssen die da
> wieder raus ==> 320 - 240 = 80.
Nö. 240+80-60=260
> Insgesamt also: 240 + (320 - 240) = 320 Hmmm, sieht
> ebenfalls komisch aus ^^
Fand ich auch.
2) Nord+Süd, Ost+West
a) Nord und Süd haben unterschiedliche Farben (5*4), Ost und West beeinflussen sich nicht gegenseitig, für jede 3 Möglichkeiten: 5*4*3*3=180
b) Nord und Süd haben die gleiche Farbe (5*1), Ost und West beeinflussen sich nicht gegenseitig, für jede 4 Möglichkeiten: 5*1*4*4=80
Insgesamt: 180+80=260
3) Farbgebung ohne Orientierung, dann Anwendung aufs Zimmer
a) vier unterschiedliche Farben: 5*4*3*2. Kann in vier Orientierungen aufs Zimmer appliziert werden, allerdings tritt dann jede Farbgebung genau viermal auf. Insgesamt also [mm] \bruch{5*4*3*2*4}{4}=120
[/mm]
b) drei unterschiedliche Farben, also zwei gegenüberliegende Wände gleich: 5*4*3*1. Kann in vier Orientierungen aufs Zimmer appliziert werden, wobei jede Farbgebung doppelt auftritt. Insgesamt also [mm] \bruch{5*4*3*1*4}{2}=120
[/mm]
c) zwei unterschiedliche Farben, also je zwei gegenüberliegende Wände gleich: 5*4*1*1. Kann in zwei Orientierungen aufs Zimmer appliziert werden, wobei jede Farbgebung doppelt auftritt. Insgesamt also [mm] \bruch{5*4*1*1*2}{2}=20
[/mm]
Zusammen: 120+120+20=260
Variante zu 3), a) wie vorher
bb) zwei gegenüberliegende Wände gleich: 5*1*4*4. Kann in vier Orientierungen aufs Zimmer appliziert werden, wobei jede Farbgebung doppelt auftritt, diejenigen mit nur zwei Farben sogar vierfach (siehe cc).
Unter Berücksichtigung nur der doppelten Farbgebung: [mm] \bruch{5*1*4*4*4}{2}=160
[/mm]
c) wie vorher
Zusammen: 120+160-20=260
Es gibt natürlich noch zahlreiche weitere Färbetechniken. Du könntest zum Beispiel mit Farbe 1 anfangen und mit ihr zwei, eine, oder keine Wand streichen und dann die anderen möglichen Farbverwendungen durchgehen: wo wäre jetzt Platz für Farbe 2 (wieder zwei, eine oder keine Wand). Bei Farbe 3 brauchst Du schon eine Fallunterscheidung etc.
lg,
reverend
|
|
|
|
