Der große Empfang < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Übungsaufgabe) Übungsaufgabe  | | Datum: | 20:30 Mi 14.07.2004 | | Autor: | Gnometech |
Meinen Gruß!
Also, hier eine kleine Aufgabe, damit es euch nicht zu langweilig wird:
Auf einem Empfang befinden sich 37 Personen. Man kann ihre Positionen als punktförmig in irgendeiner Ebene annehmen. Wir wollen außerdem annehmen, dass die Abstände, die sie voneinander haben, paarweise verschieden sind. Alles klar?
Nun sucht jede Person für sich diejenige Person heraus, die ihm am nächsten steht (dies ist eindeutig, weil die Abstände ja alle verschieden sind) und ruft dieser ein "Hallo!" zu und stellt sich vor.
Aufgabe 1: Zeige, dass es mindestens eine Person gibt, der sich niemand vorstellt.
Aufgabe 2: Es gibt keine Person, der sich mehr als 5 Personen vorstellen.
Viel Spaß!
Lars
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:20 Sa 17.07.2004 | | Autor: | Wessel |
Hallo Lars,
eigentlich bin ich völlig überfragt, aber setze mich nun mal hin und schreibe meinen Weg auf, auch wenn hier nicht das rauskommt, was Du forderst...
Gegeben sind also 37 Personen, die paarweis verschiedene Abstände zu einander haben. Da ich 37 Personen habe, gibt es insgesamt $36!$ Abstände.
Sei [mm] $P:=\{P_1,\cdots ,P_{37}\} \subset \IR^2$ [/mm] die Menge der 37 Personen in der Ebene und $d: P [mm] \times [/mm] P [mm] \to \IR, (P_i,P_j) \mapsto d(P_i,P_j)$ [/mm] die euklidische Metrik des [mm] $\IR^2$.
[/mm]
Nach Vorraussetzung ist für [mm] $i\neq [/mm] j: [mm] d(P_i,P_j) [/mm] > 0$ und alle möglichen Kombinationen der Abstände (bis auf die symmetrischen (2. Metrikaxiom)) sind verschieden. Ist dann [mm] $M:=\{d(P_i,P_j) : i\neq j, i,j = 1,2, \cdots 37\} \subset \IR$ [/mm] die Menge aller von Null verschiedenen Abstände, dann hat $M$ die Mächtigkeit $36!$.
Ferner gilt für $M$: $M$ ist endlich und beschränkt und besitzt ein Maximum und Minimum.
Also überlege folgendes Verfahren:
0. Schritt:
[mm] $\min [/mm] M$ ist ja nun der kleinste Abstand, den es in dieser Personengruppe gibt. O.B.d.A. sei [mm] $\min [/mm] M:= [mm] d(P_1,P_2)$, [/mm] also stellt sich [mm] $P_1$ $P_2$ [/mm] vor und umgekehrt.
1. Schritt:
Betrachte nun [mm] $M_1:= M\backslash \{d(P_1,P_2)\}$ [/mm] mit der Mächtigkeit $36!-1$. Wiederum ist [mm] $M_1$ [/mm] endlich und beschränkt und besitzt ein Minimum. Betrachte [mm] $\min [/mm] M := [mm] d(P_{1_i}, P_{1_j})$ [/mm] und überlege:
1. Fall [mm] $1_i [/mm] = 1$: Dann stellt sich [mm] $P_{1_j} P_1$ [/mm] vor.
2. Fall [mm] $1_i [/mm] = 2$: Dann stellt sich [mm] $P_{1_j} P_2$ [/mm] vor.
3. Fall [mm] $1_i \not\in \{1, 2\}: [/mm] P_ [mm] {1_j}$ [/mm] und [mm] $P_{i_j}$ [/mm] stellen sich vor.
Ok, das Verfahren ist klar. Denke aber, dass da irgendwo ein Denkfehler ist, denn so finde ich ja 37 Abstände, d.h. jeder stellt sich jedem vor.
Gruß,
Stefan
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:08 Sa 17.07.2004 | | Autor: | Marc |
Hallo Stefan und Lars,
ich hatte mir so etwas ähnliches überlegt, allerdings genau anders herum.
Und zwar betrachte ich zunächst den größten der kleinsten Abstände, die jede Person zu den anderen hat.
Es kann höchstens zwei Personen geben, die diesen größten kleinsten Abstand haben, da alle Abstände paarweise verschieden sind. Diese beiden Personen stellen sich gegenseitig vor, da sie ja keine nähere Person haben, der sie sich vorstellen könnten.
Diesen beiden Personen stellt sich aber auch niemand anderes vor, da alle anderen Personen einen kleineren kleinsten Abstand haben und somit keine der beiden Personen als Nächst-Stehenden haben können (sonst hätten diese beiden Personen ja einen kleineren kleinsten Abstand).
Falls aber nur eine Person diesen größten kleinsten Abstand hat, dann ist dies gleichzeitig die gesuchte, da sich ihr keiner vorstellt (alle anderen haben ja einen kleineren kleinsten Abstand und stellen sich jemand anderem vor).
Falls aber doch zwei Personen den größten kleinsten Abstand haben, dann stellen sie sich ja gegenseitig vor und ihnen wiederum kein anderer (s.o.). Deswegen betrachte ich einfach die restlichen 35 Personen und wende das obige Argument auf diese an, und induktiv dann auch auf ggfs. auf diese wieder. Schlimmstenfalls findet man so 18 Pärchen, die sich gegenseitig vorstellen -- 1 Person bleibt also selbst im "ungünstigsten" Fall übrig.
Zur zweiten Frage habe ich mir auch was überlegt, aber bis zum Ablauf der Fälligkeit habe ich ja noch etwas Zeit, das auch schön zu formulieren 
Viele Grüße,
Marc
|
|
|
| |
|
Gruß!
Ja, so geht es. 
Meine Lösung war so ähnlich, aber etwas anders: ich betrachte das Minimum ALLER vorkommenden Abstände. Dieses gehört zu 2 Personen A und B, die sich in jedem Fall einander vorstellen. Und dann gibt es 2 Fälle:
Fall 1:
Es gibt (mindestens) eine weitere Person C, die sich ebenfalls A oder B vorstellt. Dann aber hören entweder A oder B mindestens zwei Mal "Hallo!". Es gibt aber 37 Personen und es wird auch 37 Mal "Hallo!" gesagt, also muß einer leer ausgehen, wenn einer doppelt begrüßt wird. :)
Fall 2:
Niemand sonst stellt sich einem der beiden vor. Also schließen wir die beiden aus und gehen induktiv (wie oben gesagt) mit 35 Personen weiter vor.
Und weil 37 ungerade ist, muß das Verfahren abbrechen... entweder mit Fall 1 irgendwann oder einer Einzelperson.
Sehr gut! Der zweite Teil ist übrigens ein geometrisches Argument...
Lars
|
|
|
| |
|
Doch, genauso geht's. Du mußt Dir nur überlegen, dass Du im Fall 1 oder 2 fertig bist (weil dann eine Person mind. zweimal begrüßt wird und daher mindestens eine leer ausgehen muß) und sonst induktiv weitermachen. Ich habe das als Antwort auf Marcs Frage nochmal aufgeschrieben und danach erst gesehen, dass Du dasselbe hast.
Sehr gut! Fehlt nur noch der 2. Teil.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:40 So 18.07.2004 | | Autor: | Clemens |
Hallo!
Ich versuche mich mal am zweiten Teil.
Wenn sich einer Person P sechs oder mehr Personen (P1 bis Pn) vorstellen würden, so fänden sich zwei Personen (o. B. d. A.) P1 und P2, für die der Winkel alpha zwischen den Strecken P-P1 und P-P2 kleiner/gleich als Pi/3 ist (Muss man das noch beweisen, oder ist das allen klar?).
Es seien jetzt beta der Winkel zwischen den Strecken P-P2 und P1-P2 und gamma der Winkel zwischen den Strecken P-P1 und P1-P2. Dann gilt (Sinussatz):
|P1-P2|/sin(alpha) = |P-P1|/sin(beta) = |P-P2|/sin(gamma)
1. Fall
alpha = Pi/3. Dann ist entweder beta = gamma = Pi/3, womit es sich um ein gleichseitiges Dreieck handeln würde und der Abstand zwischen den Personen nicht mehr paarweise verschieden ist oder beta != Pi/3 und gamma != Pi/3. Dann gilt aber beta > Pi/3 oder gamma > Pi/3. Sei nun o. B. d. A. beta > Pi/3:
|P1-P2| = [sin(alpha)/sin(beta)]*|P-P1|
Der Vorfaktor sin(alpha)/sin(beta) ist kleiner 1 (alpha < beta) und damit ist |P1-P2| < |P-P1|. Dann würde P1 aber nicht zu P "Hallo, mein Freund" rufen, sondern zu P2.
2. Fall
alpha < Pi/3. Dann findet sich auch beta > Pi/3 oder gamma > Pi/3
Gruß Clemens
|
|
|
| |
|
Sorry, dass es so lange gedauert hat.
Ja, genau so ist es. Das ist etwas ähnliches wie eine kristallographische Bedingung: wie Du gesagt hast, bei einem Winkel von [mm] \frac{\pi}{3}[/mm] entstehen gleichseitige Dreiecke, was in dieser Aufgabe verboten ist und bei einem kleineren Winkel begrüßen sich die anderen Personen lieber untereinander.
Sehr gut, alles geklärt. :)
Lars
|
|
|
|
