 |
 |
 |
 |
 |
 |
Startseite » Forum » Begrüßungen unter Paaren
Begrüßungen unter Paaren
Universität / Fachhochschule
Graphentheorie
Tags: Graphentheorie, Kombinatorik
 
|
  |
|---|
|
Guten Tag liebes Forum Ich habe gerade leichte Probleme mit einer Aufgabe zur Graphentheorie. Sie lautet wie folgt: Daisy und ihr Partner Donald organisieren eine Party mit 4 anderen Paaren. Es werden Begrüßungen ausgetauscht, aber niemand begrüßt seinen eigenen Partner. Am Ende der Party fragt Daisy alle Leute, wie viele Leute sie begrüßt haben, und sie erhält 9 unterschiedliche Antworten. Wie viele Leute hat Daisy begrüßt? Und wie viele Leute hat Donald begrüßt? Als Hinweis ist dann noch angegeben: Betrachte den zugrunde liegenden Graphen und argumentiere kombinatorisch. Mein Ansatz bisher wäre, dass wenn wir 4 Paare plus Daisy und Donald haben hätten wir offensichtlich Personen. Jede Person begrüßt weder seinen Partner noch sich selbst (Da wir verweise auf einen Knoten selbst bisher immer außen vor gelassen haben und es auch im Sachzusammenhang sinnlos wäre). Ergo kann eine Person maximal 8 Personen begrüßen und minimal wenn sie einfach niemanden begrüßt. Wir hätten also 9 Fälle und da Daisy am Ende jeden fragt wer wie viele begrüßt hat und sie von den anderen 9 Personen 9 Antworten bekommt können wir mit Sicherheit sagen, dass jeder Fall zwischen 0 und 8 genau einmal vorkommt. Wir können auch mit Sicherheit sagen, dass Daisy irgendwo zwischen 0 und 8 Begrüßungen liegt (Der Grad ihres Knoten würde dem Grad eines anderen Knotens entsprechen) aber nach meinem Verständnis können wir doch nicht sagen, wie viele Leute sie begrüßt hat und auch nicht wie viele Donald begrüßt hat, oder ? Wenn nicht so explizit nach einer Anzahl an Leuten für Daisy und Donald gefragt werden würde, würde ich meinen Ansatz als Lösung nehmen, so dachte ich vielleicht kann mir hier noch wer helfen, falls ich mich irgendwo vertue :-) MFG Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
| Hierzu passend bei OnlineMathe: Online-Übungen (Übungsaufgaben) bei unterricht.de: Gemischte Aufgaben der Kombinatorik Kombinatorik: Ziehen mit Reihenfolge und mit Zurücklegen Kombinatorik: Ziehen mit Reihenfolge und ohne Zurücklegen Kombinatorik: Ziehen ohne Reihenfolge und ohne Zurücklegen |
|
 |
|
Am besten man beweist folgende Behauptung per Vollständiger Induktion über : Daisy und ihr Partner Donald organisieren eine Party mit anderen Paaren. Es werden Begrüßungen ausgetauscht, aber niemand begrüßt seinen eigenen Partner. Am Ende der Party fragt Daisy alle Leute, wie viele Leute sie begrüßt haben, und sie erhält unterschiedliche Antworten. Dann haben sowohl Daisy als auch Donald am Ende der Party genau Leute begrüßt, und zwar aus jedem Paar jeweils einen. Induktionsanfang ist trivial. Im Induktionsschritt überlegt man zunächst wie du, dass jede Begrüßungszahl jeweils genau einmal vorkommen muss, also auch die Maximalanzahl . Die zugehörige Person bzw. auch ihren Partner schaut man sich dann mal etwas näher an... |
 |
|
Danke erstmal für die schnelle Antwort :-) Wenn ich mich nicht vertue schließt dein Induktionsanfang jedoch deine Lösung aus: Es darf ja niemand seinen eigenen Partner begrüßen, wenn jetzt aber Paare kommen haben wir nur Daisy und Donald aber bei Begrüßungen die ausgetauscht werden müsste in diesem Fall jemand seinen Partner begrüßen |
|
|
|
Du irrst: Induktionsanfang bedeutet, dass Daisy genau Leute befragt. Diese eine befragte Person ist Donald, und der gibt offenkundig die Antwort 0. (Bei nur einer Antwort ist natürlich die Information, dass alle Antwortanzahlen voneinander verschieden sind, automatisch erfüllt.) Es ist nirgendwo davon die Rede, dass Begrüßungen ausgetauscht werden müssen - da bringst du was durcheinander. Ich präzisiere mal noch den einen Halbsatz oben: "und zwar aus jedem Paar jeweils einen" soll natürlich bedeuten "und zwar aus jedem Besucherpaar jeweils einen", d.h. das Paar Daisy/Donald ist da natürlich nicht mit dabei - sollte eigentlich selbstverständlich sein, da sich die Partner voraussetzungsgemäß ja nicht gegenseitig begrüßen. |
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
1448309
1448186