Cells and Prisoners

Thousands of years ago, a king called Samudragupta ruled the lands of Saurashtra. He was called the king of oceans as it was almost impossible for anyone to capture his lands through the battles on seas. Once a great king from Greece, Philip II used the sea routes to capture Samudragupta. Fortunately or unfortunately Samudragupta captured Philip II and his 788 powerful army. Each captive was put into a cell starting from cell number 1. The prisoners were provided sufficient food, air and water but they had to live in dark rooms. A prisoner's number was his cell number. Philip II was in cell number 173.



On the eve of the king Samudragupta's birthday, he decided to free some of the prisoners according to a plan. Initially all the prisoners were taken out of their respective cells. The doors of all the cells were closed. According to the plan:
Prisoner 1 has to open the doors of all the cells.
Prisoner 2 has to close the doors of the cells 2, 4, 6, ...
Prisoner 3 has to visit the cells 3, 6, 9, ...
If the doors are open, he has to close.
If the doors are closed, he has to open.
Similarly, continuing we have
Prisoner i has to visit all the cells i, 2i, 3i, ...
If the doors are open, he has to close.
If the doors are closed, he has to open.
This will be continued till the last captive.
At last, the prisoners of the cells whose doors were open would be released.

The queen was very eager to know how many prisoners shall be released and whether the captured king himself be released or not. Do you have the answer for the queen's questions before the plan could be executed?


Hint 1

Simplify the problem. Consider only a few cells and check whether you can solve or not.


Hint 2

Consider 11 cells and construct a table of cells and prisoners and analyze.


Answer

Prisoners whose numbers are perfect squares in the range [1, 789] would not be released, a total of 27 people. The king Philip II would not be released.


Solution

The general rule for attacking any problem is that the problem should be simplified as much as possible. Initially consider that there are only 11 cells. Also any possible information can be organized and analyzed when it is represented as pictures, graphs, tables etc... So we draw a table consisting of cells and prisoners. There can be two states for a cell, 'open' or 'close'. From the table we can know which prisoner has changed the state of which cell.

Cells	Cell 01	Cell 02	Cell 03	Cell 04	Cell 05	Cell 06	Cell 07	Cell 08	Cell 09	Cell 10	Cell 11
Initially	Close	Close	Close	Close	Close	Close	Close	Close	Close	Close	Close
Prisoner 1	Open	Open	Open	Open	Open	Open	Open	Open	Open	Open	Open
Prisoner 2	Open	Close	Open	Close	Open	Close	Open	Close	Open	Close	Open
Prisoner 3	Open	Close	Close	Close	Open	Open	Open	Close	Close	Close	Open
Prisoner 4	Open	Close	Close	Open	Open	Open	Open	Open	Close	Close	Open
Prisoner 5	Open	Close	Close	Open	Close	Open	Open	Open	Close	Open	Open
Prisoner 6	Open	Close	Close	Open	Close	Close	Open	Open	Close	Open	Open
Prisoner 7	Open	Close	Close	Open	Close	Close	Close	Open	Close	Open	Open
Prisoner 8	Open	Close	Close	Open	Close	Close	Close	Close	Close	Open	Open
Prisoner 9	Open	Close	Close	Open	Close	Close	Close	Close	Open	Open	Open
Prisoner 10	Open	Close	Close	Open	Close	Close	Close	Close	Open	Close	Open
Prisoner 11	Open	Close	Close	Open	Close	Close	Close	Close	Open	Close	Close

Consider the king's plan as a process. When the process completes, only three cells are open which is clear from the last row. They are 1, 4 and 9. If we go through the sequence the first thing which comes to our mind is that all these numbers are perfect squares less than 11. Consider that there are only 8 cells. The cells which would be open at the end of the process are 1 and 4. Here is the list of the cells which would be open after the process is completed.

Number of cells	The cells which would be open
1	{1}
2	{1}
3	{1}
4	{1, 4}
5	{1, 4}
6	{1, 4}
7	{1, 4}
8	{1, 4}
9	{1, 4, 9}
10	{1, 4, 9}
11	{1, 4, 9}

From the above table we can predict the cells which would be open for 789 cells and for n cells:

Number of cells	The cells which would be open
789	Perfect squares in [1, 789]
n	Perfect squares in [1, n]

Perfect squares in [1, 789] = {1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 381, 400, 441, 529, 576, 625, 676, 789}. Totally there are 27 numbers.

Is there any solid proof to show that only cells of perfect square numbers will be open? Yes.
Initially all cells are closed. It is clear from the problem that the state of a cell i is changed only by the prisoners whose numbers are the factors of i. If there are even number of factors for i, then the final state of the cell is 'close'. If there are odd number of factors for i, the final state of the cell is 'open'.

Number of factors	Final state of the cell
Even	Close
Odd	Open

There is one interesting fact in Mathematics. The number of factors for a non-perfect square is even and the number of factors for a perfect square is odd. Try to prove this fact. The whole problem is an application of this seemingly incorrect and unheard fact.

i	Number of factors
Non-perfect square	Even
Perfect square	Odd

Therefore the final state of any particular cell can be determined by

i	Final State of the cell
Non-perfect square	Close
Perfect square	Open

Example 1:
Consider cell 12. The cell is initially closed. The factors of 12 are 1, 2, 3, 4, 6 and 12. The state of the cell is changed by the prisoners whose numbers are 1, 2, 3, 4, 6 and 12. As the number of factors of 12 is even, the final state of cell number 12 is 'close'.
Example 2:
Consider cell 16. The cell is initially closed. The factors of 16 are 1, 2, 4, 8 and 16. The state of the cell is changed by the prisoners whose numbers are 1, 2, 4, 8 and 16. As the number of factors of 16 is odd, the final state of cell number 16 is 'open'.

i	i	Factors	Number of factors	Final state of the cell
Non-perfect square	12	{1, 2, 3, 4, 6, 12}	Even	Close
Perfect square	16	{1, 2, 4, 8, 16}	Odd	Open

From the above discussions we have seen that prisoners whose numbers are perfect squares in the range [1, 789] were released which constitutes a total of 27 people. As the king Philip II's number was 173, he was not released. May be the king Samudragupta wanted not to release Philip II. So he made this plan. This answers all the questions of the queen.

On generalizing, if there are n cells, the cells which will be open when the plan is completed are the perfect square numbers in the range [1, n].

In the problem, all the prisoners get a chance to change the state of one or more cells. Let us modify the question a bit. Consider there are n cells and only the first root(n) prisoners are allowed to change the state of the cells and not others. Ex: For 100 cells, only the first 10 prisoners can change the state. For 77 cells, only the first 8 prisoners can change the state. Now find the number of cells which are open when the process completes.

The solution for the problem goes this way. For every cell i, where i E [1, n], the final state is shown. Let f be the number of factors of i.

i	Num of factors	Num of prisoners who change state	Final state
Non-perfect square	f = even	(f/2) = even (f/2) = odd	Close Open
Perfect square	f = odd	((f+1)/2) = even ((f+1)/2) = odd	Close Open

It is an assignment to you to find the formula for the number of factors of a natural number and to prove whatever given in the above table is right.