Rubikvlak

Een Rubikvlak is een rechthoek met een willekeurig aantal rijen en kolommen: r rijen en k kolommen. Het Rubikvlak bestaat dan uit r*k vierkanten. De basisoperaties op een Rubikvlak zijn het omkeren van een rij of een kolom. Elke rij/kolom kan apart gekeerd worden. Het Rubikvlak is geïnspireerd op de bekende Rubikkubus.

Rubikvlak:beginpositie en willekeurige toestand

Probleemstelling

Mogelijke toestanden van een Rubikvlak

Welke toestanden van een Rubikvlak kunnen vanuit een bepaalde begintoestand worden bereikt met de gegeven basisoperaties. Zijn er toestanden die met de basisoperaties niet bereikt kunnen worden? Is dat afhankelijk van de afmetingen van het vlak? Bijvoorbeeld is een toestand bereikbaar met maar één transpositie verschil: slechts één tweetal vierkanten is van plaats verwisseld, terwijl de rest van het Rubikvlak onveranderd blijft?

Stel alle basisoperaties zijn even

Als beide afmetingen van het Rubikvlak 4-vouden zijn, dan bestaan alle basisoperaties uit een even aantal transposities. In dit geval kan nooit een toestand ontstaan met een oneven aantal transposities, dus ook niet met maar één transpositie. Maar ook in een Rubikvlak van bv 6*6 of 6*10 is één transpositie onmogelijk, hoewel alle basisoperaties oneven zijn!

Hoe moeilijk is het om de begintoestand te herstellen

Hoe moeilijk is het om een willekeurige toestand terug te brengen naar de begintoestand?

Begrippen

Zij G de permutatiegroep van een bepaald Rubikvlak die wordt gegenereerd door de basisoperaties op dat vlak. De operaties van G corresponderen met de verzameling toestanden van het vlak die bereikbaar zijn vanuit de beginsituatie: een baan van het Rubikvlak. Deze verzameling is een deelverzameling van alle mogelijke toestanden van het Rubikvlak. Toestanden die niet tot deze verzameling behoren kunnen niet worden gemaakt met een serie basisoperaties. Zij B de baan van een zekere begintoestand b. Voor elke toestand t in B is er dus een g in G zodanig dat t=gb

Een lijn van het Rubikvlak is een rij of een kolom.

Een transpositie is de verwisseling van twee vierkanten. Een basisoperatie kan worden beschouwd als een serie disjuncte transposities. Het omkeren van een lijn van 2n vierkanten is dan een serie van n transposities. Alle basisoperaties zijn hun eigen inverse, dus hebben orde 2.

Een operatie g is even als het aantal transposities in g even is. Een toestand t=gb is even als g even is.

Banen van de vierkanten

Een vierkant van het Rubikvlak kan alleen verplaatst worden naar een van de overeenkomstige posities in het vlak. Die posities vormen de baan van het vierkant. De vierkantsbanen zijn per definitie disjunct. Zij vormen tezamen een partitionering van het Rubikvlak. Laat door het midden van de rijen en het midden van de kolommen twee coördinaatassen lopen. Dan is direct in te zien dat vierkanten tot dezelfde baan behoren dan en slechts dan als zij symmetrisch liggen t.o.v. de coördinaatassen. De vierkanten die niet op een coördinaatas liggen hebben 4 posities, dus een baan met lengte 4. Op elke positie heeft een vierkant maar één oriëntatie. De vierkanten op een van de coördinaatassen hebben 2 posities met per positie 2 oriëntaties, een vierkant in de "oorsprong" heeft maar één positie met daar 4 oriëntaties. Om dit onderscheid voor het vervolg te vermijden splits ik een lijn op een coördinaatas in tweeën. Dan hebben alle vierkanten een baanlengte 4 en zijn de oriëntaties niet van belang omdat een vierkant per positie maar één oriëntatie heeft. Door het tweetal lijnen dat door zo'n splitsing ontstaat uitsluitend als één geheel om te draaien is het aantal mogelijkheden in dit geval beperkter dan in een Rubikvlak met dezelfde even afmetingen zonder dat een splitsing heeft plaats gevonden. Het Rubikvlak bestaat nu uit vier kwadranten. Elke vierkantsbaan bestaat uit een vierkant in elk daarvan.

Toestand van een vierkantsbaan

Zij de toestand van een vierkantsbaan de serie transposities in de baan t.o.v. de begintoestand. Een baan, d.w.z. de toestand van een baan is even als het aantal transposities vanuit de begintoestand in de baan even is.

Definitie van een Rubikvlak

Een Rubikvlak is een rechthoek bestaande uit een even aantal rijen en kolommen. Op het vlak zijn als basisoperaties gedefinieerd het omkeren van één rij of één kolom. Alle lijnen (rijen en kolommen) kunnen apart worden omgekeerd.

Stelling: Bereikbare toestanden

Een toestand is bereikbaar vanuit een bepaalde begintoestand dan en slechts dan als op alle lijnen van het Rubikvlak de vierkantsbanen allemaal even of allemaal oneven zijn, behalve de banen van de kruispunten van twee oneven lijnen: die vierkantsbanen zijn even.

Bewijs

In de begintoestand klopt de stelling: er zijn geen transposities, alle vierkantsbanen zijn even. Stel dat de stelling klopt in een bepaalde, willekeurige toestand van het Rubikvlak. Een basisoperatie verandert de toestand van alle vierkantsbanen met vierkanten op de betreffende lijn van even in oneven of omgekeerd. Er zijn twee mogelijke situaties:

• De lijn was oneven

de betreffende vierkantsbanen worden nu even, behalve op de kruispunten met oneven lijnen: de banen van die vierkanten waren even en worden hierdoor oneven. De stelling blijft voor alle vierkantsbanen kloppen.

• De lijn was even

de betreffende banen worden nu oneven, behalve op de kruispunten met oneven lijnen: de banen van die vierkanten waren oneven en worden hierdoor even. De stelling blijft voor alle vierkantsbanen kloppen.
qed

Slechts een enkele transpositie

Een toestand met maar één enkele transpositie is alleen bereikbaar als het Rubikvlak slechts 2 rijen of 2 kolommen heeft. Stel het is een Rubikvlak van 2 rijen bij 2k kolommen. Dan bestaat het omkeren van een kolom uit niet meer dan één transpositie. Het verwisselen van 2 vierkanten uit een rij kan worden gerealiseerd met de reeks basisoperaties:

1. keer een willekeurige kolom, zeg kolom x;
2. keer de bovenste rij
3. keer kolom x
4. keer de bovenste rij
5. keer kolom x

Met deze reeks operaties vindt slechts één transpositie plaats: in de bovenste rij wordt het vierkant in kolom x verwisseld met het vierkant aan de andere kant van de y-as.
De stelling geeft echter een veel sterkere beperking voor de bereikbare toestanden van het Rubikvlak, dan alleen dat een toestand met maar één enkele transpositie in het algemeen niet bereikbaar is!

Literatuur

ruwix.com: een uitgebreide verzameling gegevens over de Rubikkubus en allerlei varianten daarop.
Rogier Bos, Susanne Tak: "Symmetrie in telproblemen en puzzels". In deze Epsilon uitgave wordt in een eindopgave de "floppy cube" besproken. Dit is geen kubus, maar een Rubikvlak van 3*3.