math problem

In 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?

Does the second, third and fourth start with the first?

e.g. if the first 3 lockers are "open,open,open", does the second guy change them to "close, open, close" or "open,close,open"?

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);

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);

And 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.

Consider 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

Originally posted by Palynka
This is not the project Euler thread... 😵

Now try using least common multiples.

Originally posted by Zahlanzi
"Now try using least common multiples"
everyone will be doing that, no fun.

Lets defeat the coders
Say the school has 2^32 + 5 lockers
and the first 23 boys change the locker state

Originally posted by iamatiger
Lets defeat the coders
Say the school has 2^32 + 5 lockers
and the first 23 boys change the locker state

Originally posted by Thomaster
Are you asking a student to open 4.294.967.301 locker?!

It'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.

Originally posted by iamatiger
Err, yes, it does look a bit hard, I haven't worked out the answer myself yet!

Hmm, 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.