Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Ramsey Theorie - die einfachste Aufgabe
109 views
Skip to first unread message
JVR
Jan 4, 2024, 4:01:04 PM1/4/24
to
Gegeben seien 5 Punkte in der Ebene von denen keine
drei auf einer Geraden liegen.
Man beweise, dass 4 der 5 Punkte ein konvexes Viereck
bilden.
drei auf einer Geraden liegen.
Man beweise, dass 4 der 5 Punkte ein konvexes Viereck
bilden.
Fritz Feldhase
Jan 4, 2024, 4:37:06 PM1/4/24
to
Rainer Rosenthal
Jan 4, 2024, 6:44:10 PM1/4/24
to
Ich nehme diesen Ansatz mit in meinen Schlaf:
ich betrachte 4 Punkte, die *kein* konvexes Viereck bilden.
Sie bilden also ein Dreieck ABC mit Punkt D im Inneren.
Jetzt muss ich "nur" zeigen, dass egal wohin ich einen 5-ten Punkt E
hinlege (natürlich nicht kollinear mit irgend zweien der Punkte A, B, C,
D), dieser Punkt ein konvexes Viereck liefern muss, d.h. dass mindestens
eines der Vierecke ABCE, BCDE, ACDE, ABDE konvex ist.
Mit schon recht kleinen Äugelein beginne ich eine etwas unelegante Reihe
von Fallunterscheidungen abzuarbeiten:
1. E im Inneren von ABC. Dann ist E o.B.d.A. im Inneren von ABD,
1.1 Gerade CD trennt A und E. Dann ist BCDE konvex.
1.2 Gerade CD trennt B und E. Dann ist ACDE konvex.
Bereits 1.2 hätte ich mir sparen können, denn ich habe Freiheiten beim
Benennen der Punkte, die mir Folgendes zu sagen erlauben:
1. E im Inneren von ABC.
Dann ist E o.B.d.A. im Inneren von ABD und Gerade CD trennt A und E.
Dann ist BCDE konvex.
So kann's weitergehen ... aber nicht mehr vorm Zubettgehen.
Gute Nacht und danke für die schöne Aufgabe.
Wenn das Licht aus ist, dann wird alles dunkel, und die Punkte sind
nicht mehr individuell unterscheidbar. Und dann ... *schnarch*!
(Unterschrift entfällt, denn ich bin offensichtlich eingeschlafen.)
Fritz Feldhase
Jan 4, 2024, 7:10:02 PM1/4/24
to
On Friday, January 5, 2024 at 12:44:10 AM UTC+1, Rainer Rosenthal wrote:
> Am 04.01.2024 um 22:01 schrieb JVR:
> >
> > Gegeben seien 5 Punkte in der Ebene von denen keine drei auf einer Geraden liegen.
> > Man beweise, dass 4 der 5 Punkte ein konvexes Viereck bilden.
> >
> Hui, schöne Aufgabe!
Eigentlich nicht sonderlich schwer. Aber wenn's dunkel wird, kann man leider nicht mal mehr die Hand vor Augen sehen (siehe Mückenheim).
> Am 04.01.2024 um 22:01 schrieb JVR:
> >
> > Gegeben seien 5 Punkte in der Ebene von denen keine drei auf einer Geraden liegen.
> > Man beweise, dass 4 der 5 Punkte ein konvexes Viereck bilden.
> >
> Hui, schöne Aufgabe!
Außerdem zieht sich die detailierte Ausarbeitung des Beweises (hin) wie ein Kaugummi. :-P
In der Tat:
> Wenn das Licht aus ist, dann wird alles dunkel, und die Punkte sind
> nicht mehr individuell unterscheidbar. Und dann ... *schnarch*!
Gute Nacht.
Rainer Rosenthal
Jan 5, 2024, 3:26:13 AM1/5/24
to
Am 04.01.2024 um 22:01 schrieb JVR:
Die Teillösung "E innen" hatte ich vorm Schlafengehen gepostet.
Für den Fall "E außen" biete ich diesen Tagebucheintrag, der allerdings
ein bisschen zu breit für den Rand war:
#
# 05.01.23 Sehr schöne Aufgabe. Ich habe was skizziert
# und darüber gleich in der Nacht noch etwas gepostet.
# Damit habe ich mein Hirn offenbar genügend angeregt,
# um beim Aufwachen die Lösung zu sehen. Habe die Skizze
# entsprechend aktualisiert und eingescannt. Damit
# werden die konvexen Vierecke "mit D", also ABDE, BCDE
# und ACDE sichtbar.
# Das erledigt den Fall "E außerhalb von ABC".
# Den Fall "innerhalb" hatte ich bereits gepostet:
# Dann ist E o.B.d.A. im Inneren von ABD und Gerade CD
# trennt A und E. Dann ist BCDE konvex.
#
Die aktualisierte Skizze ist hier:
http://rwro.de/Demonstrationen/RamseyABCDE.png
Außer für "zweifelnde Blödmänner" ist nun alles "clearly" sichtbar.
Nee, Scherz. Nach dem Frühstück schreibe ich noch ein paar Worte.
Gruß,
Rainer Rosenthal
r.ros...@web.de
Rainer Rosenthal
Jan 5, 2024, 4:24:28 AM1/5/24
to
Am 05.01.2024 um 00:44 schrieb Rainer Rosenthal:
> 1. E im Inneren von ABC.
> Dann ist E o.B.d.A. im Inneren von ABD und Gerade CD trennt A und E.
>
Das ist "clearly wrong" im allgemeinen Fall. Die Anschauung hat mir
> 1. E im Inneren von ABC.
> Dann ist E o.B.d.A. im Inneren von ABD und Gerade CD trennt A und E.
>
einen Streich gespielt und mich nur spitzwinklige Dreiecke ABC sehen lassen.
Gruß,
RR
Rainer Rosenthal
Jan 5, 2024, 4:36:58 AM1/5/24
to
Am 05.01.2024 um 09:26 schrieb Rainer Rosenthal:
>
> Die Teillösung "E innen" hatte ich vorm Schlafengehen gepostet.
>
Als kritischer Cis-Mathematiker (aka "zweifelnder Blödmann" oder
>
> Die Teillösung "E innen" hatte ich vorm Schlafengehen gepostet.
>
"Matheologe") muss ich protestieren und habe es bereits getan.
Beim Duschen habe ich weiter nachgedacht und wollte die Geometrie so
weit wie möglich aus dem Spiel lassen. "Ramsey" fordert Kombinatorik.
Eine schöne Charakterisierung (*) von "konvexes Viereck" ist mir dabei
in den Sinn gekommen, die ich auch noch vor dem Frühstück loswerden möchte:
Vier Punkte P, Q, R S in der Ebene bilden genau dann ein konvexes
Viereck, wenn keines der Segmentpaare (PQ,RS), (PR,QS), (PS,QR) einen
Schnittpunkt hat.
Damit bin ich von Orientierungsfragen verschont und muss mich auch nicht
mit "überschlagenen Vierecken" plagen.
Wie gesagt: nach dem Frühstück mehr.
Gruß,
RR
(*) Nein, ich erhebe keinen Prioritätsanspruch, aber man wird sich ja
noch mal freuen dürfen.
Stefan Schmitz
Jan 5, 2024, 5:23:26 AM1/5/24
to
Am 05.01.2024 um 10:36 schrieb Rainer Rosenthal:
> Am 05.01.2024 um 09:26 schrieb Rainer Rosenthal:
> Wie gesagt: nach dem Frühstück mehr.
Um halb elf noch vor dem Frühstück, aber schon seit mindestens einer
> Am 05.01.2024 um 09:26 schrieb Rainer Rosenthal:
> Wie gesagt: nach dem Frühstück mehr.
Stunde auf. Wann ist denn Mittag bei dir?
Rainer Rosenthal
Jan 5, 2024, 5:27:46 AM1/5/24
to
Rainer Rosenthal
Jan 5, 2024, 2:10:16 PM1/5/24
to
Am 04.01.2024 um 22:01 schrieb JVR:
Es gibt 5 verschiedenen Punkten der Ebene, von denen keine drei auf
einer Geraden liegen, derart, dass je 4 der 5 Punkte stets ein
nicht-konvexes Viereck bilden. Die Punkte nennen wir A, B, C, D, E. Wir
wissen, dass insbesondere ABCD nicht konvex ist, und wir nehmen o.B.d.A.
an, dass D im Inneren des Dreiecks ABC liegt.
Dann liegt die Situation vor, die in dieser Figur dargestellt ist:
http://rwro.de/Demonstrationen/RamseyABCDE_solution.png
Die Ebene kann in 9 Regionen aufgeteilt werden, so dass in jeder Region
gilt: ist E ein Punkt dieser Region, dann bildet er zusammen mit 3
Punkten aus {A, B, C, D} ein konvexes Viereck.
Damit ist ein Widerspruch zur Annahme gefunden, denn E ist ein Punkt der
Ebene und muss folglich in einer der 9 Regionen liegen, d.h. er gehört
zu 4 der 5 Punkte, die ein konvexes Viereck bilden.
Q.E.D.
Rainer Rosenthal
r.ros...@web.de
Uff - "einfachste Aufgabe" ... ja, ich kenne das: bei Ramsey fingen
meine Synapsen schon immer zu glühen an, wenn ich nur die
Aufgabenstellung verstehen wollte.
Danke jedenfalls für die schöne Turnübung.
@verschmitzte Mitposter: Abendbrot ist vorbei :-;
JVR
Jan 6, 2024, 4:20:54 AM1/6/24
to
Eine äquivalente Lösung ist folgende:
1. Falls die konvexe Hülle ein Fünfeck ist, dann kann man jeden Punkt auslassen
2. Falls die konvexe Hülle ein Viereck ist, dann ist der Fall erledigt
3. Falls die konvexe Hülle ein Dreieck ist, dann kommt die Voraussetzung zur
Geltung, denn auf einer Seite der Verbindungsgeraden der 2 inneren Punkte
liegen 2 Punkte der Hülle, die zusammen mit ersteren das gesuchte konvexe Viereck bilden.
Rainer Rosenthal
Jan 6, 2024, 7:29:41 AM1/6/24
to
Am 06.01.2024 um 10:20 schrieb JVR:
> Das funktioniert, d.h. lässt sich so formulieren, dass daraus ein Beweis wird.
Danke.
> Das funktioniert, d.h. lässt sich so formulieren, dass daraus ein Beweis wird.
> Eine äquivalente Lösung ist folgende:
> 1. Falls die konvexe Hülle ein Fünfeck ist, dann kann man jeden Punkt auslassen
> 2. Falls die konvexe Hülle ein Viereck ist, dann ist der Fall erledigt
> 3. Falls die konvexe Hülle ein Dreieck ist, dann kommt die Voraussetzung zur
> Geltung, denn auf einer Seite der Verbindungsgeraden der 2 inneren Punkte
> liegen 2 Punkte der Hülle, die zusammen mit ersteren das gesuchte konvexe Viereck bilden.
Gruß,
RR
Rainer Rosenthal
Jan 6, 2024, 10:15:30 AM1/6/24
to
Am 04.01.2024 um 22:01 schrieb JVR:
bei der Entwicklung der Ramsay-Theorie:
https://en.wikipedia.org/wiki/Happy_ending_problem
Insofern könnte ich "einfachste Aufgabe" als Bewertung gelten lassen.
Ansonsten muss ich sagen, ich fand die Aufgabe wunderschön, aber
keinesfalls einfach, und schon gar nicht "einfachst". Ist wahrscheinlich
Mathematiker-Humor :-)
Das Bild http://rwro.de/Demonstrationen/RamseyABCDE_solution.png
zu malen, hat auch Spaß gemacht. Ich überlege, ob ich nicht doch noch
was hineinmale, um die sehr trockene Anmerkung unten im Bild deutlicher
zu machen. So könnte z.B. in dem gelben Dreieck DCY genauer geschrieben
werden, warum es gelb gefärbt ist. Steht zwar da: für E in diesem
Dreieck ist BCDE konvex, aber hier gilt das deswegen, weil die Strecke
EB die Strecke CD schneidet. Da wäre ein Vermerk "EBxCD" vielleicht
hilfreich. In BDZ hätte man dann "ECxBD" und im großen gelben Feld "EDxBC".
Der oben angegebene Link wurde mir genannt, als ich die Aufgabe
weitergegeben habe. Er ist sehr lesenswert.
Dank an JVR für die Bereicherung des dsm-Alltags.
Gruß,
RR
Fritz Feldhase
Jan 6, 2024, 6:02:35 PM1/6/24
to
On Saturday, January 6, 2024 at 4:15:30 PM UTC+1, Rainer Rosenthal wrote:
> Am 04.01.2024 um 22:01 schrieb JVR:
> >
> > Gegeben seien 5 Punkte in der Ebene von denen keine
> > drei auf einer Geraden liegen.
> > Man beweise, dass 4 der 5 Punkte ein konvexes Viereck
> > bilden.
Hier findet sich ein kurzer Hinweis auf so einen Beweis:
> Am 04.01.2024 um 22:01 schrieb JVR:
> >
> > Gegeben seien 5 Punkte in der Ebene von denen keine
> > drei auf einer Geraden liegen.
> > Man beweise, dass 4 der 5 Punkte ein konvexes Viereck
> > bilden.
P. Erdös and G. Szekeres, A Combinatorial Problem in Geometry (1935):
"INTRODUCTION.
Our present problem bas been suggested by Miss Esther Klein in connection with the following proposition.
From 5 points of the plane of which no three lie on the same straight line it is always possible to select 4 points determining a convex quadrilateral.
We present E. Klein’s proof here because later on we are going to make use of it. If the least convex polygon which encloses the points is a quadrilateral or a pentagon the theorem
is trivial. Let therefore the enclosing polygon be a triangle ABC. Then the two remaining points D and E are inside ABC. Two of the given points (say A and C) must lie on the same side of the connecting straight line DE. Then it is clear that AEDC is a convex quadrilateral."
Rainer Rosenthal
Jan 7, 2024, 5:09:40 AM1/7/24
to
Am 06.01.2024 um 10:20 schrieb JVR:
>
>
> 3. Falls die konvexe Hülle ein Dreieck ist, dann kommt die Voraussetzung zur > Geltung, denn auf einer Seite der Verbindungsgeraden der 2 inneren Punkte
> liegen 2 Punkte der Hülle, die zusammen mit ersteren das gesuchte konvexe Viereck bilden.
Das ist an Schlichtheit nicht zu toppen, sehr schön!
> liegen 2 Punkte der Hülle, die zusammen mit ersteren das gesuchte konvexe Viereck bilden.
Meine kompliziertere Denke hat mich aber auch noch weiter beschäftigt.
In dem Fall 3 mit dem Punkt D im Inneren des Dreiecks ABC muss der Punkt
E, wenn er auch im Inneren ist, in einem der Dreiecke ABD, BCD, CAD
liegen. Betrachte ich z.B. E in ABD, dann ist der andere Eckpunkt des
großen Dreiecks, also C, außerhalb des Dreiecks ABD. Die Strecke EC ist
eine stetige Verbindung zwischen dem Inneren und dem Äußeren des
geschlossenen Gebiets mit dem aus den Segmenten AB, BD und DA gebildeten
Rand. Darum muss ein Schnittpunkt S von EC mit mindestens einem dieser
Segmente existieren. Es muss sogar genau eins sein, weil Kollinearität
ausgeschlossen wurde. Uff - plötzlich bin ich mitten in der Geometrie
mit dem Axiom von Pasch usw.
Warum einfach, wenn's auch kompliziert geht :-)
Ein weiterer Gedanke, den ich aber wahrscheinlich nicht mehr zu Ende
denken werde: Der Fall 3 mit D im Inneren und E im Äußeren des Dreiecks
ABC ruft nach Symmetrisierung. Ich stelle mir die Situation darum auf
einer Kugel vor mit den Großkreisen als Geraden. Dann ist die
Unsymmetrie zwischen D und E weg. Wie gesagt: nette Gedankenspielerei.
Gruß,
RR
Stephan Gerlach
Jan 14, 2024, 7:30:51 PM1/14/24
to
JVR schrieb:
Die 5 Punkte seien mit A, B, C, D und E bezeichnet.
Wir betrachten 3 Fälle, die konvexe Hülle conv(A,B,C,D,E) der 5 Punkte
betreffend.
In jedem Fall wird der Fakt genutzt, daß keine drei Punkte auf einer
gemeinsamen Geraden liegen (erwähne ich nicht jedesmal neu).
Fall 1 (trivial):
----------------
conv(A,B,C,D,E) ist ein Fünfeck, d.h. die 5 Punkte sind genau die Ecken
dieses Fünfecks. In diesem Fall wählt man einfach irgendwelche der 4
Punkte (z.B. A, B, C, D). Diese bilden bereits das gesuchte konvexe
Viereck (was genaugenommen nochmal formal begründet werden müßte, was
ich mir hier spare).
Fall 2 (noch trivialer):
------------------------
conv(A,B,C,D,E) ist ein Viereck. D.h. 4 der Punkte (z.B. A, B, C, D)
sind Ecken dieses Vierecks und ein weiterer Punkt (z.B. E) liegt im
Inneren des Vierecks. Dann bilden die 4 Ecken A, B, C, D das gesuchte
konvexe Viereck.
Fall 3 (der einzige schwierigere Fall):
---------------------------------------
conv(A,B,C,D,E) ist ein Dreieck. Also sind 3 der Punkte die Ecken dieses
Dreiecks, seien dies o.B.d.A die Punkte A, B und C.
Die anderen beiden Punkte D und E liegen dann im inneren des Dreiecks.
Wähle nun einen der beiden Punkte aus, z.B. D. Dann wird das Dreieck ABC
durch die (inneren) Kanten AD, BD und CD in drei (Teil-)Dreiecke ABD,
BCD, CAD zerlegt.
Der "übrige" Punkt E liegt nun in genau einem dieser Dreiecke, sei dies
o.B.d.A das Dreieck ABD.
Betrachte nun die Gerade durch C und D. Diese schneidet die Kante AB im
Punkt P (einfach Kante CD bis zu AB "verlängern" ergibt Punkt P).
Das Dreieck ABD wird dadurch nochmal in zwei Dreiecke APD und PBD zerlegt.
Da E in ABD liegt, liegt dieser Punkt konstruktionsbedingt in genau
einem dieser "neuen" Teil-Dreiecke APD und PBD. Sei dies o.B.d.A das
Dreieck APD, d.h. E liegt im Dreieck APD.
Dann ist AEDC das gesuchte konvexe Viereck.
--
> Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
Wir betrachten 3 Fälle, die konvexe Hülle conv(A,B,C,D,E) der 5 Punkte
betreffend.
In jedem Fall wird der Fakt genutzt, daß keine drei Punkte auf einer
gemeinsamen Geraden liegen (erwähne ich nicht jedesmal neu).
Fall 1 (trivial):
----------------
conv(A,B,C,D,E) ist ein Fünfeck, d.h. die 5 Punkte sind genau die Ecken
dieses Fünfecks. In diesem Fall wählt man einfach irgendwelche der 4
Punkte (z.B. A, B, C, D). Diese bilden bereits das gesuchte konvexe
Viereck (was genaugenommen nochmal formal begründet werden müßte, was
ich mir hier spare).
Fall 2 (noch trivialer):
------------------------
conv(A,B,C,D,E) ist ein Viereck. D.h. 4 der Punkte (z.B. A, B, C, D)
sind Ecken dieses Vierecks und ein weiterer Punkt (z.B. E) liegt im
Inneren des Vierecks. Dann bilden die 4 Ecken A, B, C, D das gesuchte
konvexe Viereck.
Fall 3 (der einzige schwierigere Fall):
---------------------------------------
conv(A,B,C,D,E) ist ein Dreieck. Also sind 3 der Punkte die Ecken dieses
Dreiecks, seien dies o.B.d.A die Punkte A, B und C.
Die anderen beiden Punkte D und E liegen dann im inneren des Dreiecks.
Wähle nun einen der beiden Punkte aus, z.B. D. Dann wird das Dreieck ABC
durch die (inneren) Kanten AD, BD und CD in drei (Teil-)Dreiecke ABD,
BCD, CAD zerlegt.
Der "übrige" Punkt E liegt nun in genau einem dieser Dreiecke, sei dies
o.B.d.A das Dreieck ABD.
Betrachte nun die Gerade durch C und D. Diese schneidet die Kante AB im
Punkt P (einfach Kante CD bis zu AB "verlängern" ergibt Punkt P).
Das Dreieck ABD wird dadurch nochmal in zwei Dreiecke APD und PBD zerlegt.
Da E in ABD liegt, liegt dieser Punkt konstruktionsbedingt in genau
einem dieser "neuen" Teil-Dreiecke APD und PBD. Sei dies o.B.d.A das
Dreieck APD, d.h. E liegt im Dreieck APD.
Dann ist AEDC das gesuchte konvexe Viereck.
--
> Eigentlich sollte Brain 1.0 laufen.
gut, dann werde ich mir das morgen mal besorgen...
(...Dialog aus m.p.d.g.w.a.)
Stephan Gerlach
Jan 14, 2024, 8:09:05 PM1/14/24
to
Rainer Rosenthal schrieb:
Es schließt die beiden Fälle mit ein, daß die konvexe Hülle der 5 Punkte
ein Dreieck oder ein Viereck ist.
Der Fall, daß diese konvexe Hülle ein Fünfeck ist, fehlt allerdings
noch, denn im Bild ist D bereits in der konvexen Hülle von A, B und C
enthalten. Allerdings ist dieser "vergessene" Fall (ebenso wie der Fall,
daß E außerhalb der konvexen Hülle von A, B, C liegt und D darin) trivial.
> Am 04.01.2024 um 22:01 schrieb JVR:
>> Gegeben seien 5 Punkte in der Ebene von denen keine
>> drei auf einer Geraden liegen.
>> Man beweise, dass 4 der 5 Punkte ein konvexes Viereck
>> bilden.
>
> Wenn ich Wikipedia glauben darf, dann hat diese Aufgabe Pate gestanden
> bei der Entwicklung der Ramsay-Theorie:
> https://en.wikipedia.org/wiki/Happy_ending_problem
>
> Insofern könnte ich "einfachste Aufgabe" als Bewertung gelten lassen.
> Ansonsten muss ich sagen, ich fand die Aufgabe wunderschön, aber
> keinesfalls einfach, und schon gar nicht "einfachst". Ist wahrscheinlich
> Mathematiker-Humor :-)
>
> Das Bild http://rwro.de/Demonstrationen/RamseyABCDE_solution.png
> zu malen, hat auch Spaß gemacht.
Das ist im wesentlichen die Idee, die ich auch hatte.
>> Gegeben seien 5 Punkte in der Ebene von denen keine
>> drei auf einer Geraden liegen.
>> Man beweise, dass 4 der 5 Punkte ein konvexes Viereck
>> bilden.
>
> Wenn ich Wikipedia glauben darf, dann hat diese Aufgabe Pate gestanden
> bei der Entwicklung der Ramsay-Theorie:
> https://en.wikipedia.org/wiki/Happy_ending_problem
>
> Insofern könnte ich "einfachste Aufgabe" als Bewertung gelten lassen.
> Ansonsten muss ich sagen, ich fand die Aufgabe wunderschön, aber
> keinesfalls einfach, und schon gar nicht "einfachst". Ist wahrscheinlich
> Mathematiker-Humor :-)
>
> Das Bild http://rwro.de/Demonstrationen/RamseyABCDE_solution.png
> zu malen, hat auch Spaß gemacht.
Es schließt die beiden Fälle mit ein, daß die konvexe Hülle der 5 Punkte
ein Dreieck oder ein Viereck ist.
Der Fall, daß diese konvexe Hülle ein Fünfeck ist, fehlt allerdings
noch, denn im Bild ist D bereits in der konvexen Hülle von A, B und C
enthalten. Allerdings ist dieser "vergessene" Fall (ebenso wie der Fall,
daß E außerhalb der konvexen Hülle von A, B, C liegt und D darin) trivial.
0 new messages