Gurmeet.Net
Gurmeet.Net
Puzzles
Puzzles

Thousand Prisoners

Puzzle

A prison has 1000 cells. Initially, all cells are marked with - signs. From days 1 thru 1000, the jailor toggles marks on some of the cells: from + to - and from - to +. On the i-th day, the signs on cells that are multiples of i get toggled. On the 1001-th day, all cells marked with + signs are opened. Which cells are these?

Source

I remember hearing this puzzle sometimes in 1987, when I was in grade 9, from Samir Khosla. And I remember solving it in the football field in school.

Solution

A cell is toggled as many times as the number of divisors it has. For example, cell number 24 is toggled on days 1, 2, 3, 4, 6, 8, 12 and 24. Now, divisors come in pairs like 24 = 1*24 = 2*12 = 3*8 = 4*6. So the total number of divisors is even, except when the number is a perfect square, in which case the total number of divisors is odd. Since all cells are initially marked with - signs, only those cells that have an odd number of divisors have + signs eventually. These are cell numbers 1, 4, 9, 16, 25, 36, and so on.

Previous Puzzle: Forty-Five Minutes

How do we measure forty-five minutes using two identical wires, each of which takes an hour to burn. We have matchsticks with us. The wires burn non-uniformly. So, for example, the two halves of a wire might burn in 10 minute and 50 minutes respectively.

Next Puzzle: Non-Transitive Dice

You and your opponent shall play a game with three dice: First, your opponent chooses one of the three dice. Next, you choose one of the remaining two dice. The player who throws the higher number with their chosen dice wins. Now, each dice has three distinct numbers between 1 and 9, with pairs of opposite faces being identical. Design the three dice such that you always win! In other words, no matter which dice your opponent chooses, one of the two remaining dice throws a number larger than your opponent, on average.

12 Sep 2008
© Copyright 2008—2017, Gurmeet Manku.