Erik Demaine, an associate professor of computer science and engineering at MIT; his father, Martin Demaine, a visiting scientist at MIT’s Computer Science and Artificial Intelligence Laboratory; graduate student Sarah Eisenstat; Anna Lubiw, who was Demaine’s PhD thesis adviser at the University of Waterloo; and Tufts graduate student Andrew Winslow showed that the maximum number of moves required to solve a Rubik’s cube with N squares per row is proportional to N2/log N. “That that’s the answer, and not N2, is a surprising thing,” Demaine says.
The standard way to solve a Rubik’s cube, Demaine explains, is to find a square that’s out of position and move it into the right place while leaving the rest of the cube as little changed as possible. That approach will indeed yield a worst-case solution that’s proportional to N2. Demaine and his colleagues recognized that under some circumstances, a single sequence of twists could move multiple squares into their proper places, cutting down the total number of moves.
But finding a way to mathematically describe those circumstances, and determining how often they’d arise when a cube was in its worst-case state, was no easy task. “In the first hour, we saw that it had to be at least N2/log N,” Demaine says. “But then it was many months before we could prove that N2/log N was enough moves.”
If you liked this article, please give it a quick review on ycombinator or StumbleUpon. Thanks
Wang is a prolific business-oriented writer of emerging and disruptive technologies. He is known for insightful articles that combine business and technical analysis that catches the attention of the general public and is also useful for those in the industries. He is the sole author and writer of nextbigfuture.com
, the top online science blog. He is also involved in angel investing and raising funds for breakthrough technology startup companies.
He gave the recent keynote presentation at Monte Jade event with a talk entitled the Future for You. He gave an annual update on molecular nanotechnology at Singularity University on nanotechnology, gave a TEDX talk on energy, and advises USC ASTE 527 (advanced space projects program). He has been interviewed for radio, professional organizations. podcasts and corporate events. He was recently interviewed by the radio program Steel on Steel on satellites and high altitude balloons that will track all movement in many parts of the USA.
He fundraises for various high impact technology companies and has worked in computer technology, insurance, healthcare and with corporate finance.
He has substantial familiarity with a broad range of breakthrough technologies like age reversal and antiaging, quantum computers, artificial intelligence, ocean tech, agtech, nuclear fission, advanced nuclear fission, space propulsion, satellites, imaging, molecular nanotechnology, biotechnology, medicine, blockchain, crypto and many other areas.