100 doors in a row.

You have 100 doors in a row that are all initially closed. you make 100 passes by the doors starting with the first door every time. the first time through you visit every door and toggle the door (if the door is closed, you open it, if its open, you close it). the second time you only visit every 2nd door (door #2, #4, #6). the third time, every 3rd door (door #3, #6, #9), etc, until you only visit the 100th door.

Question: what state are the doors in after the last pass? which are open which are closed?
Add your possible solutions in a comment, I will put the one which will convience me here

Comments:

From way back...
By psyang on Tuesday, August 29, 2006 (UMST)

This one I first heard when I was in grade 8 about 20 years ago. Back then, I wrote a little program on my apple ][ to figure it out, then deduced the explanation from the result.

The bottom line is that a door will be open if it has an odd number of unique factors (including 1 as a factor). It will be closed if it has an even number of factors.

Knowing this, it's reasonable to deduce that a number will have an odd number of unique factors if it is a perfect square (ie. 25 has 1,5, and 25) - the squared factor only counts once.

Thus, the doors that are perfect squares (including 1) will be open, the doors that are not will be closed.

-Peter

Reply to this Comment

what about door number 6?
By themathguy on Thursday, September 28, 2006 (UMST)

Door #6 is not a perfect square nor it has 3 unique odd factors, but it is still open at the end as shown below.

So, how abt this for a solution??

Given: 100 doors, all closed

First pass: visit each door and open them

State after first pass: 100 doors, all open now

Second pass: visit all doors with multiple of 2 and close them(because we have to toggle the doors we visit)

State after second pass: Odd-numbered(1,3,5,...) doors are open, whereas even-numbered(2,4,6..) doors are close now

Third pass: visit all doors with multiple of 3 and toggle them in two different cases:

1.)odd multiples of 3 (ie. 3,9,15...) will be closed now

2.)even multiples of 3(ie. 6,12,18...) will be opened now

Final State:

Even-numbered doors that are not multiple of 3 are close: 2, 4, 8, ....

Even-numbered doors that are multiple of 3 are open: 6,12, 18...

Odd-numbered doors that are not multiple of 3 are open: 1,5,7....

Odd-numbered doors that are multiple of 3 are close: 3,9,15...

Hope this helps! Great work to this web site creators...

Reply to this Comment

Mistake!!
By Techamp on Wednesday, October 11, 2006 (UMST)

Hi theMathGuy, U have made a mistake...the door #6 would be closed finally... because... First Pass: Its opened (1) 2nd Pass : Its closed (2) 3rd Pass : Its Open (3) 6th Pass: Its Closed (6) I think the earlier soln. is convincing.
Reply to this Comment

C# program that runs this case
By vladibo on Monday, February 26, 2007 (UMST)

1=1, 2=0, 3=0, 4=1, 5=0, 6=0, 7=0, 8=0, 9=1,10=0
11=0,12=0,13=0,14=0,15=0,16=1,17=0,18=0,19=0,20=0
21=0,22=0,23=0,24=0,25=1,26=0,27=0,28=0,29=0,30=0
31=0,32=0,33=0,34=0,35=0,36=1,37=0,38=0,39=0,40=0
41=0,42=0,43=0,44=0,45=0,46=0,47=0,48=0,49=1,50=0
51=0,52=0,53=0,54=0,55=0,56=0,57=0,58=0,59=0,60=0
61=0,62=0,63=0,64=1,65=0,66=0,67=0,68=0,69=0,70=0
71=0,72=0,73=0,74=0,75=0,76=0,77=0,78=0,79=0,80=0
81=1,82=0,83=0,84=0,85=0,86=0,87=0,88=0,89=0,90=0
91=0,92=0,93=0,94=0,95=0,96=0,97=0,98=0,99=0,100=1

public static void Print(BitArray array, string str){
  FileLog.WriteLine("-----------------------------[{0}]",str);
  for(int i = 1; i <= array.Length; i++){
   FileLog.Write("{0,2}={1}",i, (array[i-1])?"1":"0" );
   if(i % 10 == 0) FileLog.WriteLine();
   else FileLog.Write(",");
  }
  FileLog.WriteLine();
}

public static void Main(string[] args) {

  BitArray array = new BitArray(100);

  int step = 0;
  while(step < 100){
   for(int i = step; i < 100; i += (step + 1)){
    array[i] = !(array[i]);
   }
   Print(array, step.ToString());
   step++;
  }

  Print(array, "END");

}

Reply to this Comment

solution
By pkiran on Monday, April 30, 2007 (UMST)

public class Reverser {

public static void main(String[] args) {
  int open = 1;
  int closed = 0;
  int [] arr;
  int j = 2;
  arr = new int[101];
  int [] mul;
  mul = new int[101];
  for(int i = 1;i<101 ;i++)
  {
   arr[i] = open;
   System.out.print(" [" + i + "]:" + arr[i]);
  }
  System.out.print("\n");

  int m = 1;
  for(j = 2; j < 100 ; j++)
  {
   for(int k = 1; k< 101; k++)
    mul[k] = j * k;

   for(int i=1; i< 101; i++)
   {
    if(i==mul[m])
    {
     if(arr[i]==open)
      arr[i]= closed;
     else
      arr[i] = open;
     m++;
    }
    System.out.print(" [" + i + "]:" + arr[i]);
   }
   System.out.print("\n");
   m = 1;
  }
  for(int i = 1;i< 101; i++)
  {
   System.out.print(" [" + i + "]:" + arr[i]);
  }
}
}

