My latest column for Quanta Magazine brings the exciting story of superpermutations down to the level of high school counting.
A superpermutation is a string of symbols in which each permutation, or arrangement, of those symbols appears in some order. Imagine, for example, you are trying to thwart the evil plans of a mad scientist and must key in a secret passcode:
Suddenly, inspiration strikes. If you punch in 123451, you’re actually trying two codes: 12345 and 23451. Even better, entering 1234512 will succeed if the code is 12345, 23451 or 34512.
You do some quick calculations. Instead of keying in 600 digits to cover all the possibilities, you now only have to enter 153 digits. You have just enough time — and it works! You’ve saved the day. It’s a good thing you read about “superpermutations” in Quanta.
Finding minimal length superpermutations is a open research problem in mathematics, but recent developments have come from the most unlikely of places! Find our more by reading the article, which is freely available here.
