Matroids Matheplanet Forum Index
Moderiert von matroid
Matroids Matheplanet Forum Index » 6. Matheplanet Challenge » Problem 4
Druckversion
Druckversion
Autor
Universität/Hochschule J Problem 4
Eckard
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 14.10.2002
Mitteilungen: 6820
Aus: Magdeburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2004-10-28





Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Morris
Senior Letzter Besuch: im letzten Monat
Dabei seit: 14.07.2003
Mitteilungen: 1537
Aus: Flensburg, Wohnort Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2004-10-28


Hallo Eckard!
Ich bin mir nicht sicher, ob ich die Aufgabe richtig verstehe. Lass mich deshalb formulieren, wie ich sie auffasse:

1. Es wird insgesamt ueber drei Aufgaben gesprochen, o.B.d.A. die Aufgaben 1, 2 und 3.

2. n_1 der 17 Beteiligten fuehren (mindestens) ein Gespraech ueber Aufgabe 1, n_2 ueber Aufgabe 2 und n_3 ueber Aufgabe 3.

3. Gefragt ist nun danach, wie gross max(n_1, n_2, n_3) mindestens sein muss.

Ist das so richtig? Nach min(n_1, n_2, n_3) zu fragen, wuerde ja wenig Sinn machen, denn das ist im besten Fall 0.

Danke und viele Gruesse
Morris

[ Nachricht wurde editiert von Morris am 28.10.2004 15:00:58 ]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Eckard
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 14.10.2002
Mitteilungen: 6820
Aus: Magdeburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2004-10-28


Hallo Morris,

ich denke, da fehlt noch ein Aspekt der Aufgabenstellung in dem, was du in deiner Formulierung schreibst. D.h. ganz so einfach ist es nicht. Aber mehr möchte ich dazu jetzt aus verständlichen Gründen nicht sagen.

Gruß Eckard



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Pebbe
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 17.07.2004
Mitteilungen: 11
Aus: Dresden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2004-10-28


Ich glaube, was Eckard meint, ist folgendes:

Wir betrachten eine Menge von Teammitgliedern, die PAARWEISE untereinander über dieselbe Aufgabe kommunizieren. Also jeder mit jedem innerhalb der Menge. Wir wählen die mächtigste aller solchen Mengen, sie habe die Mächtigkeit M.
Gesucht ist das Minimum m = min(M) bezüglich aller möglichen Verteilungen der der Aufgaben, d.h. egal wer mit wem über welche Aufgabe kommuniziert, immer gibt es eine derartige Menge mit m Elementen.

Bin mir ziemlich sicher dass das stimmt.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Eckard
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 14.10.2002
Mitteilungen: 6820
Aus: Magdeburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2004-10-28


:-)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ex_Mitglied_1790
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2004-10-30


fed-Code einblenden




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
JohnDoe
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.07.2003
Mitteilungen: 2146
Aus: Tirol
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2004-10-30


Hi hansibal,

bist Du sicher? Wenn ich es recht verstehe geht es doch um die gefärbten Graphen der Ramseytheorie. Und für 3 Farben sind nicht viele Ramseyzahlen bekannt
Da kann uns sicher Fabi Genaueres sagen...

Gruß, Heinz



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ex_Mitglied_1790
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2004-10-30


Nein,
sicher bin ich mir nicht, es war nur ein versuch.
Ehrlich gesagt, habe ich auch auf Fabi gewartet.  

mfg
hansibal



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Zahlenteufel
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 14.07.2002
Mitteilungen: 1096
Aus: Essen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2004-10-30


Hallo

@Hansibal Deine untere Schranke ist falsch.
Hier in Forum wurde mal ein ähnliches Problem gestellt,
daß bei der Lösung hilft.
"Unter 6 Personen gibt es
stets drei sich gegenseitig kennen oder nicht kennen"


Gruß
Chrstoph



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Pebbe
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 17.07.2004
Mitteilungen: 11
Aus: Dresden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2004-10-30


OK. Die Lösung lautet:
(1) Es gibt immer mindestens 3 Leute, die sich untereinander über dieselbe Aufgabe austauschen.
(2) Es gibt Verteilungen, bei denen sich nie mehr als 3 Mitglieder paarweise über dieselbe Aufgabe austauschen.

Beweis:
Um das ganze etwas zu abstrahieren, setzen wir die 17 Teammitglieder mit Knoten gleich. Zwei Teammitglieder tauschen sich immer über genau eine Aufgabe aus. Welche, wird durch die Farbe der Kante zwischen den entsprechenden Knoten verdeutlicht:
rot für Aufgabe 1
grün für Aufgabe 2
blau für Aufgabe 3

