Rubiks kub matematik

2010 bevisade ett internationellt team av forskare att oavsett hur förvrängd en Rubiks kub blev, skulle det inte kräva mer än 20 drag för att lösa det. Deras bevis förlitade sig dock på motsvarande 35 års siffror på en bra modern dator.

För kuber som är större än den vanliga Rubiks kub kan en adekvat bearbetning av startpositioner mycket väl överstiga beräkningskapaciteten för alla datorer i världen. Men i september ledde Erik Demaine (höger), en docent i datavetenskap och teknik, ett team inklusive sin far, CSAIL gästprofessor Martin Demaine (till vänster), som visade det matematiska sambandet mellan antalet kvadrater i en kub och antal drag i den kortaste lösningen till dess mest förvrängda tillstånd.

Det vanliga sättet att lösa en Rubiks kub är att hitta en kvadrat som är ur position och flytta den på plats samtidigt som resten av kuben lämnas så lite förändrad som möjligt. Det ger en värsta lösning vars antal drag är proportionellt mot N2, där N är antalet rutor per rad. Men teamet såg att under vissa omständigheter kunde en enda sekvens av vändningar flytta flera rutor på plats.

Att beskriva dessa omständigheter matematiskt var ingen lätt uppgift. Den första timmen såg vi att det måste vara minst N2/log N, berättar Erik Demaine. Men sedan tog det många månader innan vi kunde bevisa att N2/log N räckte med drag.

Dölj