Mathematische Knobelaufgabe

durchschnittlich....

ein buschmann im urwald wird sicher viele viele viele ecken brauchen, wäredn wir höchst kommunikativen menschen hier sicher nur wenige ecken brauchen....


weiterhin ist hier die definition von kennen zu vereinfachen! kenne bedeutet in dem fall in irgendeiner form mit irgendwem in interaktion getreten zu sein also auch icq usw

Wombat's Lösungsansatz ist doch gut. Man könnte natürlich der Einfachheit halber nur die Leute von Stufe 6 berechnen, womit die Berechnung des Wertes auf die 6te Wurzel aus 6,4 Milliarden zurückzuführen ist. Wombat's Ansatz bezieht aber alle Menschen mit ein, die ich auf dem Weg dorthin schon kennengelernt habe. Allerdings beträgt x^5 bei x=43 lediglich nur etwas mehr als 2% von x^6 (x^5 ist 1/43 von x^6), so daß man diese Potenzen im Zuge einer Überschlagsrechnung vernachlässigen kann. Will man es aber ganz genau haben, müsste man sie ausrechnen. Zudem nimmt deren Gewicht für kleinere x zu

Interessant ist das ganze in zweierlei Hinsicht:
1. Wenn ich mich nur in Dresden bewege, wieviel Ecken brauche ich um alle zu kennen?
2. Wie komm ich am schnellsten mit demjenigen, mit dem ich es wünsche, in Kontakt?

Und was noch die Frage ist, kenn ich meine direkten Freunde über 0 oder über 1 Ecke? D.h. habe ich zwischen allen Personen der Welt und mir 5 oder 6 "Hops"?

Mir fiel heute nacht ein, dass die Bedingung "Jeder kennt nur X Leute" mit dem Ansatz deshalb nicht erfüllt ist, weil die Beziehungsecke aus der eine Person gekannt wird mitgezählt werden muss.
D.h. der Lösungsweg bleibt richtig, jeder muss 43 neue Personen kennen zzgl. zu der Person über welche sie gekannt wird. Dann muss ich nur 43 kennen, alle nach mir kennen dann aber 44.

mathematisch wird aus:

x^0 + x^1 + x^2 + x^3 + x^4 + x^5 + x^6 = 6,4 Mrd.

Lösung: x= 42,9197231

dann: x^0 + (x^1-x^0) + (x^2-x^1) + (x^3-x^2) + (x^4-x^3) + (x^5-x^4) + (x^6-x^5) = 6,4 Mrd

das kann man durch scharf hinguggen vereinfachen zu

x^6 = 6,4 Mrd

Lösung: x= 43,0886938


hab ich mir jetzt so gedacht ...

und jeder von uns weiss, was jetzt als naechstes passiert.
die ankunft des grossen weissen taschentuchs! wir sind eindeutig zuviele leute, denn die korrekte und unabdingbar vernuenftige sowie einzig moegliche antwort waere

42

gewesen.

mfg, unikat

yo, dann müssen wir aber die Telefondesinfizierer & Co. in ein Raumschiff packen und deportieren ....

@Socres: um solche Definitionen kümmert man sich in der Mathematik nicht.

@Chris: nach der These nach sind es - weltweit - maximal 6 Ecken.

@mArVinTheRobot: Du hälst den Finger auf die richtige Stelle. Aber lies dir noch einmal die Annahmen durch!

@unicum: Die USA versucht doch regelmäßig Maßnahmen, um wieder auf die 42 zu kommen ;-)

@rene: die frage war nicht, nach wie vielen Ecken ich eine Person kenne, sondern, ob ich meine direkten Freunde über eine Ecke kenne, oder ob die Freunde meiner direkten Freunde über eine Ecke mit mir bekannt sind.

also ich würd mal sagen, ihr habt die aufgabenstellung nicht richtig gelesen. über sechs ecken jemanden zu kennen, würde für mich erstmal heissen, dass ich sechs mittelsmänner habe, dass heisst, ich kenne jemanden über sieben kanten. (fuchs hat das problem schon indirekt angesprochen)

mit wommes lösungsansatz (den, den ich für richtig halte)
1+x+x^2+x^3+x+4+x^5+x^6+x^7 = 6.4e9
wobei x^1 bis x^6 die mittelsmänner wären (baumstruktur) komme ich auf 25,02... freunde.

viel interessanter ist das problem allerdings, wenn man diese eigenschaft für jeden erdenbewohner haben möchte. dann geht das nämlich mit dem konstruierten baum nicht mehr.
die effizienteste struktur, um soetwas zu realisieren, ist ein hypercube. ein hypercube ist zwar ein schönes modell, es hat aber den nachteil, dass die anzahl der freunde und die der längste pfad zum nachbarn (in kanten gemessen) immer gleich sein muss. die anzahl der elemente im hypercube sind 2^anzahl der freunde. log2(6.4e9) = 32,57...

fine. als braucht jeder erstmal rund 33 freunde und kennt jeden über32 ecken.

nun können wir aber unseren hypercube verändern, indem wir sagen, wir kennen nicht nur unsere nachbarn, sondern auch noch den am weitesten entfernten menschen (diagonale). ich brauch also nur noch die nächstganzzahligehälfte des weges und habe einen freund mehr. (kann sich jeder an einem quadrat und einem würfel veranschaulichen) wenn wir das fortführen, so landen wir dann bei:
ceil(33 / 2) = 17
ceil(17 / 2) = 9
leider müssel wir also nochmal teilen. ich kann nicht abschätzen ob wir nach dem runden bei 32,57.. auf 33 genügend ecken sparen, dass es hier schon reicht
ceil(9 / 2) = 5.
damit sind wir aber ganz sicher dabei.
also braucht jeder 33+3 = 36 freunde, damit jeder jeden über 4 ecken(mittelsmänner) / 5 kanten! (also auch 5 oder 6 ecken) kennt.
und wir haben dann sogar ne menge dschungelredundanz

Der Spruch ist so gemeint, daß die sechste Ecke das Ziel ist ...

(aber gut, da ist ggf. Interpretationsspielraum)

@rene: also ist der direkte Freund die erste Ecke

@stth: tolle Erläuterung ... aber:
wo ist der Unterschied zwischen "jeder" und "jeder Erdenbürger"? Also wo genau liegt der Unterschied zwischen dem statistischen Ansatz und dem Hypercube. Und warum differieren die Lösungen. Und was bedeutet deine Lösung für die Aufgabenstellung?

jepp!

@Chris: auch wenn das jetzt abschweifend vom eigentliches Rätsel ist (noch hat keiner die korrekte Lösung / den korrekten Lösungsansatz):

Dieses Rätsel geht von Person X aus ... dann kann man sozusagen ein Baumdiagramm spannen. Gehe ich nun von einer beliebigen Person Y aus, die selber sich erst in der sechsen Ecke befindet, benötigt diese zu einer anderen Person Z der sechsten Ecke bis zu 12 Schritte (also Ecken), wenn beide vorher keinen gemeinsamen Bekannten haben ...

Das wäre durch aus eine weitere interessante Fragestellung ... also wenn Jeder jeden über sechs Ecken kennt ... (aber hier geht es nur um "man kennt jeden" ...) ;-)

der statische ansatz istbaumartig.. das heisst unter umständen kennen sich zwei "blätter" im baum über 2n ecken. die erweiterung fordert aber, das jeder jeden über maximal n ecken kennt

das der hypercube diese eigenschaft hat, ist numal in der natur seiner sache

*koppknall*

d.h., die Summe der letzten ecke muss 6,4 Mrd entsprechen. Ich hab ja alle mitgezählt die ich über 0-5 Ecken kenne. hmmpf

d.h. aus

wird

x^6 - x^5 - x^4 - x^3 - x^2 - x^1 - x^0 = 6,4 Mrd.


Lösung wäre: 43,2610110619187

*koppschüttel*

@rene:
Versteh ich nicht. Du musst doch nicht den Baum rückwärts durchlaufen, um von einer bestimmten Person zu einer anderen bestimmten Person zu kommen. Lediglich wenn du IMMER den egozentrischen Ansatz wählst, und festlegst, dass der Baum im 6ten Knoten sein Ende hat. Was er aber reell gesehen nicht hat, weil ja niemand keine Freunde hat, bloß weil du ihn schon über 6 Ecken kennst. Man spannt also den Baum für jede Person Y neu auf und läuft von dieser Startposition immer nach unten im Baum.

Von daher gibt es keinen Unterschied, ob du sagst "man" kennt jeden über 6 Ecken, oder jeder kennt jeden über 6 Ecken.

Die Hypercube Lösung kommt mir immer noch nicht so recht gut vor. Sie besagt, dass jeder mit jedem über 5 Kanten verbunden ist, wenn er nur 36 Freunde besitzt. Da wir den Baumansatz für eine Person (also mich z.B.) als richtig akzeptieren kann ich das ganze leicht wiederlegen. Möchte ich (Mensch Nr. 1) zum allerletzten Menschen (Nr. 6,4 Milliarden) vordringen, allein über 5 Kanten, und nehme ich an (wie auch in der Aufgabenstellung), dass alle Freunde einzigartig sind, und davon jeder 36 besitzt, so befinden sich in dem klassischen Baum, den ich aufspanne knapp 62 Millionen Menschen. Da kann also etwas nicht passen.

Ich kann einfach nicht mehr Menschen adressieren. Das funktioniert nur, wenn ich irgendwelche weiteren Vorbedingungen mit einschiebe, zum Beispiel, dass wenn A C über B kennt, A gleichzeitig auch C direkt kennt. Mit dieser Vorbedingung können wir aber auch gleich postulieren: jeder kennt jeden. Ohne Ecken ohne Kanten.

@marv:
x^0 + x^1 + x^2 +x^3 + x^4 + x^5 + x^6 = 6,4 Mrd. == Alle Knoten und Blätter im Baum sind insgesamt 6,4 Mrd.
x^6 = 6,4 Mrd == Nur die Blätter des Baumes sind 6,4 Mrd.
x^6 - x^5 - x^4 - x^3 - x^2 - x^1 - x^0 = 6,4 Mrd. == Blätter minus Knoten sind 6,4 Mrd., die Blätter liegen also insgesamt über 6,4 Mrd.

Welcher Ansatz auch immer gut ist, zum Ausrechnen des Baumes, man kommt doch mit den Lösungen darauf, dass es, auf Menschen gerundet, immer 43 ergibt und die Anzahl der Knoten verglichen mit der Anzahl der Blätter relativ irrelevant ist und deren Einfluß für große X deutlich sinkt. Im vorliegenden Fall haben wir ein Verhältnis von Knoten zu Blättern von 1 zu 42.