WisFaq!

Hyper cubes

Hallo,

Hopelijk dat ik het onderwerp onder het juiste kopje heb geplaatst maar ik heb een vraag over Hyper-kubussen.
Dit onderwerp komt aan de orde in het boekje "Enen en nullen" nr 19 van de zebra-reeks.
Het gaat hier om vraag 50 die als volgt luidt:

Opdracht 50
"Probeer zoveel mogelijk hoekpunten op de 5-kubus te vinden zo, dat ze twee aan twee Manhattan-afstand mistens 3 hebben.
Probeer ook te verklaren waarom je er niet meer kunt vinden"

Geven:
0-kubus = punt.
1-kubus = lijn.
2-kubus = vlak.
N-kubus = enzovoort

Een Manhattan afstand van 3 wil zeggen dat drie van de N-bits (N-kubus) tussen twee gekozen coordinaten verschillen.

Ik snap bovenstaande vraag niet goed. Mij lijkt het dat je van elk hoekpunt moet nagaan naar welke mogelijke andere hoekpunten je kan gaan waarbij de afstand 3 of meer is.\
Sommigen hiervan overlappen elkaar.
Ben benieuwd of iemand me op weg kan helpen met het juist interpreteren van deze vraag.

Groeten Wytze

Wytze Hoekstra
9-12-2005

Antwoord

Dag Wytze,

Elk punt van de 5-kubus kan je beschrijven met 5 enen of nullen, zo is (1,0,1,0,1) een punt ervan.

De Manhattanafstand tussen twee punten is nu het aantal plaatsen waarop de coördinaten van beide punten van elkaar verschillen: zo is de afstand tussen (1,0,1,0,1) en (0,1,0,1,0) gelijk aan 5, de afstand tussen (1,1,0,0,1) en (0,1,0,1,1) is 2.

De opdracht is nu om een verzameling punten te vinden zodat, als je er twee willekeurig uitkiest, hun onderlinge afstand minstens drie is. Om die verzameling op te stellen: begin met een eerste, willekeurig punt, vb (0,0,0,0,0). Voor je tweede punt heb je een punt nodig op afstand minstens 3. Probeer eerst eens een punt op afstand 5 te leggen (dus (1,1,1,1,1)). Kan je nadien nog een punt toevoegen dat op afstand minstens 3 van deze twee punten ligt? Probeer dan eens met afstand 4 (vb (1,1,1,1,0)), zoek nog een punt, etc.

Groeten,
Christophe.

Christophe
10-12-2005