Mathematische Knobelaufgabe

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

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

ä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