Mathematische Knobelaufgabe

Dumme Gedanken:

HC:
- Jeder Knoten hat genau n-Kanten
- Es gibt genau 2^n Knoten.
- Jeder Knoten ist hoechtens n-Knoten von einem anderen Knoten entfernt.
- Wir nennen den n-HC auch n-Dimensionaler HC.

Erfuellt der HC eine der Bedingungen nicht, so ist es kein HC.
Ist es kein HC, so ist das Ergebnis v. fuer HC definierten Formeln ebenfalls undefiniert.

(_über_ 6 nodes (also Startknoten & Endknoten nicht eingerechnet):
--------------------------> <--------------------------
00-01-02-03-04-05-06-Z1-Z2-16-15-14-13-12-11(-00-01-02...)
01-02-03-04-05-06-07-08-09-10-11-12-13-14-15(-01-02-03...)
01: Ich.
Z1/Z2: worst-case Endpunkte fuer einen Weg.

Das muss man nun noch in ein HC ähnliches Gebilde (vielleicht ein nichtregelmaessiges Polyeder mit "inneren" Verbindungen) überführen. Die x(n-1)^n+1 bzw, x(n-1)^n, bzw, x(n-1)^n+1 Loesung hatte ich auch am Anfang. Ist aber IMHO crap.

Dieser Beitrag wurde von aktsizr: 24 Feb 2007, 18:29 bearbeitet

Offizielle Auflösung: x = 43,7539963

Der Grundansatz wäre erst einmal eine allgemeine Formel, die die Anzahl der Personen aller Ecken addiert.

Diese könnte so aussehen (Anlehnung an LaTeX-Syntax):

6.4 Mrd = 1 + n_1 + n_2 + n_3 + n_4 + n_5 + n_6

(Die, die die Aufgabe jetzt so ausgelegt haben, als sei über sechs Ecken auch die siebente Ecke eingeschlossen, würden hier noch ein n_7 dranhängen)

Nun gilt es die Stufen mit Leben zu füllen. n_1 sind alle meine direkten Kontakte - es entspricht dem gesuchten Wert x.

Ab der zweiten Ecken ist zu beachten, daß Kontakte auf Gegenseitigkeit beruhen. Das
heißt meine x Kontakte kennen ja bereits mich, d.h. sie kennen nur noch x - 1 weitere
Kontakte. (Rechenbeispiel: Wenn ich 5 Kontakte kenne, kennen diese fünf jeweils mich
und vier andere)

n_2 = x * (x-1)

Das müßte man synchron auf alle weiteren Stufen anwenden.

Dann heißt es alles ausmultiplizieren (Pascal'sches Dreieck) zusammenfassen und Kürzen, bis man folgende Gleichung erhält:

6.400.000.000 = 1 + x^6 - 4x^5 + 7x^4 - 6x^3 + 3x^2

Nun kann man probieren, den GTR quälen - oder wer das mathematische Gen noch im Blut hat: den Newton anwenden.

Das war´s ;-)

Ich habe zusammenfassend noch eine PDF-Datei dazu erstellt mit Aufgabenlösung und detaillierteren Rechenweg: http://renephoenix.de/pic/b1536p1.pdf

Ich bin auch zu doof. Mein einziger Trost, keiner hier hat meinen Fehler bemerkt.

Danke Dir für die nette Aufgabe

@Rene: gugg dir mal ganz genau die letzten knoten von deinem Baum an. Die lösung geht nicht auf... hab erst dem aktsizr nicht geglaubt stimmt aber wirklich

Da passt was nicht. Der Ursprung hat noch x Kontakte, die Ecken haben aber nur noch x-1 Kontakte. Ich als Anfangsknoten habe aber genauso nur x-1 Kontakte.
D.h. n_1 = (x-1), n_2 = (x-1)*(x-1), n_3 = (x-1)*(x-1)*(x-1) und so weiter.
Jetzt kann ich (x-1) = y substituieren und erhalte N_1 = y, N_2 = y^2, N_3 = y^3 ...
Damit bin ich wieder bei wombat's Formel, kann das ganze ausrechnen und erhalte y=43, x=44, wobei der erste (also ich) nur 43 Kontakte besitze.
Mit deiner Formel kommt man zwar auch auf die 44, nimmt dabei aber an, dass der Ursprung einen Kontakt mehr besitzt, als die anderen.
Da deine Annahmen (2 und 3 widersprechen sich übrigens) sowieso davon ausgehen, dass es keine redundanten Kontakte gibt (und der Kontakt zum vorhergehenden Freund wäre so einer), dann reicht sogar der Ansatz nach y um die korrekte Anzahl der neuen Kontakte auszurechnen.

@chris: zu dem zeitpunkt, als du gefragt hattest, wa die alte lösung schon überholt. lesen hilft.

ansonsten ist renes lösung mathematisch korrekt.

@rene
du redest über netzwerke und bringst dann eine solche baumlösung. ist es nicht irgendwie schade, dass der mensch an der spitze des des "netzwerkes" nicht austauschbar ist, ohne die gegebene netztopologie koplett umzuwerfen?

@aktsizr
die hypercubelösung ist wie bereits in post #32 erwähnt habe nicht machbar, selbst mit abkürzung über diagonalen nicht.
meine lösung aus post #38 behält die hypercubeeigenschaften, nur halt dass nicht verdoppelt wird in jeden schritt, sondern ver-n-facht (und damit auch n-1 mehr kanten an jeden knoten sind).

Dieser Beitrag wurde von stth: 25 Feb 2007, 11:34 bearbeitet

und die angebliche loesung gilt doch wieder nur fuer den optimalen fall....also ist sie zwar nicht falsch, aber auch nicht korrekt.

ums nochmal zu verdeutlichen (von mir ausgehend):

zwei meiner bekannten kennen sich ebenfalls, dies wuerde bei der ersten ecke schon x-2 bedeuten oder etwa nicht? da bekannte oftmals auch verwand sein koennen, ist dies auch als ein normalfall anzunehmen... so und nun will ich mal nen ordentlichen ansatz von loesung sehen, welcher diesen aspekt mit einbezieht. man beachte, das man vorher noch statistisch ermitteln muss, wer wen in meinem bekanntenkreis kennt

Wenn ich stth (der es immer wieder schafft, um die Antwort drum herum zu reden) richtig verstehe, bildet sein komischer n-Hypercube genau den von gfx-shaman geforderten realen Anwendungsfall ab.

Die angebliche Lösung von Rene, bzw. von wombat gilt natürlich für den optimalen Fall, da in der Aufgabenstellung nach dem optimalen Fall gefragt war. D.h. man erfasst mit der statistischen Methode den minimalen Fall. Jede Berechnung die mit durchschnittlich weniger als 43 neuen Freunden pro Knoten auskommt muss falsch sein.

@stth: warum sollte der Mensch an der Spitze des Baumes nicht austauschbar sein? Natürlich ist er das, weil er ja nicht genau bestimmt ist. Auch lässt sich die Topologie auf jeden idealen Menschen übertragen. Ideal deshalb weil wir durch unsere Annahmen auch ein ideales Modell konstruieren.

Und warum ist Renes Lösung korrekt? Womit erklärst du, dass der Ausgangspunkt x und jeder andere Knoten nur x-1 Verbindungen hat?

@Chris: Das Mathematik auch an der Realität vorbei gehen kann, ist doch allseits bekannt - schon alleine die Annahme, redundante Kontakte auszuschließen.

Ich selber kenne n-Kontakte, wen sollte ich denn noch kennen. Da gibt es keinen Weg zurück (Wenn ich 5 Kontakte kenne, kennen die fünf bereits mich und vier andere)

@stth: Ja, schon. Es kann ja jemand die Aufgabe mal auf Hypercube umstellen ... wäre sicher auch ein interessantes Rätsel.

@gfx: wenn du die Redundanzen einbauen willst, kommt eine zweite Unbekannte ins Spiel: wieviele kenne sich dann untereinander ...

@Rene:
Schon klar. Für mich ist aber der Kontakt zu meinem Vorgänger ein redundanter Kontakt. Dieser wird mit deiner Annahme "jeder kennt gleich viele oder weitere für diese Betrachtung nicht relevante Kontakte" ausgeschlossen. Aber darüber könnten wir ewig streiten. Sagen wir du hast einen richtungslosen Graphen angenommen, während ich einen richtungsorientierten Baum angenommen habe.

Kann mir jetzt jemand erklären, was für eine Problemstellung mit dem Hypercube gelöst wird?
Und warum der Baum nicht auf jeden beliebigen Menschen anwendbar sein soll? (Klar ist, dass ich nicht einen produzierten Graphen aus dem Baum für alle Menschen anwenden kann, ich muss natürlich das Wurzelelement auf den aktuellen Menschen setzen und den Graph neu zeichnen.)

@stth: warum sollte der Mensch an der Spitze des Baumes nicht austauschbar sein? Natürlich ist er das, weil er ja nicht genau bestimmt ist. Auch lässt sich die Topologie auf jeden idealen Menschen übertragen. Ideal deshalb weil wir durch unsere Annahmen auch ein ideales Modell konstruieren.
[/quote]gut. wir haben einen baum. dieser stellt die in unserem fall reale freundestopologie dar.
tante fuchs ist an der spitze. dann erklär mir mal bitte, wie du in der ersten schicht zu jemanden in der letzen schicht des unterbaumes eines anderen freundes von tante fuchs immer noch nur 6 ecken haben willst?

allgemein ausgedrückt. die erde ist gegeben und

weil der mensch an der spitze keine verbindung nach oben hat

sonst: der n-hypercube ist auch nur eine wunschvorstellung. der witz daran ist, dass alle menschen gleichberechtigt sind und die welt von ihnen aus immer genauso aussieht. und damit das netzwerk bestehen bleibt, und trotzdem jeder mensch über 6 ecken bekannt ist.

ach kacke, ich drops hab auch bei n_1 x-1 gerechnet..

naja, ich sagte ja bereits: zu trivial!