Mathematische Knobelaufgabe Über sechs Ecken kennt man jeden auf der Welt!

@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.

ok ich hab den fehler gefunden.
die erste diagonale, für die benötigt man nur einen neuen freund.
für die zweite diagonale braucht man dann schon viele mehr weil man die struktur ja zerstört hat. danach hat man seeeehr viel mehr am weitesten entfernte punkte. ob sich das lösen lässt, überleg ich mal beim duschen....

ok ich hab den fehler gefunden.
die erste diagonale, für die benötigt man nur einen neuen freund.
für die zweite diagonale braucht man dann schon viele mehr weil man die struktur ja zerstört hat. danach hat man seeeehr viel mehr am weitesten entfernte punkte. ob sich das lösen lässt, überleg ich mal beim duschen....

ich denke das geht so. hab da gestern abend mal drüber nachgedacht. ich mal das dann mal auf. im prinzip müssen von jedem menschen strahlförmig kontakte ausgehen. zu den meisten direkt, zu anderen weit entfernten auch paar. so dienen immer ein paar wenige als vermittler für sehr viele und man erhält ein netzwerk, das immer über nur 6 ecken zu jedem menschen eine verbindung herstellen kann. eine baumstruktur kann niemals funktionieren, weil man sich nur mal die verbindung zwischen den beiden äußersten ästen in der weitesten verzweigung anschauen muss..

Rhizome statt Bäume !

auch das wird nicht gehen. denn die weitest entfernten zweige müssen auch noch vernetzt sein, es kann jeder unterschiedlich viele direkte kontakte haben, muss aber immer äquivalent viele indirekte kontakte besitzen, um auf 6,4 millionen zu kommen.

/edit: mir fiel da noch was ein..

Dieser Beitrag wurde von yocheckit: 22 Feb 2007, 19:23 bearbeitet

so, hier noch schnell meine skizze dazu:

(leider nicht die beste quali)
ich starte auf einem kleinen dorf in der nähe von dresden, kenne jemanden in letztgenannter stadt und über ihn jemanden in frankfurt am main - mein bekannter über die erste ecke, nämlich über den aus dresden. durch meine bekanntschaft mit diesem dresdner kenne ich auf der welt 1,4 milliarden menschen wie im kreis eingezeichnet. allein über den bekannten, den der frankfurter in dubai hat werden 280 millionen kontakte beigesteuert. die reise geht weiter bis zu irgendeinem wildfremden in williams creek, im herzen australiens. diesen erreiche ich über 6 ecken. nun hab ich aber noch eine bekannte in neuseeland auf dem dorf, die heute nacht in einem pub ihren traummann kennen lernen wird, den sie zwar nicht kennt, ich aber über 6 ecken schon. nun stellt euch vor, sie wäre nicht eine bekannte von mir, dann würde ich davon nie erfahren.

links oben hab ich davon ein modell abgeleitet, was zwar falsch sein kann, aber so ließe sich das problem vielleicht vergleichmäßigen. die einen sind direkte kontakte und dann gibt es eine verbindung zu denen, die weit weg von mir wohnen. jetzt müsste mir nur noch das mathematische modell dazu einfallen, aber ich muss leider gleich weg..

ich denke das geht so. hab da gestern abend mal drüber nachgedacht. ich mal das dann mal auf. im prinzip müssen von jedem menschen strahlförmig kontakte ausgehen. zu den meisten direkt, zu anderen weit entfernten auch paar. so dienen immer ein paar wenige als vermittler für sehr viele und man erhält ein netzwerk, das immer über nur 6 ecken zu jedem menschen eine verbindung herstellen kann. eine baumstruktur kann niemals funktionieren, weil man sich nur mal die verbindung zwischen den beiden äußersten ästen in der weitesten verzweigung anschauen muss..

ähm.. mal dir mal n 4er hypercube auf, zeichne die diagonalen ein und markieren alle knoten, die 2 einheiten von einem beliebigen punkt entfernt sind. zu diesen müsstest du jetzt wieder eine diagonale ziehen. es sind 10. das heisst, du hast dan ne jeder mit jedem vernetzung also insgesamt bei 16 knoten 15 verbindugnen. in nem 6er hypercube halbiert das dann zwar auch noch mal die verbindungen, aber du musst mit wesentlich mehr enferntesten punkten rechnen. vllt mit 40 oder so. äusserst ineffizient

€ checkit: genau das ist das prinzip eines hypercube

Dieser Beitrag wurde von stth: 22 Feb 2007, 20:09 bearbeitet

ok.. ich hab den hypercube mal verallgemeinert:


und nu rechnen wir damit:

das ist die böse variante. also 6 kanten

k = 6 d.h. der abstand zwischen 2 beliebigen knoten beträgt maximal 6 kanten im gesamten (ich such noch n namen dafür, sagen wir stth (oder ist es das, was pusti meinte))

log n (6.4mrd) = 6

