Archiv verlassen und diese Seite im Standarddesign anzeigen : "lustige" Matheaufgabe
Ich habe hier eine nette Kombinatorikaufgabe die man ohne viel rechnen lösen kann, die Frage ist wie gut man das kann :)
Acht Studierende haben sich zu einer Arbeitsgruppe zusammengeschlossen. Jeder Studierende löst genau eine der jeweils acht Aufgaben und übernimmt die Ergebnisse der sieben anderen Aufgaben von seinen Kommilitonen. Die Studierenden tauschen die Ergebnisse jeweils am Tag vor der Hausaufgabenabgabe telefonisch aus. Geben sie ein effizientes Kommunikationsmodell an.
Nun, die Frage bleibt was Frau Prof. sich mit "effizient" vorstellt. Ich nehme an sie bezieht sich auf die Anzahl der Anrufe, wobei man noch einschließen könnte das die Telefongebühren für den Einzelnen noch minimal sind, aber das lassen wir mal...
auf was für Lösungen kommt ihr so?
2 Leute: 1 Anruf
3 Leute: 3 Anrufe
4 Leute: 4 Anrufe
5 Leute: komm gerade nicht unter 7
8 Leute: bin ich bei 15
wer unterbietet mich? Und ich merke das die 3 Mon. Ferien meinem Gehirn eher geschadet haben
Gruss
boxleitnerb
2010-10-25, 15:48:32
x Leute, ein Anruf...Telefonkonferenz ;D
Reaktion meiner Professorin wäre dann ein beliebiges "I see what you did there"-Bild ;)
MiamiNice
2010-10-25, 15:50:44
Ich komme für 8 Leute auf 14 Anrufe oder Konferrenzschaltung ^^
KakYo
2010-10-25, 15:52:17
8 Leute: 14 Anrufe
Personen A-G rufen jeweils Person H an. Person H sammelt die Ergebnisse un druft dann die Personen A-G zurück...einer is halt der Arsch
wieso habe ich 15 hingeschrieben? Ich habe 12
Simon Moon
2010-10-25, 15:56:28
8 Leute: 14 Anrufe
Personen A-G rufen jeweils Person H an. Person H sammelt die Ergebnisse un druft dann die Personen A-G zurück...einer is halt der Arsch
Statt dass er nach G wieder bei A anfängt, könnte er G auch gleich die Resultate mitteilen -> 13 Anrufe.
MiamiNice
2010-10-25, 16:03:25
wieso habe ich 15 hingeschrieben? Ich habe 12
Die 12 konnte ich nachvollziehen, aber mehr ist glaub ich nicht drin.
Azubi
2010-10-25, 16:05:25
1. Student (Ergebnis) telefoniert mit 2. Student (braucht Ergebnis 1)
2. Student (Ergebnis 1+2) telefoniert mit 3. Student (braucht Ergebnis 1+2)
3. Student (Ergebnis 1+2+3) telefoniert mit 4. Student (braucht Ergebnis 1+2+3)
...
...
7. Student (Ergebnis 1+2+3+4+5+6) telefoniert mit 8. Student (braucht Ergebnis 1+2+3+4+5+6+7)
8. Student hat Ergebnis 1+2+3+4+5+6+7+8 (braucht nicht zu telefonieren)
also 7 Anrufe :D
MiamiNice
2010-10-25, 16:06:47
Und wie kommt Student 1 an die Ergebnisse von z.b. Student 8? :tongue:
Azubi
2010-10-25, 16:08:49
Und wie kommt Student 1 an die Ergebnisse von z.b. Student 8? :tongue:
SMS? :freak:
daflow
2010-10-25, 16:10:30
13 ;( Okili jetz au 12 ;)
MiamiNice
2010-10-25, 16:10:48
SMS? :freak:
Reaktion meiner Professorin wäre dann ein beliebiges "I see what you did there"-Bild ;)
:biggrin:
mich interessiert jetzt viel eher die dadurch entstehende Zahlenfolge (im Internet gibt es einen Folgenscanner :) der durch die Eingabe von Gliedern alle bekannten Folgen ausspuckt)
ich glaube auch nicht das man die 12 drücken kann. Aber wie beweist man das?
Pinoccio
2010-10-25, 16:35:31
Sieht das nicht wie (d)ein Telefonplan aus?
http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/images/figure8.gif
Jedes Kreuz ist ein Gespräch ...
mfg
Azubi
2010-10-25, 16:37:09
mich interessiert jetzt viel eher die dadurch entstehende Zahlenfolge (im Internet gibt es einen Folgenscanner :) der durch die Eingabe von Gliedern alle bekannten Folgen ausspuckt)
ich glaube auch nicht das man die 12 drücken kann. Aber wie beweist man das?
Verdammt, wie kommst du auf 12??? Ich rechne und rechne und komme nur auf 13. :confused:
... und das auch nur wenn Student 7 solange am Hörer bleibt bis Student 8 die Lösung hat. Dann haben bereits 7+8 alle Lösungen. Sonst komme ich auf 14 Anrufe. :freak:
MiamiNice
2010-10-25, 16:40:26
Verdammt, wie kommst du auf 12??? Ich rechne und rechne und komme nur auf 13. :confused:
http://www.abload.de/thumb/img_0517ji33.jpg (http://www.abload.de/image.php?img=img_0517ji33.jpg)
Auf die schnelle.
Jedes Kreuz ist ein Gespräch ...
ist das irgendein Lattice-Filter?
Verdammt, wie kommst du auf 12??? Ich rechne und rechne und komme nur auf 13.
am Besten mit was Kleinem probieren
mit 4 Leuten
1->2
3->4
2->3
4->1
da hat auch jeder die gleichen Tel.-kosten :)
bei 8 Leuten machen 2 disjunkte Hälften Obiges
Und dann tauschen sich die beiden Hälften mit 4 Anrufen aus
Pinoccio
2010-10-25, 16:44:08
Das ist eine FFT. >< (http://www.google.de/images?um=1&hl=de&client=firefox-a&rls=org.mozilla%3Ade%3Aofficial&tbs=isch%3A1&sa=1&q=fft+butterfly&aq=f&aqi=&aql=&oq=&gs_rfai=)
@pest: Brauchst auch eine Beweisidee für Mimimalität?
/edit: deine Schilderung (mit der Rekursion (http://blog.niveaufrei.de/wp-content/uploads/2009/07/google-rekursion-rekursion.png)) zeigt sie schon auf.
mfg
für N als Zweierpotenz kann man das rekursiv zeigen, aber sonst wird es hässlich..imo
also ja ich brauche eine Beweisidee ;)
Crop Circle
2010-10-25, 16:49:03
Das ist eine FFT. >< (http://www.google.de/images?um=1&hl=de&client=firefox-a&rls=org.mozilla%3Ade%3Aofficial&tbs=isch%3A1&sa=1&q=fft+butterfly&aq=f&aqi=&aql=&oq=&gs_rfai=)
Und wie kommt man damit zur Faltung?
obwohl es reicht ja hier das ganze für 2^p zu zeigen, macht einen Teile&Herrsche-Ansatz und fängt bei 2 an :)
Pinoccio
2010-10-25, 17:16:25
obwohl es reicht ja hier das ganze für 2^p zu zeigen, macht einen Teile&Herrsche-Ansatz und fängt bei 2 an :):biggrin:Und wie kommt man damit zur Faltung?Hä?
mfg
Crop Circle
2010-10-25, 17:20:38
Na du meinst doch fast fourier transformation, oder nicht? -> Faltungstheorem.
Azubi
2010-10-25, 17:20:54
ist das irgendein Lattice-Filter?
am Besten mit was Kleinem probieren
mit 4 Leuten
1->2
3->4
2->3
4->1
okay, ich hab es jetzt auch
vier 2x und vier 1x
1-8
2-7
3-6
4-5
8-2
7-1
6-4
5-3
1-3
2-4
5-7
6-8
da hat auch jeder die gleichen Tel.-kosten :)
Ich krieg das nicht hin. Ich komme zwar jetzt auch auf 12 Anrufe aber ich schaffe es nicht es so zu optimieren das jeder mindestens 1x anruft. :mad:
Mein bestes Ergebnis ist immer
ein Student ruft 3x an
drei Studenten rufen 2x an
drei Studenten rufen 1x an
ein Sudent ruft 0x an
Das mit den gleichen Telefonkosten haut bei 12 Anrufen ja eh nicht hin. Aber das zumindest jeder mindestens einen Anruf macht müßte doch gehen. Ich kriege das nicht hin. :confused:
Pinoccio
2010-10-25, 17:28:06
Ich krieg das nicht hin. Ich komme zwar jetzt auch auf 12 Anrufe aber ich schaffe es nicht es so zu optimieren das jeder mindestens 1x anruft. :mad:
Das mit den gleichen Telefonkosten haut bei 12 Anrufen ja eh nicht hin. Aber das zumindest jeder mindestens einen Anruf macht müßte doch gehen. Ich kriege das nicht hin. :confused:Schau dir "meine" Skizze (http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/images/figure8.gif) an. In Stage 1 rufen an: 2, 3, 4 und 5, in Stage 2 die vier restlichen.Na du meinst doch fast fourier transformation, oder nicht? -> Faltungstheorem.Ja, aber was hat das mit dem Thema zu tun?
mfg
Azubi
2010-10-25, 17:36:59
Schau dir "meine" Skizze (http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/images/figure8.gif) an. In Stage 1 rufen an: 2, 3, 4 und 5, in Stage 2 die vier restlichen.Ja, aber was hat das mit dem Thema zu tun?
mfg
Ah, nun hab ich es :biggrin:
vier rufen 2x an und vier rufen 1x an
1->8
2->7
3->6
4->5
8->2
7->1
6->4
5->3
1->3
2->4
5->7
6->8
Coole Aufgabe. Das ist was für den nächsten Frühschoppen am Sonntag. :D
aber ich schaffe es nicht es so zu optimieren das jeder mindestens 1x anruft.
du hast doch meine Liste für 4 Leute
da gibts ja noch 4 andere Leute, für die machst du auch so eine Liste, also auf jede Zahl 4 draufaddieren->jeder ruft einmal an
bei den letzten 4 Anrufen haben halt 4 Glück
Coole Aufgabe.
nicht wenn du seit 9 Semestern Mathe studierst
Azubi
2010-10-25, 17:50:32
nicht wenn du seit 9 Semestern Mathe studierst
Ich hatte den falschen Ansatz. Ich hatte es binär gelöst.
1. Student 0 0 0 0
2. Student 1 0 0 0
3. Student 0 1 0 0
4. Student 1 1 0 0
5. Student 0 0 1 0
6. Student 1 0 1 0
7. Student 0 1 1 0
8. Student 1 1 1 0
Die Summe der 1ser ergibt 12 nötige Anrufe. Aber der 1. Student hatte immer 0 Anrufe. :freak:
Da kam ich halt immer auf
1 x 0 Anrufe
3 x 1 Anrufe
3 x 2 Anrufe
1 x 3 Anrufe
was ich nicht verstehe ist Folgendes
für n=2^p ergibt sich ja folgendes Schema
2: 1
4: 2+2
8: 4+4+4
16: 8+8+8+8
32: 16+16+16+16+16
usw
wenn ich die Zahlen jetzt bei OEIS (http://www.research.att.com/~njas/sequences/) eingebe findet er nix
gebe ich dagegen nur "1,4,12,36" ein kommt als zweiter Beitrag "Number of n-step self-avoiding walks on square lattice." was imo genau das ist was ich suche :? aber für p=5 kommt ja nicht 100 raus
FireFrog
2010-10-25, 17:59:25
Also ich hab das einfach so gerechnet,
7 Studenten rufen Nummer 8 an und sagen ihm ihre Ergebnisse
= 7 Anrufe nun legen die auf und rufen (30 Minuten später) nochmal Nummer 8 an und lassen sich die Lösungen sagen, da Nummer 8 aber bereits vor der zweiten Telefonreihe alle Ergebnisse weiß braucht Nummer 7 nur 1 x anzurufen, um alle Ergebnisse zu bekommen daher wäre ich persönlich bei 13 Anrufen.
Die wechseln sich dann halt jede Woche immer ab.
Pinoccio
2010-10-25, 18:18:20
was ich nicht verstehe ist Folgendes
für n=2^p ergibt sich ja folgendes Schema
2: 1
4: 2+2
8: 4+4+4
16: 8+8+8+8
32: 16+16+16+16+16
usw
wenn ich die Zahlen jetzt bei OEIS (http://www.research.att.com/~njas/sequences/) eingebe findet er nix
gebe ich dagegen nur "1,4,12,36" ein kommt als zweiter Beitrag "Number of n-step self-avoiding walks on square lattice." was imo genau das ist was ich suche :? aber für p=5 kommt ja nicht 100 rausDu suchst A001787 (http://www.research.att.com/~njas/sequences/A001787).
/edit: Die auch Azubis Lösung enthält, dort formuliert als Number of zeros in all different (n+1)-bit integers
mfg
Gnafoo
2010-10-25, 18:25:53
Wenn die Studenten 2-7 jeweils zwei Telefone haben, kann man mit 7 Anrufen einen Bus aufbauen und alle notwendigen Daten per Stille Post austauschen :freak:.
Pro Zweiergespräch kann die Zahl der bekannten Lösungen bestenfalls verdoppelt werden. Das ist bei Pinoccios Schema immer der Fall. Demzufolge kann man nicht schneller ans Ziel kommen, weil bei Pino jedes Gepräch die größtmögliche Informationsvermehrung bietet.
Du suchst A001787 (http://www.research.att.com/~njas/sequences/A001787).
/edit: Die auch Azubis Lösung enthält, dort formuliert als Number of zeros in all different (n+1)-bit integers
mfg
ah danke mir gefällt aber anz. der kanten des n-dim würfels besser :)
das passt dann auch zum stoff (irgendwas mit geometrie :wink:)
Pinoccio
2010-10-25, 19:09:30
Wenn die Studenten 2-7 jeweils zwei Telefone haben, kann man mit 7 Anrufen einen Bus aufbauen und alle notwendigen Daten per Stille Post austauschen :freak:.Hardwareforen ... :hammer:Pro Zweiergespräch kann die Zahl der bekannten Lösungen bestenfalls verdoppelt werden. Das ist bei Pinoccios Schema immer der Fall. Demzufolge kann man nicht schneller ans Ziel kommen, weil bei Pino jedes Gepräch die größtmögliche Informationsvermehrung bietet.Elegante Begründung. :smile:ah danke mir gefällt aber anz. der kanten des n-dim würfels besserMir ist leider nicht klar, warum ein Würfel ein gutes (d. h. insb. zielführendes) Modell für das Ausgangsproblem ist. :confused:
Anzahl der Studenten=Dimension ist dann doch irgendwie unanschaulich.
mfg
ja sinnvoll ist das nicht, aber das Fach heißt Kombinatorik und wir behandeln gerade Affine Ebenen und ich kann da leider keinen Zusammenhang herstellen.
Mit Informationsvermehrung oder Dualzahlen brauche ich da garnicht ankommen.
BeetleatWar1977
2010-10-25, 19:39:16
mal überlegen:
1. 1-2
2. 2-3
3. 3-4
4. 4-5
5. 5-6
6. 7-8
7. 8-1
8. 7-6
9. 6-5
10. 5-4
11. 4-3
12. 3-2
oder
1. 1-2
2. 8-7
3. 2-3
4. 7-6
5. 3-4
6. 6-5
7. 4-5
8. 4-3
9. 5-6
10. 3-2
11. 6-7
12. 2-1
13. 7-8
verdammt :freak:
also auf weniger wie 12 komm ich net^^
Anzahl der Studenten=Dimension
wenn, dann Anzahl der Knoten=Anzahl der Studenten (also hier Dimension 3)
da kann man auch einen Zusammenhang zu Binomialkoeffizienten herstellen,
oder den Knoten Binärzahlen geben die den Hammingabstand zum Ursprung darstellen womit wir wieder beim Ursprünglichen sind
doch irgendwie unanschaulich.
das macht nix, hier sind auch sich anschaulich schneidende Geraden parallel :wink:
vBulletin®, Copyright ©2000-2024, Jelsoft Enterprises Ltd.