(1) ist äquivalent dazu, dass es in jeder 3-Färbung des K_17 (d.h. der Färbung jeder Kante zwischen 17 Knoten mit einer von 3 Farben) immer ein Dreieck in einer der 3 Farben gibt.
Wir wählen einen der 17 Knoten aus, z.B. der zu matroid zugehörige Knoten :-). Nach Schubfachprinzip gibt es eine Farbe (oBdA rot), so dass matroid mit (mindestens) 6 der 16 verbleibenden Knoten mit einer roten Kante verbunden ist.
Wir betrachten nun den Graphen mit diesen 6 Knoten. Wenn es in ihm eine rote Kante gibt (zwischen A und B), dann gibt es ein rotes Dreieck A-B-matroid. Wenn es keine solche Kante gibt, ist der Graph vollständig mit grün und blau gefärbt. Laut dem Resultat, das Zahlenteufel erwähnte, gibt es dann stets ein grünes oder ein blaues Dreieck (weil die Ramsey-Zahl R(3,3) = 6 ist).
Das kann man auch beweisen: Sei A einer der 6 Knoten, dann ist die Kante zu mindestens 3 Knoten B,C,D in der gleichen Farbe, oBdA grün. Wenn zwischen diesen drei Kanten eine grüne Kante B-C existiert, ist das Dreieck A-B-C grün. Wenn nicht, ist das Dreieck B-C-D blau.
Es gibt also immer ein Dreieck in einer der 3 Farben, w.z.b.w.
Soeben haben wir bewiesen, dass die Ramsey-Zahl R(3,3,3) höchstens 17 ist (Tatsächlich gilt sogar R(3,3,3)=17).
(2) Jetzt müssen wir noch zeigen, dass es eine Färbung gibt, für die es keine vier Knoten gibt, deren Verbindungskanten alle die gleiche Farbe haben.
Zunächst betrachten wir dazu eine Färbung des K_8 mit 2 Farben: Die Knoten nummerieren wir mit 1 bis 8 durch. Die folgenden Kanten färben wir
grün: (1,2), (1,3), (1,4), (1,5), (1,6), (2,3), (2,4), (2,7), (2,8), (3,5), (3,8), (4,6), (4,7), (5,6), (5,8), (6,7), (7,8) (17 Kanten)
blau: (1,7), (1,8), (2,5), (2,6), (3,4), (3,6), (3,7), (4,5), (4,8), (5,7), (6,8) (11 Kanten)
In diesem Graphen gibt es weder ein blaues Dreieck noch ein grünes Viereck (mit Diagonalen, d.h. keine 4 Knoten, deren 6 Verbindungskanten alle grün sind). (ist mir jetzt zu mühsam zu beweisen, man male sich das einfach mal auf und gucke nach ;-) ). Mit 9 Knoten würde das übrigens nicht mehr funktionieren, da die Ramsey-Zahl R(4,3)=9 ist.

Kehren wir zu unseren 17 Leuten zurück. Wir nehmen wieder matroid heraus und färben jede Kante von ihm mit rot.
Dann haben wir noch 16 Leute übrig. Wir teilen sie in zwei Gruppen G1 und G2 mit je 8 Mitgliedern ein.
Diese beiden Gruppen werden mit der oben angegebenen Färbung gefärbt.
Alle Kanten zwischen G1 und G2 schließlich färben wir rot.
Jetzt wählen wir irgendwelche 4 Knoten aus und zeigen, dass nicht alle Kanten zwischen ihnen gleichfarbig sind.
Nach dem Schubfachprinzip gehören mindestens zwei der 4 Knoten zu einer der Gruppen G1 oder G2. Die entsprechende Kante ist also nicht rot. Wenn nun ein anderer Knoten entweder matroid heißt oder zur anderen Gruppe (G2 oder G1) gehört, dann ist die Verbindungskante zu ihm rot, somit liegt also kein gleichfarbiges Viereck vor.
Wenn aber alle 4 Knoten zu einer der Gruppen G1 oder G2 gehören, gibt es erst recht kein gleichfarbiges Viereck, wie oben bemerkt.
Tja, und das war zu zeigen.
Nebenbei, gibt es sogar kein blaues Dreieck. Wir haben also gezeigt, dass die Ramsey-Zahl R(4,4,3) > 17 ist.
Es müsste sogar eine Färbung mit nur 2 Farben geben, weil R(4,4)=18 ist.
Oder man könnte auch erreichen, dass es kein grünes Dreieck gibt, denn es gilt 30 <= R(4,3,3) <= 34. So auf die Schnelle hab ich das aber nicht hingekriegt.
[ Nachricht wurde editiert von Pebbe am 30.10.2004 18:02:20 ]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Ex_Mitglied_1790
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2004-11-02


Hallo,

jetzt ist es mir klar.
Zuerst war ich nur verwirrt, was Ramsey damit zu tun hat
und ich habe Graphen gezeichnet und meine Argumentation ausprobiert und es hat geklappt.
Ich habe bei der Aufgabe das "untereinander" übersehen/ignoriert.

mfg
hansibal



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Buri
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2003
Mitteilungen: 46189
Aus: Dresden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2004-11-04


Hallo Pebbe,
das hast du gut gemacht!
Ich glaube, das paßt.
Dein Beitrag steht schon ziemlich lange da, sorry, daß ich es übersah!
Meinen Respekt!
Gruß Buri




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Eckard
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 14.10.2002
Mitteilungen: 6820
Aus: Magdeburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2004-11-07





Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Eckard
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 14.10.2002
Mitteilungen: 6820
Aus: Magdeburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, vom Themenstarter, eingetragen 2004-11-07


7 Punkte natürlich für euch! Wie erwähnt, ist das ein recht alter Hut, aber Kombinatorik ist ja nicht jedermanns Sache. Deswegen habe ich dieses Problem - obwohl hinlänglich bekannt - trotzdem genommen.

Gruß Eckard



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Buri
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2003
Mitteilungen: 46189
Aus: Dresden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2004-11-07


Hi Eckard,
du verzichtest darauf, ein Beispiel zu geben, wo keine vier über dasselbe Thema schreiben, das ist schlecht.
Das Team hat da besser aufgepaßt, und sich auch Mühe mit diesem (erforderlichen!) Nachweis gegeben.
Gruß Buri



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Eckard
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 14.10.2002
Mitteilungen: 6820
Aus: Magdeburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, vom Themenstarter, eingetragen 2004-11-07


Hi Buri,

lies bitte noch einmal den letzten Satz der Aufgabenstellung, gefragt war nur die minimale Anzahl der korrespondierenden Mitglieder. Dass ihr mehr gemacht habt, ist sehr löblich, war aber hier nicht gefordert.

Gruß Eckard



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Buri
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2003
Mitteilungen: 46189
Aus: Dresden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2004-11-07


Hi Eckard,
"welches ist die minimale Anzahl?" ist die Frage, das stimmt.
Noch genauer gesagt, jeder Graphenfärbung kann man die Knotenanzahl eines maximalen darin enthaltenen monochromatischen vollständigen Teilgraphen zuordnen, von dieser Maximalanzahl ist dann das Minimum, genommen über alle Färbungen, gesucht.
Du hast bewiesen, die minimale Anzahl ist größer oder gleich 3.
Wir dagegen haben, wie verlangt, bewiesen, die minimale Anzahl ist gleich 3.
Eine ähnliche Verständnisschwierigkeit gab es auch bei dieser Aufgabe von der 3. MPC.
Auch hier hast du, wie ich im Nachhinein mit Erstaunen sehen muß, den Nachweis, daß die dort gesuchte Zahl nicht größer als 9 ist, nicht erbracht, das Team von damals aber, soweit ich nachgeblättert habe, auch nicht, obwohl ich in dem Beitrag, der deiner Lösung vorausgeht, dazu einlud, diese Lücke zu schließen.
Das war aber damals nicht so wichtig, da die Regeln anders waren, niemand anders weiß das besser als du.
@alle
Nur die Richtigkeit der Antwort hat gezählt, ich bin aber damit einverstanden, diesem Mißstand abzuhelfen, wem gelingt es, diese Änderung der Regeln am besten in Worte zu gießen?
Ich weiß, irgendwo steht es, aber man sollte doch ein neues Regelwerk erstellen, wo dies berücksichtigt ist, das alte Regelwerk von Eckards MPC 1 sollte aus historischen Gründen unverändert stehenbleiben.
Gruß Buri

[ Nachricht wurde editiert von Buri am 07.11.2004 15:26:34 ]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Eckard hat die Antworten auf ihre/seine Frage gesehen.
Das Thema wurde von einem Senior oder Moderator abgehakt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]