There are 100 prisoners in 100 separate locked cells. During the night each of 100 prison officers visits the cells. The first officer visits every cell. The second officer visits cells 2,4,6,... etc (every 2nd cell), the third officer visits cells 3,6,9,..etc (every third cell), the fourth officer visits every fourth cell, and so on until the 100th officer visits the 100th cell. On a visit each officer unlocks the door if it is locked or locks the door if it is unlocked. If the cell remains unlocked after all officers have completed their rounds, the prisoner can escape. In the morning, how many prisoners have escaped and why?

*This puzzle was contributed by John Rowland, an IT officer who also provides maths tuition, preparing students for examinations at GCSE and A level.*

*If you have a puzzle you think might interest Plus readers, please email us!*

## Comments

## Prison cells

It depends if the doors start locked or unlocked ;)

## "There are 100 prisoners in

"There are 100 prisoners in 100 separate locked cells."

Is there a similar site dealing with English comprehension? ;)

## 10 prisoners...

The prisoners that will be able to escape at the end of the rounds will be the numbers:

1 , 4 , 9 , 16 , 25 , 36, 49, 64, 81, 100

That is, the difference between each number of prisoner who will be able to escape increments in every odd:

1 - 4 -> 3

4 - 9 -> 5

9 - 16 -> 7

16 -25 -> 9

25 - 36 -> 11

36 - 49 -> 13

49 - 64 -> 15

64 - 81 -> 17

81 - 100 -> 19

etc...

That would be: 10 prisoners...

Javier Novoa C.

jstitch @ gmail . com

## Could you do it with 50 cells

Could you do it with 50 cells and get the same result just not including the numbers above fifty?

## 10 lucky Daltons

Each cell number 1-100 (say it k) is the product of two integers, say m*n. If k is prime, there is only one pair of (m, n); otherwise there are more.

Doors, being initially locked ("There are 100 prisoners in 100 separate locked cells."), prison officer m (m is a divisor of k) visits the cell k and unlocks it, while later prison officer n in its visit locks the cell.

Lucky cells are 10: those that have odd number of divisors, where m=n, that means no prison officer visits the cell later, which means k = perfect square

1, 4, 9, 16, 25, 36, 49, 64, 81, 100.

nikif99@gmail.com

## Excellent puzzle...

I make it 12, myself...

Using Excel to lay out the actual sequence of events, I too get 1, 4, 9, 16, 25, 36, 49, 64, 81 and 100: but I also get 66 and 99.

Try it and see!

## Jail Break

Cell 66 and cell 99 are visited even number of times by officers (No.66 by Officer no. 1,2,3,6,11,22,33 & 66 ; No.99 by officer no. 1,3,9,11,33 and 99) that means they will remain locked.

## 10 prisoners.

i didn`t use any methods in the beginning, but when i found the first 1,4,9 i saw that it was exactly the same numbers as in the chess square puzzle I just added the extra numbers,

Original chess puzzle:

1 + 4 + 9 + 16 + 25 + 36 + 49 + 64=204

3 - 5- 7 - 9 - 11 - 13- 15 difference in the numbers in the line over

2 - 2 - 2 - 2 - 2 - 2 difference in the numbers in the line over

With extra numbers:

1 – 4 – 9 – 16 – 25 – 36 – 49 – 64 – 81 – 100

3 – 5 – 7 – 9 – 11 – 13 – 15 – 17 - 19 difference in the numbers in the line over

2 – 2 – 2 – 2 – 2 – 2 – 2 – 2 – difference in the numbers in the line over

The lucky prisoners are I cell`s: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100

Hope this is somehow understandable

## 26 Prisoners

This puzzle seems to be another way of expressing the classic Sieve of Eratosthenes algorithm.

Basically, all the prisoners in prime numbered cells can escape plus the prisoner in cell 1 (which is not considered prime).

That makes 25 + 1 cells that are unlocked after all the officers have completed their rounds. Therefore 26 prisoners escape!

## But if it is a prime number,

But if it is a prime number, it will be visited twice (officer 1 and officer 'the prime number'), which means it will remain locked as the initial condition of all cells are locked.

## 10 escapees

The way I looked at first just analysing the first ten cells, I then had a look at the prime factors of the numbers from 1-20 and drew my attention to the square numbers as they resulted in having the cells open due to an odd number of prime factors and only square numbers would have an odd number as there is a repeated root. I therefore concluded that the answer was 10, cells number 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.

## Jail break

A prisoner n is visited by an officer d, if d divides n. For instance, prisoner 63 is visited by officer 7, but not by officer 8. So we have to determine the divisors of the prisoner numbers. For example, prisoner 16 is visited by officer 1, 2, 4, 8 and 16. 1 opens, 2 closes, 4 opens, 8 closes and finally, 16 opens the door for the lucky prisoner. On the other hand, prisoner 63 can not escape, because he/she has an even number of divisors: 1,3,7,9,21 and 63 and the last one closes the door. The prisoners who are allowed to escape have an odd number of divisors. Here they are (the number of divisors in brackets): 1(1), 4(3), 9(3), 16(5), 25(3), 36(9), 49(3), 64(7), 81(5) and 100(9)

Hub Boreas

## 10 escapes

You will escape if you have odd number of factors (1 and the number are also factors). A number has odd number of factors only if it is a perfect square. So, the prisoners in cells 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 will escape. Thanks

You can find similar math puzzles at www.pratikpoddarcse.blogspot.com

## 20 prisoners escape

20 prisoners escape

## the no. of prisoners who escaped is

10

## Using K

'If a cell number has k divisors, then it is visited k times. For example, cell 14 is visited by officers 2 and 14. You need to count how many numbers between 2 and 100 have an odd number of divisors.

Hope this helps. Alex.

## 10 members

there are the persons who all are visit by even number of times are locked so odd numbers only have chance to esc..

hence 10 members are esc,

## 10 prisoners

Only the cells were visited with odd number times,can the prisoners escaped.Locked cells are named from 1 to 100.The times that a cell been visited is equals to how many factors its corresponding number have.Every single number except 1 should have at least 2 factors,include 1 and the particular number itself,others should be geminations,When the gemeled number is the same one,the number of factors of this cell number is odd number.Means the prisoners in this kind of cells would escape.These numbers are 1,4(2*2),9(3*3),16(4*4),25(5*5),36(6*6),49(7*7),64(8*8),81(9*9),100(10*10).