Latijnse kubus

[Marcelo Pars]

Hoi,

Ik heb een spelletje gemaakt dat het meest overeenkomt met een 3D Sudoku. De oplossing van het spel is steeds een Latijnse kubus, zoals bijvoorbeeld op deze figuur:


Mijn vraag is nu: hoeveel Latijnse kubussen van 4 x 4 x 4 bestaan er? Ik besef dat 1 kubus op 6 manieren op de tafel gezet kan worden en ik beschouw dat ook als 6 verschillende Latijnse kubussen (tenzij er symmetrie in het spel is).

Enfin, ik ben er niet uit gekomen en vond het uiteindelijk makkelijker om een de app te maken met 1000 spelletjes. Als je meer wil weten kun je naar http://www.cubicks.com.. Maar de vraag heeft me toch niet los gelaten.

Met vriendelijke groet,

Marcelo

[siep]

Via brute kracht met de computer:
Als je de kubus fixeert EN de kleuren van 1 ribbe vastlegt, bijvoorbeeld bovenvoor = rood-groen-geel-blauw, zoals in je plaatje, dan kom ik uit op 5528 verschillende oplossingen.
Dus als we alle 4! = 24 kleurpermutaties beschouwen, dan zijn er bij de gefixeerde kubus
24 * 5528 = 132672 Latijnse kubussen mogelijk.

Als we de kubus vrij mogen verdraaien, heeft elke kubus 24 mogelijke posities:
6 mogelijke posities voor het voorvlak, met voor elk van deze 6 posities nog 4 mogelijkheden voor het ondervlak.
Als ik de overbodige kopieën van bestaande kubussen wegfilter, hou ik van de 132672 nog 6520 over die werkelijk uniek zijn.

NOOT: zo'n computerprogramma vraagt nogal wat (foutgevoelige) boekhouding, daarom zou het mooi zijn als er nog iemand is die deze getallen kan bevestigen of weerleggen.

[parko]

Via brute kracht met de computer:
Als je de kubus fixeert EN de kleuren van 1 ribbe vastlegt, bijvoorbeeld bovenvoor = rood-groen-geel-blauw, zoals in je plaatje, dan kom ik uit op 5528 verschillende oplossingen.
Dus als we alle 4! = 24 kleurpermutaties beschouwen, dan zijn er bij de gefixeerde kubus
24 * 5528 = 132672 Latijnse kubussen mogelijk.

Als we de kubus vrij mogen verdraaien, heeft elke kubus 24 mogelijke posities:
6 mogelijke posities voor het voorvlak, met voor elk van deze 6 posities nog 4 mogelijkheden voor het ondervlak.
Als ik de overbodige kopieën van bestaande kubussen wegfilter, hou ik van de 132672 nog 6520 over die werkelijk uniek zijn.

NOOT: zo'n computerprogramma vraagt nogal wat (foutgevoelige) boekhouding, daarom zou het mooi zijn als er nog iemand is die deze getallen kan bevestigen of weerleggen.

ik kom uit op (4!x4)x((4!-8)x4)x4x2x2x2 = 196.608 mogelijkheden

voor 1 vlak(voorkant) zijn er 4!x4 mogelijkheden = 96
voor de achterkant zijn er dan nog (4!-8)x4 = 64 mogelijkheden
voor de linkse kant blijft er nog 4 mogelijkheden over
voor de 3 andere vlakken blijven er telkens 2 mogelijkheden over

[siep]

Hoe kom je aan deze getallen?
Zonder draaiingen en met de bovenrand gefixeerd rood-groen-geel-blauw kom ik uit op 24 mogelijke Latijnse vierkanten:



(Als we ook alle mogelijke permutaties van de kleuren van de bovenrand meetellen,
zijn er dus 4! * 24 = 24 * 24 = 576 verschillende Latijnse vierkanten.)

De 4 randen van deze vierkanten leggen in de Latijnse kubus elk 1 rand van het aangrenzende vlak vast.
Voor het rechter zijvlak houden we dan met 1 vaste rand weer 24 mogelijkheden over.
De mogelijkheden van het bovenvlak worden nu nog sterker beperkt: zowel door het voorvlak als door het rechter zijvlak, die resp. de voorste en de rechtse rand vastleggen.

