Doors Toggling Problem.

Today we will discuss a puzzle which is very interesting as its end result is mathematically elegant and intuitive.

There are 100 doors initially kept in closed state. One has to go through 100 iterations and in each iteration, he has to toggle a certain set of doors given by the rule below:


In 'i'th numbered iteration, he has to toggle the doors i, 2i, 3i, 4i, .. n * i. where n * i <= 100 < (n + 1) * i. For instance, in 3rd iteration, doors to be toggled are 3, 6, 9 ... 99.

By toggling, it means if the door is closed it has to be opened and if it is opened, it has to be closed.

Given that, question is after 100 iterations, which are all the doors would be in open state. Please stop reading if you want to try this puzzle on your own.

First off, door would be in OPEN state, if it had been toggled for odd number of times otherwise it would be in CLOSED state. I hope this is clear. This is very essential to understand the following.

Let us try some simple cases now. The first door wouldn't be toggled further, after 1st iteration which means one of the doors in open state after 100 iterations, is first door. Second door would be toggled in 2 iterations, namely first and second. So, it would be in closed state. Third would be toggled in iterations 1, 3 and would be in closed state. Fourth would be toggled in iterations 1, 2, 4 and would be in opened state. Now you could see the pattern clearly.

A 'N'th numbered door would have been toggled in an iteration 'i' if 'i' is a divisor of 'N'. Number of times a door toggled is the total number of divisors of door's number. For door 1, only one divisor is there which is again 1. For door 4, divisors are 1, 2, 4.

So, this question boils down to the simplified version: what are all the numbers( < 100) contains odd number of divisors.

Number theoretically, for what numbers tau(n) is odd. I will discuss Number theoretic functions in a different post.

Generally, if a number 'N' is divisible by 'n' and it would be divisible by (N / n) also. That means number of divisors would come in pair. But if a number is a square number like 25 which has divisor 5 and pair ( 25 / 5) is also 5, then it has odd number of divisors.

All square numbered doors like 1, 4, 9 ... 81, 100 would be in OPEN state and others in CLOSED state.


So, the number of opened doors after 100 iterations is 10. If you simulate the puzzle in computer, the program would be of complexity O(n * H[n]) where H[n] is 'n'th harmonic number.

http://en.wikipedia.org/wiki/Harmonic_number

In this naive approach, 1st iteration has to toggle 100 doors, 2nd 50 doors, 3rd 33 doors .... 100th 1 door.

So, total number of toggles would be ( 100 + 50 + 33 + 25 ... 1) => 100( 1 + 1/2 + 1/3 ... + 1/100), which is 100 * H(100) . I am attaching the code in Java. Remove the comments if you want to check the complexity in terms of iterations.


public static void main(String[] args)
{
List<Boolean> doorState = new ArrayList<Boolean>();
for(int i = 0; i <= 100; i++)
doorState.add(false);
// int totalIterations = 0;
for( int i = 1; i <= 100; i++)
{
// int innerIterations = 0;
for( int j = i; j <= 100; j += i)
{
Boolean state = doorState.get(j);
doorState.set(j, !state);
// totalIterations++;
// innerIterations++;
}
// System.out.println(innerIterations);
}
// System.out.println(totalIterations);
System.out.println("Following doors would be open: ");
for(int i = 1; i <= 100; i++)
{
if(doorState.get(i))
{
System.out.println(i);
}
}
}


Thanks for Reading.