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