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!
It depends if the doors start locked or unlocked ;)
"There are 100 prisoners in 100 separate locked cells."
Is there a similar site dealing with English comprehension? ;)
They start locked! :)
They all started locked
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
That would be: 10 prisoners...
Javier Novoa C.
jstitch @ gmail . com
Could you do it with 50 cells and get the same result just not including the numbers above fifty?
if there were 1,000 prisoners would the 400th prisoner escape and why ?
Please respond i really need help with this. :)
I realized that if any cell had an even number of factors, it would be locked by the end. I remembered from Grade 7 that the only numbers that have an odd number of factors (including 1 and themselves) are the square numbers.
For any non-square numbered cell, any cell C will be visited by both warden A and warden B such that A*B=C. That means there's an even number of such wardens therefore the cell is locked. However if we take cell 100 for example, warden 10 will visit cell 100 only once, he is his own correspondent. Therefore for square numbered cells, there will be an odd number of wardens (factors) visiting the cell, so it will be unlocked. There are 10 square numbers between 1 and 100, therefore the answer is 10 prisoners free!
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.
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!
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.
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
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, 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.
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.
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)
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
'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.
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,
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).
Can you do it for 1000
Out of 1000 prisoners, 31 prisoners will be released (1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484,529,576,625,676,729,784,841,900,961)
There will be 10 prisoners who wold escape in cell no.
1, 4, 9, 16, 25, 36, 49, 64, 81, 100
They are all perfect squares and have odd number of multiples
If there were 1,000 prisoners would the 400th prisoner escape.
Here is the puzzle could someone work it out and and respond to me please I am really confused with this:
In Transum prison there are 1000 prisoners in cells numbered 1 to 1000.
On day 1, the guard turns the key in every lock to open every cell.
On day 2, the guard turns the key in every cell which is a multiple of 2. This locks all the even numbered cells.
On day 3, the guard turns the key in every cell which is a multiple of 3, locking or unlocking them.
On day 4, the guard turns the key in every cell which is a multiple of 4, locking or unlocking them.
This continues for one thousand days. The prisoners whose cells are open after the 1000th day are set free. Which prisoners will be set free?