# math problem

wormer
Posers and Puzzles 08 Oct '09 12:14
1. 08 Oct '09 12:14
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?
2. Palynka
Upward Spiral
08 Oct '09 13:15

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"?
3. 08 Oct '09 14:02
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);
4. Palynka
Upward Spiral
08 Oct '09 14:54
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);
This is not the project Euler thread... ðŸ˜µ

Now try using least common multiples.
5. 08 Oct '09 16:34
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.
6. 08 Oct '09 20:181 edit
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
7. 09 Oct '09 07:15
Originally posted by Palynka
This is not the project Euler thread... ðŸ˜µ

Now try using least common multiples.
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)

"Now try using least common multiples"
everyone will be doing that, no fun.
8. Palynka
Upward Spiral
09 Oct '09 09:241 edit
Originally posted by Zahlanzi
"Now try using least common multiples"
everyone will be doing that, no fun.
Dude, most of us can also write a code to solve this in a few minutes.

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. ðŸ˜µ
9. 09 Oct '09 20:32
Lets defeat the coders
Say the school has 2^32 + 5 lockers
and the first 23 boys change the locker state
10. 13 Oct '09 21:201 edit
11. 14 Oct '09 14:12
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
Are you asking a student to open 4.294.967.301 locker?!
12. 15 Oct '09 08:08
Originally posted by Thomaster
Are you asking a student to open 4.294.967.301 locker?!
Err, yes, it does look a bit hard, I haven't worked out the answer myself yet!
13. 16 Oct '09 17:31
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.
14. 16 Oct '09 19:14
Originally posted by iamatiger
Err, yes, it does look a bit hard, I haven't worked out the answer myself yet!
I'm running a problem to solve it, but it looks like it will take 40 cpu hours on my notebook pc!
15. 17 Oct '09 02:39
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.