[parko]

Hoe kom je aan deze getallen?
Zonder draaiingen en met de bovenrand gefixeerd rood-groen-geel-blauw kom ik uit op 24 mogelijke Latijnse vierkanten:

waarom niet 24x4?
je kan je bovenste horizontale rij ook in de de tweede, derde en vierde horizontale rij zetten
wat telkens ook 24 mogelijkheden oplevert

[siep]

Ik heb hierboven de eerste rij gefixeerd, en dan alle mogelijke oplossingen gegeven voor het Latijnse vierkant.
Dit zijn er 24.
Elke permutatie van de bovenste rij geeft een nieuwe set van 24 Latijnse vierkanten.
Er zijn 4! = 4*3*2*1 = 24 permutaties van de bovenste rij mogelijk, die elk 24 verschillende oplossingen genereren.
In totaal zijn er dan 24 * 24 = 576 Latijnse vierkanten.

In jouw oplossing tel je alle Latijnse vierkanten waarin de rij
rood-groen-geel-blauw
voorkomt op 1 van de rijen.
Maar er zijn ook oplossingen zonder deze rij, bijvoorbeeld het vierkant:

groen-rood-geel-blauw
rood-groen-blauw-geel
geel-blauw-groen-rood
blauw-geel-rood-groen

Dergelijke vierkanten mis je dus in je telling.

[parko]

Dergelijke vierkanten mis je dus in je telling.

inderdaad, had eerst 4!x4!x384(achterkant) gedaan , maar veranderd vanwege een verkeerde ingeving

[Marcelo Pars]

Beste Arie,
Leuk dat je op mijn vraag bent ingegaan. Ik ben nog steeds niet in staat de puzzel op te lossen en jij maakt voor mij te grote stappen waardoor ik je niet kan bijhouden. Uiteindelijk zeg je dat je 6520 unieke exemplaren overhoudt. Kun je mij uitleggen waarom het antwoord niet deelbaar door 24 hoeft te zijn? Aangezien er 24 unieke eerste rijen zijn, zou ik ook verwachten dat het aantal unieke Latijnse kubussen deelbaar moet zijn door 24, aangezien geen van de 24 unieke eerste rijen wezenlijk verschilt van de ander.

[siep]

Er bestaan kubussen met zelfsymmetrie, bijvoorbeeld deze:



(in dit plaatje zie je resp:
bovenvlak,
voor-, rechter-, achter-, linkervlak,
ondervlak
waarbij je het plaatje kan uitknippen en dichtvouwen tot een kubus)

De bovenvoorbalk heeft nu slechts 2 mogelijke waarden (hoe je de kubus ook draait):
rood-groen-blauw-geel
of
geel-blauw-groen-rood

Deze kubus wordt dus 2 keer gevonden als we alle oplossingen genereren, en telt 1 keer mee bij de unieke kubussen.

Hier een tabel met waarden die ik vond:
r = aantal verschillende boven-voor-balken op een kubus
n = aantal unieke kubussen met r verschillende boven-voor-balken
r*n = aantal gegenereerde kubussen met r verschillende boven-voor-balken

Code: Selecteer alles

r          n         r*n
2         24          48
6        120         720
8        168        1344
12      1536       18432
24      4672 +    112128 +
       -------   ---------
        6520      132672

De optelling van de tweede kolom geeft het aantal unieke kubussen:
6520,
de optelling van de derde kolom geeft het totaal aantal kubussen:
132672 = 24 * 5528

Voor de kubussen met r=24 verschillende boven-voor-balken geldt:
alle 12 ribben van links naar rechts EN van rechts naar links gelezen,
leveren verschillende kleuringen van de boven-voor-balk.
Deze kubussen worden dus 24 keer gegenereerd (voor elk van de
boven-voor-balken een keer), en leveren slechts 1 unieke kubus.
Hiervan blijven er dus 1/24 over.
En 1/24 van een 24-voud hoeft geen 24-voud te zijn.

[Marcelo Pars]

Hoi Arie,

