grade Anzhl Beknnter auf Party < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:57 Do 18.10.2007 | | Autor: | kickin |
| Aufgabe | | Auf einer Party der Erstsemester befindet sich eine angehende Mathematikerin. Sie stellt fest, dass die Anzahl der Anwesenden ungerade ist. Daraufhin verkündet sie stolz, dass es wenigstens einen Partygast gibt, der genau eine gerade Anzahl von Anwesenden der Party kennt. Versuchen Sie diese Aussage zu beweisen. Formulieren Sie zuerst ein mathematisches Modell der Situation. |
Moinsen,
weiß gar nicht ob ich hier richtig bin. Und es ist auch nicht wirklich schwere und irgendwie höhere Mathematik. Aber da ich diese in einer Vorlesung auf der Uni bekommen habe, dachte ich, ich poste sie in diesem Forum.
Was ich mir dazu gedacht habe: Es gibt offensichtlich keine Verbindung zwischen den Gästen und dem Grad der Bekanntschaft zwischen ihnen. Da viel mir z.B. ein Gegenbeispiel ein: In einem Zug sitzen 19 Leute (ungerade Anzahl Anwesender). Warum muss denn mind. 1 eine gerade Zahl (also mind. 2!) kennen. Wer will mir das denn beweisen?
Daher würde ich sagen, dass man die Aussage nur beweisen kann, wenn man davon ausgeht, dass sie selbst eine gerade Anzahl von Personen kennt, oder? Dann würde die Aussage passen, dass mind. 1 Person eine gerade Anzahl Gäste kennt!?
Mir würde es schonmal super weiterhelfen, wenn mir jemand sagen könnte, ob ich damit richtig liege, oder ob ich irgendwas wichtiges nicht berücksichtigt habe. Und zweitens fänd ich es super, wenn mir jemand einen Tipp geben könnte, wie ich das Mathematsiche Modell formulieren könnte. Bin im 1. Semster und möchte das schon gerne alleine schaffen. Also ein Tipp für die richtige Richtung wäre super.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Gruß
Kickin
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:34 Do 18.10.2007 | | Autor: | leduart |
Hallo kickin
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
ich hab zwar die Lösung noch nicht, aber 0 ist in diesem Zusammenhang auch ne grade Zahl, und 1 ne ungerade.
Also wenn sich alle nicht kennen bist du fertig.
also wirds erst interessant, wenn es keinen gibt der 0 kennt.
Am einfachsten fängt man mit der kleinsten Zahl die interessant ist an. 3 A,B,C einer mindestens kennt einen Also A kennt B =B kennt A. entweder kennt C weder A noch B als0 0 fertig, oder er kennt A oder B, nimm an A dann kennt A B und C.
Weiter hab ich noch nicht überlegt.
Gruss leduart
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:12 Fr 19.10.2007 | | Autor: | Walty |
Ich würde evtl das Pferd von hinten aufzäumen und versuchen die Aussage zu falsifizieren...
Behauptung: ungerade Anzahl Leute => mindestens eine Person kennt 0,2,4.... andere
Gegenbehauptung: alle kennen nur ungerade viele Leute
und dann hingehen und ein Modell aufstellen, wieviele Beziehungen der Einzelne hat unter der Prämisse es gibt niemanden der keinen kennt und alle haben nur eine ungerade Anzahl von Beziehungen
wenn man das richtig macht muss man zu dem Schluss kommen können, es bleibt immer einer übrig der entweder keinen oder 2 oder 4 ... kennt...
beispiel;(trivial) jeder kennt 1 => paarbildung; dann bleibt am Ende einer übrig, der keinen kennt
Maximale Anzahl der Kontakte =n-2 (n ungerade)
mal systematishc aufschreiben:
Anzahl 1: Sonderfall 1 kennt 0
Anzahl 3: jeder kann max 1 kennen (2 ist gerade ;) ) -bleibt 1 übrig der 0 kennt
Anzahl 5: 2 neue unverbundene Knoten (insgesamt 3)
die können aber nicht (siehe vorher) eine ungeraden Anzahl von Verbindungen haben, ohne einen der bereits vernetzten knoten miteinzubeziehen, was dessen Verbindungszahl um 1 erhöhen und somit 'gerade' machen würde
Zeichnet sich hier eine vollständige Induktion ab?
es ist mir zu spät, um dass jetzt noch auzuarbeiten...
hth
Gruß Walty
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:37 Fr 19.10.2007 | | Autor: | rainerS |
Hallo Kickin,
ich glaube, es läuft auf die Aufteilung der Anwesenden in Gruppen auf.
Nimm irgendeinen Anwesenden A. Dazu gibt es eine Gruppe von Leuten, die er kennt, und die Gruppe von Leuten, die er nicht kennt. Beide Gruppen haben entweder gerade Anzahl oder beide eine ungerade Anzahl von Mitgliedern (weil A + 1.Gruppe + 2.Gruppe = ungerade).
Entweder die erste Gruppe hat eine gerade Anzahl, dann ist die Aussage wahr. Fertig.
Oder sie hat eine ungerade Anzahl. Dann nehmen wir die zweite Gruppe (die A nicht kennen) und wenden das gleiche Argument wieder an: greife irgendeine Mitglied B heraus und teile die restlichen Mitglieder auf in die, die B kennen, und die, die B nicht kennen.
Dies wiederholen wir solange, bis entweder die beiden Gruppen gerade Anzahl haben, oder in der 2. Gruppe nur noch ein Partyteilnehmer ist. Das funktioniert, weil in jedem Schritt die Gruppen kleiner werden, wir also in endlich vielen Schritten zum Ende kommen.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:08 Fr 19.10.2007 | | Autor: | kickin |
Hallo ihrs!
Vielen lieben Dank für die schnellen Antworten. Habe jetzt das Problem verstanden. Aber mir ist folgendes noch nicht ganz klar:
Warum kann ich die Gruppe der Bekannten von Person a unberücksichtig lassen, wenn ich mir die weiteren Gruppen angucke? Kann nicht sein, dass jemand aus der 2. Gruppe (Rest - nicht bekannt mit a) eine Bekanntschaft zu jemanden aus der 1. Gruppe hat? Gut - in diesem Fall hätte die Personen (aus der 1. Gruppe) zwei Bekanntschaften (wieder gerade)! Aber angenommen 2 Personen aus der zweiten Gruppe, haben auch Kontakt zu einer Person aus der 1. Gruppe?
Ich weiß, dass es im endeffekt trotzdem aufgeht, aber kann ich das so begründen wie im Beitrag zuvor, oder muss ich diesen Fall auch berücksichtigen? Oder: Wie kann ich begründen, dass ich diesen Fall nicht berücksichtigen muss? Stehe da so ein bisschen aufem Schlauch.
Gruß
Jörg
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:00 Fr 19.10.2007 | | Autor: | leduart |
Hallo
Aus rainers post get wirklich nicht so einfach hervor, warum die Zahl kleiner wird.
Ich denk du kannst das mit Induktion machen.
fang mit 1 an, klar
es kommen 2 dazu.... wieder klar.
Nimm an du weisst es für irgend ne Anzahl von Gästen dass es stimmt. 2 neue kommen dazu. dann zeig, dass es weiter gilt.
Mathematisches Modell wären etwa eine ungerade Anzaahl von Punkten in der Ebene. und mögliche Verbindungen, dann heisst es :mindestens 1 Punkt hat ne grade Anzahl von Verbindungen zu anderen.
Das kannst du auch gut zeichnen, und daran nen Lösungsweg suchen.
Gruss leduart
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:18 Sa 20.10.2007 | | Autor: | rainerS |
Hallo!
> Ich weiß, dass es im endeffekt trotzdem aufgeht, aber kann
> ich das so begründen wie im Beitrag zuvor, oder muss ich
> diesen Fall auch berücksichtigen? Oder: Wie kann ich
> begründen, dass ich diesen Fall nicht berücksichtigen muss?
> Stehe da so ein bisschen aufem Schlauch.
Nein, du hast recht; ich habe das Problem nicht ausreichend durchdacht - es war offensichtlich zu spät am Abend.
Ich glaube, der Ansatz ist möglich, erfordert aber weitere Fallunterscheidungen.
Rabilein1 hat eine viel schönere Lösungsmethode geliefert.
Viele Grüße
Rainer
|
|
|
| |
|
> Sie stellt fest, dass die Anzahl der Anwesenden ungerade ist.
> ... dass es wenigstens einen Partygast gibt, der genau eine
> gerade Anzahl von Anwesenden der Party kennt.
Folgendes Modell:
1) Ungerade Zahl von Anwesenden
2a) Gerade Anzahl von Bekannten = MINUS
2b) Am Anfang kennt keiner keinen. Jeder bekommt ein MINUS
3) Man multipliziert alle Minusse. (wie bekannt: Minus mal Minus ist Plus)
4) Wegen Ungerade Zahl von Anwesenden ist das Produkt MINUS
5) Wenn zwei sich kennen, dreht sich deren Vorzeichen um (bei beiden)
6) Resultat: Das Produkt ist stets MINUS - und das heißt: es gibt mindestens einen mit gerader Anzahl von Bekannten (siehe 2a).
|
|
|
|
