kubus
Opgave - BaMO 2001 vraag 4
Een kubus van $3\times3\times3$ wordt verdeeld in 27 eenheidscellen. Eén van deze cellen is leeg, de andere worden opgevuld met eenheidskubussen die we willekeurig labellen van 1 tot en met 26. Een legale beweging bestaat erin om een eenheidskubus te verplaatsen naar een lege naburige cel. Bestaat er een eindige rij van legale bewegingen met als resultaat dat alle eenheiskubussen met label $k$ en $27-k$ van positie zullen gewisseld hebben voor alle $k=1,2,\ldots,13$?
- login om te reageren
Oplossing
Dit is onmogelijk.
De permutatie die de 27 mogelijke cellen weergeeft ten opzichte van de begintoestand is altijd even of oneven, waarbij elke verwisseling van twee willekeurige cellen even omzet in oneven en omgekeerd.
Elke legale beweging doet dit dus ook.
We moeten 13 verwisselingen doen, de totale permutatie moet dus oneven zijn.
Kleuren we de cellen nu volgens 3D-dambordpatroon (wit-zwart met naburige cellen tegengestelde kleur).
Bij elke beweging zal de cel van het lege blokje van kleur verwisselen. Aangezien het terug moet eindigen op dezelfde plaats, moet de eindkleur gelijk zijn aan de beginkleur en moet het aantal uitgevoerde bewegingen even zijn. Dit komt overeen met een even permutatie van alle cellen.
Contradictie.