Bedankt. Je hebt veel verduidelijkt, maar als je het goed vind gebruik ik nu mijn eigen woorden om zeker te zijn dat ik het snap: Stel je hebt de kubus met een gefixeerde voorkant en een gefixeerde bovenkant. Zeg maar een kubus op een stokje op de vensterbank die met altijd dezelfde kant de huiskamer in kijkt. Een schilder moet dan 132672 keer schilderen om vanuit die huiskamer alle verschillende kubussen een keer gemaakt te hebben. Maar hij kan ook de kubus maar 6520 keer opnieuw schilderen en toch alle versies tonen door (stiekem) de kubus te verdraaien.

Verder zeg je in je eerste mail:

zo'n computerprogramma vraagt nogal wat (foutgevoelige) boekhouding, daarom zou het mooi zijn als er nog iemand is die deze getallen kan bevestigen of weerleggen.

en in je laatste mail:

Hier een tabel met waarden die ik vond:

Heb je met de gevonden tabel daarmee zelf je computerberekening bevestigd?

De symmetrie die je hebt aangehaald is verhelderend voor mij geweest. In mijn zoektocht naar het aantal unieke Latijnse kubussen stuitte ik op een voor mij raadselachtig fenomeen (zie plaatjes). In dit eerste plaatje zie je een gedeelte van de Latijnse kubus. De kubusjes die je niet ziet heb ik beschilderd en er blijken in totaal 4 mogelijke Latijnse kubussen te zijn.

In onderstaand plaatje weer een gedeelte van Latijnse kubus, maar uiteindelijk blijkt dit geen Latijnse kubus te zijn want er is geen enkele mogelijkheid om de niet zichtbare blokjes juist te kleuren.

Ik denk dat dit een zelfde fenomeen is als de symmetrische kubussen. De ene is de ander niet. Maar de symmetrie begrijp ik toch nog niet. Bij r = 2 zijn er 2 verschillende soorten ribben. Maar je hanteert ook r = 24. Hoe kunnen er 24 verschillende ribben aan een Latijnse kubus zitten, terwijl er maar 12 ribben zijn? Je probeert het uit te leggen met

van links naar rechts EN van rechts naar links gelezen

maar ik begrijp dat (nog) niet.

Marcelo

[Marcelo Pars]

Sorry, de afbeeldingen had ik fout doorgezet. Dit is de Latijnse kubus met vier oplossingen:


En dit is de Latijnse kubus zonder oplossingen, dus eigenlijk geen Latijnse kubus:

[siep]

... als je het goed vind gebruik ik nu mijn eigen woorden om zeker te zijn dat ik het snap: Stel je hebt de kubus met een gefixeerde voorkant en een gefixeerde bovenkant. Zeg maar een kubus op een stokje op de vensterbank die met altijd dezelfde kant de huiskamer in kijkt. Een schilder moet dan 132672 keer schilderen om vanuit die huiskamer alle verschillende kubussen een keer gemaakt te hebben. Maar hij kan ook de kubus maar 6520 keer opnieuw schilderen en toch alle versies tonen door (stiekem) de kubus te verdraaien...

Klopt

... Heb je met de gevonden tabel daarmee zelf je computerberekening bevestigd?...

Die tabel is een samenvatting van mijn gegevens.
Met dit soort berekeningen is het fijn als iemand anders ze (onafhankelijk) kan bevestigen.
Mogelijk zijn de getallen ook in de literatuur terug te vinden, maar ik ben ze nog niet tegengekomen.

Maar je hanteert ook r = 24. Hoe kunnen er 24 verschillende ribben aan een Latijnse kubus zitten, terwijl er maar 12 ribben zijn? Je probeert het uit te leggen met
"van links naar rechts EN van rechts naar links gelezen"
maar ik begrijp dat (nog) niet.

Neem bijvoorbeeld deze kubus (weer opengevouwen als voorheen):



