The Locker Problem


There is a hallway of lockers with lockers numbered 1 through 100. There are also 100 students. Student 1 opens every locker, then student 2 closes every other locker, then student 3 opens or closes every 3rd locker (if it’s open then she closes it and if it’s closed then she opens it), and so on, where the nth student opens or closes every locker which is a multiple of n. (Does it matter in which order the students go down the hallway in?)

The problem: Which lockers are open after all the students walk down the hallway?

Think about it for a bit, and I’ll post a solution later.

Advertisements

16 responses to this post.

  1. Posted by Shobhit Gupta on January 24, 2011 at 1:30 am

    I started out with 10 numbers, and I noticed a pattern of the number of flips applied to each number.
    And it turns out that its totally related to the factors (or divisors) of the number.

    For example, the 4th door will be flipped 3 times:
    By Student no. 1
    By Student no. 2
    By Student no. 4

    Its the factors…

    So I checked out:
    http://www.wolframalpha.com/input/?i=Divisors+1+to+100

    And then:
    http://www.wolframalpha.com/input/?i=number+of+Divisors+1+to+100

    And then:
    http://www.wolframalpha.com/input/?i=number+of+Divisors+1+to+100+|+divisible+by+2

    So I see a bigger picture now:
    1 False
    2 True
    1 False
    4 True
    1 False
    6 True
    1 False

    until

    18 True
    1 False

    Thanks for such a thoughtful exercise.

    Reply

  2. Posted by Shobhit Gupta on January 24, 2011 at 1:35 am

    My last link (|+divisible+by+2) doesn’t open properly by clicking on it. Make sure you copy the link and paste it manually.

    Reply

  3. Yes you’re right–it’s related to the divisors of the number 🙂 I don’t understand what you mean by “1 False, 2 True”, etc. though. What kinds of numbers have lockers which end up open at the end? There’s one characterization and then an even deeper characterization. (I don’t mind if you post the answer if you have it, maybe put a disclaimer.)

    Reply

  4. Posted by Shobhit Gupta on January 25, 2011 at 5:40 am

    Oh yeah, I should have put a disclaimer in my 1st comment as well.
    Next time I will be careful about it.

    Well let me do that here:

    —————
    |SPOILER ALERT|
    —————
    My True and False meant:
    True = ‘door is closed’
    False = ‘door is open’

    But anyway, in better words, all those doors that have odd number of factors are open.

    So the final answer would be: 1,4,9,16,25,36,49,64,81,100

    Also, this is how my previous True False stuff relates…
    1 = 1
    4 = 1+2+1
    9 = 1+2+1+4+1
    16 = 1+2+1+4+1+6+1
    25 = 1+2+1+4+1+6+1+8+1
    and so on…

    Reply

  5. Posted by Shobhit Gupta on January 25, 2011 at 5:49 am

    Oh!

    Just gave more though about ‘deeper characterization’. I just noticed that the answer in above comment is actually a series of n^2.

    Now I realize that only the perfect squares can have odd number of factors. Nice!

    Reply

  6. Yes, great job! The sequence you wrote out for the squares is also equivalent to saying that n^2 is equal to the sum of the first n odd numbers (add the preceding 1 to each number and there’s a 1 at the end). In general, when you take differences of a quadratically behaving sequence (f(x) is a quadratic equation and you look at f(1), f(2), …) you get a linear sequence, and the pattern continues: take differences of a cubic and you get a quadratic, etc. Pretty neat huh?

    Experimentation is often a great way to notice patterns, and then mathematicians try to prove their assertions once they come up with them. (I see you thought like a computer programmer pulling out Wolfram Alpha 🙂 ) Can you prove why perfect squares are the only numbers with an odd number of factors? (You need to know how to find the number of factors of a number given its prime factorization.)

    Reply

  7. Posted by Jenny on January 25, 2011 at 10:28 pm

    I saw a variation on this problem – where only odd-numbered students come to flip doors. Is there a nice way count the open doors in that case?

    Reply

  8. Posted by Shobhit Gupta on January 26, 2011 at 12:38 am

    >> I saw a variation on this problem – where only odd-numbered students come to flip doors. Is there a nice way count the open doors in that case?

    I think the answer would remain same if only the odd-numbered students come to flip doors.
    I have my own simplistic reasoning for that. Will explain once someone validates my answer.

    >> Can you prove why perfect squares are the only numbers with an odd number of factors?

    Nope. I guess I will have to turn to Google for the answer 🙂

    Reply

    • Posted by Jenny on January 26, 2011 at 4:46 pm

      No, I think the answer was 53 or so…
      I tried counting it by hand (the number of odd factors numbers have) and got 33.

      Reply

  9. Okay, so the solution to the initial problem is that the only numbers with an odd number of factors are perfect squares. This is because for numbers which aren’t perfect squares factors of the form k and 2/k (so if you have 12, your pairs are {1,12}, {2,6}, {3,4}) but with squares the square root of the number isn’t part of a pair.
    In this problem, we only care about numbers with an odd number of *odd* factors. To count the number of odd factors of a number, we can just look at the number of factors of the greatest odd factor, because that includes all the other odd factors. Try solving it from here 🙂 I don’t think the answer is 17.

    Reply

  10. Posted by Jenny on February 1, 2011 at 10:42 pm

    Yes, that’s what I tried doing, but it got rather complicated…I mean, it’s all the numbers up to 100.
    Never mind, then. I was just wondering if there was a quick solution, because this was a timed test.
    And Mr. Cocoros says it’s 17 🙂

    Reply

    • Well what I’ve gathered is that for a number to have an odd number of odd factors, it has to be of the form a power of 2 times an odd power. Which isn’t too bad to count, because for one thing 4 times an odd square is a square itself so your number has to be of the form k^2 or 2k^2. And oh you’re right, it is 17 🙂 Because its just 10 perfect square up to 100 + 7 squares less than 50 so that 2k^2 is less than 100.

      Reply

  11. Posted by Shobhit Gupta on February 2, 2011 at 3:12 am

    I tried it the naive way. And I couldn’t match up 17. Maybe I did something wrong.

    But here is my calculation spreadsheet for reference: https://spreadsheets.google.com/ccc?key=0AoVtWtp1e2j5dGJvT0JPZXpsMjNDblBQLUhRX0hzZ2c&hl=en&authkey=CL6ii9cL

    Reply

  12. Posted by Shobhit Gupta on February 2, 2011 at 3:15 am

    Oh never mind, i had a wrong formula earlier. Its 17.

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: