Aufgabe zur Zahl 18

Neue Frage »

chroom Auf diesen Beitrag antworten »
Aufgabe zur Zahl 18
Ich weiß nicht, ob ich hier in dem richtigem Forum gelandet bin, und hoffe einfach mal um Hilfe. Ich komme nicht weiter.

Edit (mY+): Bitte KEINE Hilferufe, vor allem nicht in der Überschrift. Entfernt.

Die Aufgabe lautet wie folgt:

______________________________________________
Zu 18)
Zeige folgendes: Wenn auf einer Feier 18 Personen eingeladen sind, dann gibt es entweder eine 4-er Gruppe die sich alle gegenseitig kennen, oder eine 4-er Gruppe, von denen sich keiner untereinander kennt.
______________________________________________


Muss man hier etwas beweisen? Und wenn ja, wie?
Ich sitze seit einigen Tagen daran und kann mir nicht erklären, wie das wäre, würden eben die verschiedenen Personen sich kennen oder nicht kennen - untereinander in der Gruppe.
Würde ich die Personen z.B. einladen, kenne ich alle Personen, und würden 4-er Gruppen aufgeteilt, dann würde ich alle Personen kennen.

Das war meine eine Überlegung.

Dann; was ist, wenn man die Menschen in ungleich große Gruppen aufteile?
5 Personen + 5 Personen + 4 Personen (die sich kennen; nicht kennen) + 4 Pesonen (die sich kennen; nicht kennen)

ODER

7 Personen + 7 Personen + 4 Personen (die sich kennen)

Ist das so gemeint?
Sonst würde das ganze ja schließlich auch schon viel eher gehen, als ab 18.

Es ist ja immer 17 + 1 (also der Gastgeber) muss eine 3er Gruppe enthalten sein, die sich untereinander kennen.
In den anderen Gruppen dürfen sich höchstens 2 Leute kennen;..

Oder werden 18 eingeladen + 1 Gastgeber der nicht zu den 18 dazu gehört?
D.h wiederum dass sich mehr Menschen in der Gruppen kennen dürfen. Und nicht kennen dürfen.

ach man, ich bin zu verwirrt.
Ich bitte um Hilfe!
Iridium Auf diesen Beitrag antworten »

Hi,

Das hört sich für mich nach nem Problem an, das man graphentheoretisch lösen könnte bzw. mit Hilfe der Ramseytheorie (geht in dieselbe Richtung)...schau vielleicht mal dort nach...

http://de.wikipedia.org/wiki/Ramseytheorie

Zitat "In einem weiteren Beispiel treffen 6 Personen aufeinander. Je zwei sind entweder miteinander befreundet oder nicht befreundet. Dann gibt es (stets!) eine Gruppe von dreien, die jeweils miteinander befreundet bzw. nicht-befreundet sind."

Das hört sich doch so ähnlich an. Bei 18 Personen ist die Zahl der Möglichkeiten natürlich größer...das kann u.U. das ganze verkomplizieren.

Andererseits...du hast das Problem doch bestimmt von irgendjemand gestellt bekommen, der weiß, wie schwierig er es machen kann...also kann es auch wiederrum nicht so schwierig sein...in welchem Zusammenhang sollt ihr denn die Aufgabe lösen?

Im übrigen scheint mir die Aufgabe, zumindest wie du sie zitierst, unvollständig zu sein. Gibt es nicht noch eine Nebenbedingungen, die eine Aussage darüber trifft, wieviele Personen sich insgesamt kennen? Denn wenn man die Annahme trifft, daß man 18 Personen einlädt, die sich alle kennen, oder gar nicht, dann macht das Problem keinen Sinn.
Iridium Auf diesen Beitrag antworten »

Mal mal den vollständigen Graph mit 18 Knoten und schau mal, ob du die Kanten so mit zwei Farben färben kannst, daß ein/kein Vierring (vier Knoten, sechs Kanten) mit derselben Färbung existiert...darauf läuft das ganze glaube ich hinaus...
kiste Auf diesen Beitrag antworten »

Literaturhinweis:
Greenwood, R. E. and Gleason, A. M. "Combinatorial Relations and Chromatic Graphs." Canad. J. Math. 7, 1-7, 1955.

Dort wird gerade R(4,4) = 18 bewiesen.
Iridium Auf diesen Beitrag antworten »

Zitat:
Original von kiste
Literaturhinweis:
Greenwood, R. E. and Gleason, A. M. "Combinatorial Relations and Chromatic Graphs." Canad. J. Math. 7, 1-7, 1955.

Dort wird gerade R(4,4) = 18 bewiesen.


@ kiste: Ist das ein Problem aus der Ramsey Theorie? Ich kenn mich da nur insoweit aus, daß ich mir mal abgespeichert habe, daß nur relativ überschaubare Problemstellungen bisher beweisen wurden und schon bei sehr kleinen Zahlen/Graphen nichts genaues über die Lösungen mehr bekannt ist...
kiste Auf diesen Beitrag antworten »

Ja. 4,4 ist aber noch klein genug dass man es gelöst hat Augenzwinkern
Bereits 5,5 ist ungelöst
 
 
Iridium Auf diesen Beitrag antworten »

@ kiste. Ja, ok, danke...sowas in der Art hatte ich in Erinnerung.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »