Es stand die These im Raum: Über sechs Ecken kennt man jeden auf der Welt.


Die daraus resultierende, interessante Frage: Wieviele Personen müßte dafür jeder kennen?

Es wird angenommen:

• Die Population der Erde beträgt 6.4 Mrd Menschen
• Keine redundanten Kontakte
• Jeder hat gleich viele Kontakte (oder für die Betrachtung nicht relevante zusätzliche redundante Kontakte)

Auf was für Ergebnisse kommt ihr bei der Rechenaufgabe? (Und für die, die zu faul zum Rechnen sind: Was schätzt ihr?)

(Zur Kontrolle: der Wert ist durchaus nicht utopisch. Da falsche Ansätze zu relativ ähnlichen Ergebnissen führen können, möglichst mit Kommastelle)

Anmerkung: die These drückt aus, daß du mit maximal fünf Zwischenkontakten jede Person auf der Welt kennst.

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