In deze vorm is de boven-voor-balk: rood-groen-geel-blauw
Draai deze kubus nu 2 keer een kwart slag (2 x 90 = 180 graden) over de as loodrecht op het beeldscherm:
het voorvlak blijft het voorvlak, het oude bovenvlak zit nu onder.
Neem vervolgens de draai-as horizontaal in het vlak van het beeldscherm,
neem de onderkant van het voorvlak en draai die omhoog (een kwart slag = 90 graden).
Nu zit het oude voorvlak in het bovenvlak, en het oude ondervlak in het voorvlak.
De boven-voor-balk is nu: blauw-geel-groen-rood.
De ribbe tussen voor- en boven-vlak levert zo 2 verschillende kleuringen.

Door deze kubus in alle 24 mogelijke posities te draaien (6 mogelijkheden voor het grondvlak en vervolgens telkens 4 mogelijkheden voor het voorvlak), krijgt de boven-voor-balk steeds een andere kleurcodering (ook 24 verschillende).

Omgekeerd zal elk van de 4! = 24 mogelijke kleuringen van de bovenbalk deze kubus als 1 van zijn mogelijke oplossingen genereren.
Deze kubus tellen we dus 24 keer in plaats van 1 keer = 23 keer te veel.

[Marcelo Pars]

Bedankt Arie, je uitleg over de 24 ribben is me nu ook duidelijk. Nu begrijp ik ook hoe jij het totale probleem benadert zonder dat ik weet of je tellingen juist zijn. Met het gevaar dat blijkt dat ik het toch niet begrijp, wil ik terug naar je eerste regel in je tabel waarbij geldt: r = 2 en n = 24.

Ik begrijp hieruit dat er maar 24 Latijnse kubussen zijn te maken die maar 2 verschillende ribben hebben. Eén daarvan heb je zelfs geheel uitgetekend. Aangezien er ook maar 24 verschillende ribben mogelijk zijn denk ik dat er 12 paren zijn (in jouw uitgewerkte voorbeeld het paar "geel-blauw-groen-rood" in combinatie met het spiegelbeeld "rood-groen-blauw-geel) die ieder 2 Latijnse kubussen opleveren. Als jij van dit specifieke paar al de ene Latijnse kubus hebt getekend, ben ook benieuwd naar de ander.

Zelf zie ik vooralsnog wel meer Latijnse vierkanten met de door jouw getekende ribben. In jouw getekende Latijnse kubus vormen de rode en gele vakjes steeds diagonalen. Een ander Latijnse kubus zou zijn waarbij de rode en gele kernen juist verwisseld zouden zijn met rode en gele hoekpunten en weer een andere Latijnse kubus zou zijn als in een aantal vlakken de rode en gele wel diagonalen vormen en in een aantal vlakken juist niet.
Maar ik neem aan dat ik met deze gedachte een misstap maak en jij mij weer op het juiste pad zult helpen..

[siep]

Dit zijn alle 24 Latijnse kubussen waarvan er per stuk precies 2 gegenereerd worden.

Let wel:
[1] ze hebben elk 2 ribbe-kleuringen (in tegengestelde kleurvolgorde van elkaar)
EN
[2] ze zijn bij vrije draaing volledig identiek aan hun tweeling-kubus

Ze moeten dus niet alleen slechts 2 gelijke ribben hebben, maar moeten ook nog via draaiing volledig in elkaar kunnen overgaan. En dat beperkt het aantal.

Dit betekent voor elke kubus ook dat alle 6 vlakken hetzelfde moeten zijn (op draaiing na).
Immers: als er onder eenzelfde ribbe-kleuring meer dan 1 vlak zou zijn, dan moet het aantal gegenereerde kubussen met die kleuring ook meer dan 2 zijn (2 is het minimum: voor elke ribbe-kleuring hebben we ook de tegengestelde kleuring).

[Marcelo Pars]

Oke Arie, ik moet hier weer van bijkomen. Toch meteen een vraag terwijl ik mogelijk eerst zelf wat harder na zou moeten denken:

In jouw r | n tabel staat een onderverdeling van alle unieke Latijnse kubussen (totaal 6520) geordend naar het aantal verschillende ribben dat een kubus heeft (r). In welke regel van jouw tabel vallen nu de Latijnse kubussen die slechts 2 verschillende ribben hebben (nota bene tegengesteld aan elkaar) maar niet hetzelfde vlak hebben (op de draaiing na).