_AHA! Puzzle This By Michael H. Pryor

MAKE’s favorite puzzles. (When you’re ready to check your answers, visit makezine.com/10/aha.)

down position, or from the down position to the up position). You may choose which switch to toggle;

however you must toggle one and only one switch, and I’m not telling you which position they are in to start with. Afterward, you will be led back to the dungeon, and I will continue selecting maidens and forcing them to toggle a switch. My selection of maidens each time will be random, meaning I may even take the same person up the tower multiple times.” “When you think that all of you have visited the tower at least once, any one of you may state that this has happened. If you are correct, you will all be freed. If you are wrong, you will be locked in the dungeon forever.”

“You will have one chance now to confer with each other and devise a plan. After that, you will be kept in separate cells and have no chance at further communication.”

The maidens come up with a plan using only the switches to communicate. Using this plan they will be able to say with 100% certainty that each maiden has visited the switch room. The maidens will not be able to speak to each other or communicate in any other way besides looking at the position of the switches in the tower. What is their plan?

Switch or Miss

Late one night, an evil witch rounds up 23 maidens from the surrounding village and makes them prisoners in her dungeon. The next morning she tells the maidens she will free them if, and only if, they can pass the test she has devised.

A room in the tower of the castle has two switches (we’ll call them switches A and B). The witch says, “Whenever I feel like it, I will lead any one of you to the top of the tower and make you toggle one of the switches (either move it from the up position to the

Seat Shuffle

A line of 100 passengers is waiting to board a plane. They each hold a ticket for one of the 100 seats on that flight. (For convenience, assume that the nth passenger in line has a ticket for seat number n. For example, the first person has a ticket for seat #1, etc.)

Unfortunately, the first person in line is crazy, and will ignore the seat number on their ticket, picking any random seat out of all 100 seats to occupy. All of the other passengers are quite normal, and will go to the proper seat unless it is already occupied. If it is occupied, they will then find a free seat to sit in at random.

What are the chances that the last (100th) person to board the plane will sit in the proper seat (#100)?

Michael Pryor is the co-founder and president of Fog Creek Software. He runs a technical interview site at techinterview.org.

Illustrations by Roy Doty

122 Make: Volume 10