- 08 Oct '09 12:14In a school there are 1000 lockers. The principle of this school takes 4 students. He tells the first one to open every locker, the second one to close every second locker, the third one to open or close every third locker finally the forth one to open or close every forth locker. After these round ups how many lockers will be open?
- 08 Oct '09 14:02bool[] lockers=new bool(1000);

for(int i=0;i<1000;i++)

{

lockers[i]=true;

}

for(i=0;i<1000;i+=2)

{

lockers[i]=false;

}

for(i=0;i<1000;i+=3)

{

lockers[i]=!lockers[i];

}

for(i=0;i<1000;i+=4)

{

lockers[i]=!lockers[i];

}

int openedLockers=0;

for(i=0;i<1000;i++)

{

if(lockers[i])

{

openedLockers++;

}

}

System.Console.WriteLine("This how many lockers opened: ",openedLockers); - 08 Oct '09 14:54

This is not the project Euler thread...*Originally posted by Zahlanzi***bool[] lockers=new bool(1000);**

for(int i=0;i<1000;i++)

{

lockers[i]=true;

}

for(i=0;i<1000;i+=2)

{

lockers[i]=false;

}

for(i=0;i<1000;i+=3)

{

lockers[i]=!lockers[i];

}

for(i=0;i<1000;i+=4)

{

lockers[i]=!lockers[i];

}

int openedLockers=0;

for(i=0;i<1000;i++)

{

if(lockers[i])

{

openedLockers++;

}

}

System.Console.WriteLine("This how many lockers opened: ",openedLockers);

Now try using least common multiples. - 08 Oct '09 16:34And remember to index your arrays as well...

Roughly speaking:

Divisible by 2, 3, 4 = 1/12 of the total

2, 3, not 4 = 1/12

2, not 3, 4 = 1/6

2, not 3, not 4 = 1/6

not 2, 3, 4 = 0

not 2, 3, not 4 = 1/6

not 2, not 3, 4 = 0

not 2, not 3, not 4 = 1/3

Lockers will be open if they are divisible by an even number of 2, 3, 4

So:

2, 3, not 4 (1/12)

2, not 3, 4 (1/6)

not 2, 3, 4 (0)

not 2, not 3, not 4 (1/3)

=> Total = 7/12

Out of 1000, there'll be about 583. There are going to be rounding errors (partly affected by the answer to Palynka's question above), but I can't be bothered working those out! I reckon that'll be accurate +- 1 or 2. - 08 Oct '09 20:18 / 1 editConsider the locker number modulo 12 (LCM of 2,3,4)

A locker must have an even number of divisors out of the set {2,3,4} to stay in the open state the first boy puts it in.

if the locker number is 1 mod 12, then nothing divides it, locker is open

if 2 mod 12 then, 2 divides it, locker is closed

if 3 mod 12, 3 divides it, locker is closed

4 => 2, 4, : open

5 => none : open

6 => 2, 3 : open

7 => none : open

8 => 2, 4 : open

9 => 3 : closed

10 => 2 : closed

11 => none : open

0 => 2, 3, 4 : closed

Therefore out of every 12 lockers, 7 are open and 5 are closed

There are 83 12s in 100, and 83 12's is 996

997 is 1 mod 12 : open

998 is 2 mod 12 : closed

999 is 3 mod 12 : closed

1000 is 4 mod 12 : open

So the number of open lockers is 83 * 7 + 2 = 583

nice one mtthw - 09 Oct '09 07:15

this is isn't such an awesome problem to find an elegant math solution. brute force is much simpler and with a basic c compiler, done in 3 minutes.(as long as it takes to write and compile. 5 if you download the c compiler)*Originally posted by Palynka***This is not the project Euler thread...**

Now try using least common multiples.

"Now try using least common multiples"

everyone will be doing that, no fun. - 09 Oct '09 09:24 / 1 edit

Dude, most of us can also write a code to solve this in a few minutes.*Originally posted by Zahlanzi***"Now try using least common multiples"**

everyone will be doing that, no fun.

But, fair enough, you're right that this is a problem that is adequate to solve by coding. I'm sorry if I sounded like the P&P security force. - 16 Oct '09 17:31It's easier to think about if you visualize it (for me at least!)

Only boys 3 and 4 are causing any problems because they are both opening and closing lockers. Let's start with the configuration after boy 2 has gone through:

O= open

L= closed (to avoid confusion between O and C, which I find to be distracting...)

After boy 2 goes through, the configuration of the first 33 lockers looks like this:

O L O L O L O L O L O L O L O L O L O L O L O L O L O L O L O L O

Now, we let boy 3 go through and do his thing, we are left with the configuration:

O L L L O O O L L L O O O L L L O O O L L L O O O L L L O O O L L L

Now, since we're going to be concerned with what the fourth boy is going to do to every fourth locker, we can group them into groups of four:

{OLLL} {OOOL} {LLOO} {OLLL} {OOOL} {LLOO} {OLLL} {OOOL} {LLOO}

It's pretty clear the it's following some sort of pattern, namely ({OLLL} {OOOL} {LLOO}) repeats over and over again. How many times?

Well each group contains 12 lockers. 1000 divided by 12 is 83 1/3, meaning that the groups will repeat 83 times with an extra {OLLL} thrown in at the end.

Now, if we let the fourth boy do his thing, the pattern will change to:

{OLLO} {OOOO} {LLOL} (because every fourth locker changed its status)

We know that these groups repeat 83 times, plus an extra {OLLO} at the end, so we just need to count up

Each group has 7 open lockers and 5 closed lockers, so 83*7 = 581, and 5* 83 = 415, plus the additional {OLLO} gives:

583 open lockers and 417 closed lockers. - 17 Oct '09 02:39Hmm, it occurs to me to find the LCM and figure out what portion of those are open and closed. Then figure out how many are left after all the complete runs are done.

Unfortunately, this runs into a little problem in that you have 4,294,967,301 lockers, and an LCM of 5,354,228,880.

However, if you could determine the first 22 boys (LCM=232,792,560), then figuring out and swapping the state of every 23rd locker, it may be more easily solved with a mere 186,737,708 checks for the final run.