Röhrenpost < Kombinatorik < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:59 Di 16.10.2012 | | Autor: | sazzi |
| Aufgabe | Ein Ort will mehrere Häuser mit einem Röhrenpostsystem ausstatten. Jedes Haus kann nur N Zu-/Ableitungen besitzen (Briefe können pro Röhre in beide Richtungen verschickt werden).
Jedes Haus kann nur N Nachbarn direkt eine Nachricht schicken. Wenn eine Nachricht zwischen 2 Häusern verschickt wird, welche nicht direkt benachbart sind, soll diese über möglichst wenige andere Häuser weitergeleitet werden.
Aufgabe A:
N=3, Anz.Häuser=6
Überprüfe über wie viele Stationen ein Brief verschickt werden muss um alle Nachbarn zu erreichen! Wie viele Station sind bei geschickter Anordnung maximal nötig um Briefverkehr zwischen allen Häusern sicher zu stellen?
Aufgabe B:
Finde eine allgemeine Formel für N direkte Nachbarn und K Häuser! Beweise! |
A: Lösung:
1-2-3-4-5-6 : schlechte Anordnung (N=2):
längste Verbindung: Weiterleitung über 4 Häuser wenn 1 <-> 6 eine Nachricht schicken will.
Gute Anordnung
1 - 2
/ \ / \
3----X----4
\ / \ /
5 - 6
längste Verbindung 2; Weiterleitung über max. ein anderes Haus: Z.B. wenn 1 <-> 5 eine Nachricht schickt, dann Weiterleitung über 3 oder 6.
-> Bis hierhin ist es einfach :D
-> aber B ?? Wie kann man denn daraus eine Formel ableiten? Wie beweist man denn so etwas?
Hiiiilfe ;)
(Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.)
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:05 Di 16.10.2012 | | Autor: | Diophant |
Hallo sazzi und
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
Könntest du uns der Form halber noch sagen, wo genau diese Aufgabe herstammt? Vielen Dank!
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:04 Do 18.10.2012 | | Autor: | sazzi |
Ja das kann ich.
Unser Mathematiklehrer hat sie uns gestellt :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:18 Do 18.10.2012 | | Autor: | Diophant |
Hallo sazzi,
> Ja das kann ich.
> Unser Mathematiklehrer hat sie uns gestellt :)
ok, ich habe die bisher gegebene Antwort wieder entschlüsselt. Ich bitte um Verständnis für meine Vorgehensweise: solche Kombinatorik-Aufgaben könnten Wettbewerbsaufgaben zu einem laufenden Wettbewerb sein; und es ist hier streng untersagt (wie anderswo auch), solche Aufgaben zu diskutieren.
Hat euer Lehrer denn etwas zu der Herkunft der Aufgabe gesagt, denn eine ganz gewöhnliche Schulbuchaufgabe scheint mir das denn doch auch nicht zu sein?
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:20 Di 23.10.2012 | | Autor: | sazzi |
er meinte : " Hier, da könnt ihr in den Ferien (noch 2 Wochen), ein bisschen drauf herum beißen." Wo er die her hat weiß ich wirklich nicht.
Danke für die Hilfe
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:43 Di 16.10.2012 | | Autor: | pits |
Hallo sazzi,
ich denke man muss erst mal eine Strategie entwickeln, wie man die Häuser geschickt anordnet um dann mit Hilfe eines Systems eine Formel zu entwickeln.
Ich würde dazu für feste Häuserzahlen K mal durchgehen, wie sich die Weglängen entwickeln, so z.B. wie das für 6 Häuser gemacht worden ist.
K=6:
Bei N=2 ist 1-2-3-4-5-6-1 eine gute Kombination, oder auch die einzige  , der längste Weg ist von 1 nach 4 (bzw 2 nach 5 usw.)
Falls ich N=3 wähle kann ich die Wege optimieren, da würde ich dann 1 mit 4 verbinden usw., der Längste Weg ist dann von 1 nach 3 und ähnlich.
Bei N=4 gibt es immer noch ein Haus, das nicht direkt benachbart ist
Bei N=5 ist alles klar.
Das würde ich jetzt für mehrer Hausanzahlen ausprobieren und nach einem System ausschau halten.
Für N=2 ist die maximale Weglänge bei jedem K leicht zu ermitteln.
Für N=K-1 auch, K-2 wahrscheinich auch.
Viel Erfolg
pits
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 14:23 Di 23.10.2012 | | Autor: | sazzi |
Ja das habe ich gemacht. Bei N=10 und k=3 z.B. wird es aber schon recht unübersichtlich. Außerdem bin ich mir bei meinen Zeichnungen nicht schlüssig ob ich nicht eine bessere Anordnung übersehen habe.
Außerdem verstehe ich nicht wie man das beweist.
Vielen Dank noch einmal für die Hilfe
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:20 Do 25.10.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:47 Fr 26.10.2012 | | Autor: | sazzi |
Ich weiß nicht warum die Zeit abgelaufen ist. Nächste Woche sind auch noch Ferien. Ich hätte die Antwort zu gern bei Mitte übernächster Woche.
Danke schön
|
|
|
|