The program is in java, run this to get the solution

Reply to this Comment

100 Doors
By SantiagoICanepa on Friday, May 25, 2007 (UMST)

For each door D, count how many numbers N there are where D is multiple of N, and 1 <= N <= D

If the result is even, the door is closed

If the result is odd, the door is open

Reply to this Comment

Read the question properly
By prasanna on Thursday, June 28, 2007 (UMST)

Hi themathguy u have to pass the doors till u get that multiple of 100 not just 3 times.He has just posed example till multiples of 3.Please read the question fully
Reply to this Comment

Good one
By prasanna on Thursday, June 28, 2007 (UMST)

That was a good answer
Reply to this Comment

Siddhant
By sforsawant on Saturday, August 25, 2007 (UMST)

Answer : Doors opened will be 1 4 9 16 25 36 49 64 81 100 (all perfect square ). Here's C program to prove it : #include<stdio.h> #include<conio.h> /* 0 = door closed 1 = door opened */ void main() { int a[101],i,j; //clrscr(); for(i=1;i<=100;i++) { a[i]=0; // all door closed } for(i=1;i<=100;i++) for(j=i;j<=100;j=j+i) a[j]=(a[j]==0)?1:0; // toggle doors for(i=1;i<=100;i++) { printf("%d",a[i]); if(i%10==0) printf("\n"); } getch(); }
Reply to this Comment

The answer
By Leon on Monday, September 24, 2007 (UMST)

The answer will be: 1,4,9,16,25,36,49,81,100.

(i am a chinese , so my english is not good)

Lets see. only the number with odd factors meets the requirement.

1 : 1.

4 : 1,2,4.

9: 1,3,9.

16: 1,2,4,8,16.

why only the odd factors. its simply because change the door odd times can finally change the states of door.

Right?

Leon

Reply to this Comment

100 doors
By xy on Tuesday, October 09, 2007 (UMST)

I wrote a small program, the result I got is :

OCCOCCCCOCCCCCCOCCCCCCCCOCCCCCCCCCCOCCCCCCCCCCCCOCCCCCCCCCCCCCCOCCCCCCCCCCCCCCCCOCCCCCCCCCCCCCCCCCCO

(O: open, C: closed)

Reply to this Comment

100 door 100 times
By amitmisra on Monday, December 24, 2007 (UMST)

It's just matter of seeing the problem. Your visit is called in a perfect square way so the perfect squared gates (in 100 perfect square are 1,4,16,25,36,49,64,89,100) will be open and rest will be closed till your 100 linear passes to the 100 initially closed gates.
Reply to this Comment

Solution (common sense / math)
By matans on Tuesday, January 01, 2008 (UMST)

The state of the door depends on the number of times it will be visited as follows:
if the number of times it is visited is even - the door will end up closed
otherwise - the door will end up open

The number of times each door is visited is directly related to the number of dividers the number (door number) has (including 1 and itself).

For example, every prime number door will be visited twice, and hence ends up closed

Now, for every divisor of a number there must exist another divisor - that other devisor is the result of dividing with the first divisor! So, divisors for a number come in pairs... except for... when the number is a square of a divisor.

If the number is a square of a divisor, then it means it has one divisor - the square root - that does not have a pair. Dividing the number by it's square root yields the square root itself, and not a new divisor.

hence numbers that have an integer square root have an odd number of divisors, while numbers that do not have an integer square root do not.

Therefore only 1,4,9,16,25,36,49,64,81,100 will be open! and you don't need to write a computer program to solve this (which was certainly not the purpose of the question in an interview setting)

~Matan

Reply to this Comment

100 doors
By buddhibal on Saturday, March 08, 2008 (UMST)

This is simple XOR logic. For e.g lets do it for 10 doors. See pattern in below example. 1 2 3 4 5 6 7 8 9 10 -------------------------------- c c c c c c c c c c 1st - o o o o o o o o o o ==> XOR with all 1's 2nd - o c o c o c o c o c ==> XOR with even 1's 3rd - o c c c o o o c c o ==> XOR with every 3rd 1 4th - o c c o o o o o c o 5th - o c c o c o o o c c 6th - o c c o c c o o c c 7th - o c c o c c c o c c 8th - o c c o c c c c c c 9th - o c c o c c c c o c
Reply to this Comment

Purrfect. :-)
By Adhiraj on Wednesday, June 11, 2008 (UMST)

Purrfect. :-)
Reply to this Comment

100 Doors
By santa_02003 on Tuesday, June 17, 2008 (UMST)

Here is what i think: The door #1 will be open- Since this door will remain untouch after it open at the 1st time The door #100 will be open- i find this by using its factors: 1 2 4 5 10 20 25 50 100... Since the total number factors is an odd number... So it will be open All the doors with prime number will be closed because the doors with only be touch twice that is during the 1st try and at the number itself The door #4 will be open The rest of the doors will be closed because the # of times the door will be touch is always in even number of times
Reply to this Comment

Its easy ! :)
By AZBZCZ on Saturday, June 21, 2008 (UMST)

Hey.. here is a simple explanation.. . The door will be opened if the number of factors for the number is ODD. :) ... Let the number be N. If X is a factor of it, then X * Y = N, so Y is also a factor of it, so it will open for X and close for Y, but when Y = X ? i.e., X * X = N, it will open for X and no corresponding pair to close.. so only PERFECT SQUARES stay open :)
Reply to this Comment

Add Your Comment