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 N

^{2}/log N. "That that’s the answer, and not N

^{2}, is a surprising thing," Demaine says.

(Read more.)

(I owe the pointer to Wild About Math.)

I probably should just read the original article, but I am too busy. Does this have any connection to the formula for the distribution of primes (i.e. the number of primes less than or equal to n is approx. n/ln(n)?

ReplyDeleteHi Roy. Sorry for the delayed reply... Well, no, I'm not aware of any connection. The linked MIT piece is nice but rather short, anyway.

ReplyDelete