Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  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. Standard member Palynka
    Upward Spiral
    08 Oct '09 13:15
    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"?
  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. Standard member 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:18 / 1 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. Standard member Palynka
    Upward Spiral
    09 Oct '09 09:24 / 1 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:20 / 1 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.