Kleinste natürliche Zahl für die Aufgabe

Question

Seien k und n natürliche Zahlen. Eine Party mit n Gästen heißt k-lebhaft, wenn es eine Teilmenge von k Gästen gibt, die sich untereinander alle kennen, oder die sich untereinander alle nicht kennen. Jede Party mit mindestens 2 Gästen ist also 2-lebhaft, denn für jede Teilmenge von 2 Gästen gilt: entweder kennen sich die beiden, oder sie kennen sich nicht. Insbesondere gibt es eine Teilmenge von 2 Gästen, so dass sich die beiden kennen oder nicht kennen. Eine Party mit 4 Gästen muss nicht 3-lebhaft sein. Seien zum Beispiel Angie, Benji, Cindy und Danny die 4 Partygäste. Kennen sich Angie und Benji, so wie auch Cindy und Danny, aber Cindy kennt weder Angie noch Benji, und auch Danny kennt Angie und Benji nicht, so findet man keine Teilmenge von 3 Gästen, die sich alle kennen, oder die sich alle nicht kennen. Gibt es eine natürliche Zahl n, so dass jede Party mit n Gästen mit Sicherheit 3-lebhaft ist? Wenn ja, welches ist die kleinste natürliche Zahl n mit dieser Eigenschaft? Begründen Sie Ihre Aussagen.

Hinweis:

Die Relation "sich kennen" ist symmetrisch; wenn Angie Benji kennt, dann kennt Benji auch Angie. Die Relation "sich kennen" ist aber nicht transitiv.

Comments

Erläutere die Abbildung durch Text.

---

Ich verstehe die Abbildung nicht

---

Dein Kommentar kam ja auch viel zu schnell.

---

Soll das einmal die Dreier Gruppe sein?

---

Aber warum ist das Ergebnis bei dir 5

---

Das regelmäßige Fünfeck links (soviel zu deiner anderen Frage, die eigentlich lauten müsste "Wie sieht ein regelmäßiges nicht-konvexes Fünfeck aus ?") beweist das "kleinste" in der Aufgabenstellung.

---

n=5 klappt auch nicht: Betrachten wir ein regelmäßiges Fünfeck, und die Seiten repräsentieren Bekanntschaften, während die Diagonalen dann für Nicht-Kennen stehen. Man kann sich nun beliebige drei Punkte des Fünfecks sowie das verbindende Dreieck anschauen: Es sind immer mindestens eine Fünfeckseite und mindestens eine Fünfeckdiagonale unter den drei Seiten dieses Dreiecks.

n=6 klappt: Finde eine Begründung dafür!

Das war mein Gedanke

Answer 1

Die linke Abbildung ist ein Beispiel für eine 5-Personen-Party, die nicht 3-lebhaft ist. Erkennst du, warum?

Die grünen Verbindungsstriche kann man als "Paar kennt sich" und die roten als "Paar kennt sich nicht" interpretieren.

Die rechte Abbildung zeigt eine  6-Personen-Party. Ist es möglich, auch diese "nicht-k-lebhaft" zu konstruieren?

Comments

Ich weiß leider nicht warum das so ist

---

Die schwarzen Punkte stellen die Personen dar, das sieht man ja an den feucht-fröhlichen Party-Gesichtern.
Von der Person unten links müssen fünf Verbindungslinien (rot oder grün) zu den anderen gezeichnet werden, also müssen mindestens drei von gleicher Farbe sein (ich habe mal rot genommen). Die drei Endpunkte dieser Linien müssen untereinander ebenfalls verbunden werden (rot oder grün). Sowie eine Linie rot ist, entsteht ein rotes Dreieck, andernfalls ein grünes.

---

Ah okay aber wie kann man das in Worte formulieren

---

Was Gast hj2166 geschrieben hat, SIND Worte.

---

Ich weiß aber wir dürfen nicht mit Zeichnungen arbeiten

---

Dann schreib halt auf, was Du siehst:

Gegeben eine Gruppe mi 6 Personen. Wir greifen eine heraus und nennen sie P1. Wir betrachten 2 Fälle

1. P1 hat (mindestens) 3 Bekannte, sagen wir P2,P3,P4. Wenn P1 und P2 bekannt sind....

2. P1 hat (mindestens) 3 Nicht-Bekannte ......

---

Betrachten wir einen der sechs Gäste, den wir als "Gast A" bezeichnen. Gast A hat Beziehungen zu den verbleibenden fünf Gästen (B,C,D,E,F). Nun gibt es zwei Fälle:

Fall A: Gast A kennt mindestens drei der fünf anderen Gäste (B,C,D,E,F).

Angenommen, A kennt die Gäste X,Y und Z. Jetzt analysieren wir die Beziehungen zwischen X,Y und Z:

1. Szenario 1:X,Y und Z kennen sich alle gegenseitig.

In diesem Fall bildet die Gruppe {X,Y,Z} eine 3-lebhafte Gruppe, da sich alle Gäste in dieser Teilmenge untereinander kennen.

2. Szenario 2: Mindestens zwei der Gäste X,Y und Z kennen sich nicht.

Angenommen, X und Y kennen sich nicht. Dann bilden die Gäste A,X und Y eine 3-lebhafte Gruppe, da sich alle Gäste in dieser Teilmenge untereinander nicht kennen.

Gast A könnte auch Gäste auswählen, die nicht in allen Fällen bekannt sind, solange er mindestens drei kennt.

Fall B: Gast A kennt mindestens drei der fünf anderen Gäste nicht (B,C,D,E,F).

Angenommen, A kennt die Gäste X,Y und Z nicht. Jetzt analysieren wir die Beziehungen zwischen X,Y und Z:

1. Szenario 1:X,Y und Z kennen sich alle gegenseitig nicht.

In diesem Fall bildet die Gruppe {X,Y,Z} eine 3-lebhafte Gruppe, da sich alle Gäste in dieser Teilmenge untereinander nicht kennen.

2. Szenario 2: Mindestens zwei der Gäste X,Y und Z kennen sich.

Angenommen, X und Y kennen sich. Dann bilden die Gäste A,X und Y eine 3-lebhafte Gruppe, da sich alle Gäste in dieser Teilmenge untereinander kennen.

Gast A könnte auch Gäste auswählen, die nicht in allen Fällen unbekannt sind, solange er mindestens drei nicht kennt.

Da Gast A in beiden Fällen eine 3-lebhafte Gruppe bilden kann, gilt dies für jeden der sechs Gäste. Daher ist jede Party mit 6 Gästen mit Sicherheit 3-lebhaft.

Geht das so