matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenMathematik-WettbewerbeDer große Empfang
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Mathematik-Wettbewerbe" - Der große Empfang
Der große Empfang < Wettbewerbe < Schule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Mathematik-Wettbewerbe"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Der große Empfang: Übungsaufgabe
Status: (Übungsaufgabe) Übungsaufgabe Status 
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

        
Bezug
Der große Empfang: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

Bezug
                
Bezug
Der große Empfang: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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


Bezug
                        
Bezug
Der große Empfang: Antwort
Status: (Antwort) fertig Status 
Datum: 15:40 So 18.07.2004
Autor: Gnometech

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

Bezug
                
Bezug
Der große Empfang: Antwort
Status: (Antwort) fertig Status 
Datum: 15:42 So 18.07.2004
Autor: Gnometech

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.

Bezug
                        
Bezug
Der große Empfang: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

Bezug
                                
Bezug
Der große Empfang: Antwort
Status: (Antwort) fertig Status 
Datum: 10:01 Mi 21.07.2004
Autor: Gnometech

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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Mathematik-Wettbewerbe"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]