There are 100 prisoners in 100 separate locked cells. During the night each of 100 prisoner 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?

Solution

A cell will remain unlocked in the morning if it has been visited by an odd number of prison officers during the night. Let's look at a particular cell $n$. It will be visited by an officer for every number $a$ that divides $n$ (including $a=1$ and $a=n$). If $a$ divides $n$, then so does $n/a$. Thus, divisors of $n$ come in pairs $(a,n/a)$. If $n$ is not a square number, then each such pair is made up of distinct numbers. So, if $n$ is not a square number, then cell $n$ is visited an even number of times and therefore ends up locked. If $n$ is a square number, then the cell is visited an odd number of times and remains unlocked in the end. There are 10 square numbers up to and including 100, so the answer is 10.

---

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

Back to original puzzle