Rubik’s Cube in 20 Moves or Less

Herbert Kociemba, Darmstadt, Germany

9am - 10am

Abstract:

Rubik's cube is a puzzle which gained its greatest popularity in 1980/1981. But even today it is quite popular and there exists a growing community of speedcubers who want solve a Rubik's cube as fast as possible. From the beginning there was another group of people - mostly mathematicians - who tried to develop methods how to solve a cube in as few moves as possible. The term "God's number" was coined for the smallest number of moves which will suffice to solve every Rubik's cube. But it took 30 years until 2010 to settle that this number is 20. In this lecture the development of the ideas which finally led to this proof will be discussed.

• Herbert Kociemba's homepage.

• Cool links: God's Number? Kociemba's Algorithm?

Solvable Squares: Minimally Clued Latin Square Puzzles

Daniel Katz, Brown University

10am - 11am

Abstract:

Over the last few decades, a wide variety of abstract logic puzzles have become popular around the world, with some (such as sudoku, futoshiki, and KenKen) appearing in mainstream Western publications, and others entertaining a more niche audience of constructors, solvers, and international competitors. Many of these puzzles, including the three just mentioned, present the task of completing a Latin square (an NxN grid of numbers from 1 to N with no repeats in any row or column) given a set of clues. While a puzzle constructor chooses these clues as a trail of bread crumbs to lead solvers to a solution, a mathematician can study the possible sets of clues that create valid puzzles. A puzzle with very few clues is not always interesting to solve, but the existence of these puzzles may be mathematically interesting.

In this talk, I'll briefly summarize the path that led me to a life of puzzling, and then introduce a collection of Latin square puzzle types, each with some preliminary discoveries and open questions about how they can be "minimally" clued. If time allows, I may provide a very short introduction to puzzle construction, to contrast the cluing decisions made when aiming for efficiency with the ones made in pursuit of an enjoyable solving experience.

• Dr. Katz's homepage...

• ... and puzzle page!

Math & Puzzle Hunts

Tanya Khovanova, Massachusetts Institute of Technology

3:30pm - 4:30pm

Abstract:

We are going to interactively solve a bunch of mathematically interesting puzzles. These puzzles come from the puzzle-hunt tradition, as exemplified by the venerable MIT Mystery Hunt. The critical thing about puzzle-hunt puzzles is the lack of instructions: the solver needs to figure out what to do from the content of the puzzle itself.

We will start with a relatively easy warm-up puzzle and then continue with one or two hard ones. To keep it fun and fast-paced, I will rely on you to generate the ideas, and I will take care of any tedious work that arises.

• Dr. Khovanova's homepage.

• Related video: TEDed: Can you solve the Leonardo da Vinci riddle?

Algorithmic Puzzles

Pete Winkler, Dartmouth College

4:30pm - 5:30pm

Abstract:

Many great puzzles present an algorithm for doing some task, then ask you whether that algorithm could work---and if it could, then, perhaps, whether it must work.

Since real-life problems in computational mathematics often take the same form, it is not surprising that techniques for solving such puzzles are nice to know about.  Many of the best of these techniques involve potential functions, and the puzzles you will see are designed to help you appreciate the amazing things they can do.

• Dr. Winkler's homepage.

• Related video: Puzzles That Solve Themselves.