n = 43.089 (zu dumm) aber 44 hoch 6 ist auch nur 7,35 mrd
(dass die ergebnisse sich ähneln ist übrigens kein zufall)

das heisst, dass k(n-1) = 6*(44-1) = 258 kanten an jedem knoten.
das heisst, jeder mensch auf der welt benötigte genau 258 freunde, damit das prinzip für jeden gilt.

für checkit: betrachte die 44 leute in einer einheit einfach als freundeskreis dummerweise müssen jeder dieser 44 215 leute aus disjunkten freundeskreisen kennen.

nehmen wir eure lasche variante:

log n (6.4mrd) = 7
n = 25.17 -> n = 26
(na guck mal einer schau, schon wieder ähnlichkeit)

k(n-1) = 7*(26-1) = 175 kanten an jedem knoten. also 175 freunde.
fine.

so und nun vernetzt mal euren baum so, dass ihr da drunter kommt. ich bin gespannt.

Des leichteren Verständnisses wegen, erklär ich meinen Gedankengang ersteinmal für den Fall, dass jeder mit jedem höchstens im 2. Grad bekannt ist, dh. über höchstens 2 Kanten (oder anders: jeder ist mit sich (0. Grad), mit seinen direkten Freunden (1. Grad) oder deren Freunden (2. Grad) bekannt).

Stellen wir uns ein 2-dimensionales Raster vor. Jeder Gitterpunkt stellt einen Menschen dar. Menschen auf einer Linie (waagerecht oder senkrecht) sind miteinander befreundet (jede Linie bildet also einen Freundeskreis). Es ist offensichtlich, dass jeder mit jedem über höchstens 2 Kanten befreundet ist. Geht man davon aus, dass das Raster durch ein Quadrat mit der Kantenlänge n begrenzt ist, wäre jeder Mensch in 2 Freundeskreisen (2 Dimensionen) und hätte demzufolge F=(n-1)*2 Freunde (Anzahl der Punkte sowohl in der Waagerechten als auch Senkrechten OHNE sich selbst). Erweitert man nun das Ganze auf d Dimensionen, wäre jeder Mensch also in d Freundeskreisen und hätte (n-1)*d Freunde. Bei M=6.4e9 Menschen und 6 Freundeskreisen ergäbe sich das viel diskutierte n^6=6.4e9, dh. eigentlich n=M^(1/6)=43.088... also n=44 => F=(44-1)*6=258, so wie schon festgestellt. Das Problem an dieser Theorie ist die Tatsache, dass das Kriterium der geringen Redundanz nicht berücksichtigt wurde, denn:

Gehen wir zurück zum 2-dimensionalen Fall: ein Mensch mit den Koordinaten (1|5) ist mit dem Menschen auf (7|2) genau über 2 andere Menschen bekannt ((1|2) und (7|5)), wobei einer ja vollkommen reichen würde. Reduzieren wir unser Quadrat nun auf ein rechtes Dreieck, fällt einer der beide weg (zB. (7|5)) und es ändert an der oben genannten Formel für F nichts, außer dass man jetzt nichtmehr sagt "JEDER Mensch hat F Freunde" sondern "ES GIBT Menschen mit maximal F Freunden (im Koordinatenursprung)" [Das kann jeder gerne selbst mit Stift und Papier nachvollziehen]. Das größere Problem ist jedoch, dass die eben "wegreduzierten" Menschen jetzt ebenfalls in diesem Dreieck untergebracht werden müssen, d.h. M ergibt sich im 2D-Fall nichtmehr durch n*n sondern in etwa durch n*n/2 (eigentlich sogar n*(n+1)/2). n wird im allgemeinen also größer sein als zuvor - ebenso F. Dafür ist auf der anderen Seite aber gewährleistet, dass es für jedes Paar Menschen nur exakt einen Weg gibt, über den sie bekannt sind, und dieser ist maximal d Kanten lang.


Es bleibt zu ermitteln, inwelcher Form die Dimension d die Abhängigkeit von n und M beeinflusst. Man muss in jeder Dimension halbieren, jedoch "halbierten" man dabei WÖRTLICH Menschen (entlang der Diagonalen)... vermutlich gilt: M=(n-1+d)!/(n-1)!/d!... viel Spaß beim Umstellen nach n... (^^,)

Macht's nicht zu kompliziert ... ;-)

Die Baumvorstellung reicht völlig ... nur das entscheidende, worauf es bei der Formel ankommt, hat noch keiner eingearbeitet

25,17?

Dieser Beitrag wurde von NEO.POP: 23 Feb 2007, 00:08 bearbeitet

Warauf kommt es dir denn an, Rene?

@Robin: einer hatte schon die richtige Idee hier gehabt ... hat nur keiner ausgebaut ;-)

@Neo: ist nen Tick zu wenig ...

Ansonsten: ich laß es noch ein zwei Tage drin, dann gibt es die Auflösung.

gib mal ne definiton von ecke...

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" ...) ;-)

schade, jetzt erst gelesen.. nun ist mir das problem zu trivial!