Hacker News Reader

Comment by simonebrunozzi | Hacker News Reader

I am not a math genius, but I spent a few minutes thinking about the locker problem.

It seems to me that:

1) Every locker essentially is open (let's say "1"), and it will switch to the other binary state ("0" from 1, or 1 from 0) a number of times.

2) The number of switches is based on number of factors that comprise that number, minus one. E.g. position 1 = zero switches. Position 2 = one switch. Position 3 = one switch. Position 4 = two switches. Position 5 = one switch. Position 6 = three switches. And so on.

Am I correct?

In case, the final result is something like: 100100001000000... Which is essentially 1 + a number of zeros equal to two, then four, then six, then eight, etc.

Edit: I've now continued reading the article and, well, the solution is down there. In a way, it seems I was correct.

View on HN

He said the perfect squares are the only ones with an odd number of factors, which doesn't make sense to me. 16 for example has 4, 25 has 5, 36 has 4 again, so I'm not sure what he was getting at.

16: 1 2 4 8 16 (5)

25: 1 5 25 (3)

36: 1 2 3 4 6 9 12 18 36 (9)

So is this the right answer?

Yes. Not too hard to confirm with a tiny little program:

    lockers = ['Closed'] * 101
    for i in range(1, 101):
      for locker in range(i, 101, i):
        lockers[locker] = 'Open' if lockers[locker] == 'Closed' else 'Closed'

    print ([locker for locker, value in enumerate(lockers) if value == 'Open'])

    >>> [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

The first door will only be flipped once, by the first person. The fourth door will be flipped by the first, second, and fourth people (three times). The ninth door will be flipped by the first, third, and ninth people (three times). The sixteenth door will be flipped by the first, second, fourth, eighth, and sixteenth people (five times). The twenty-fifth door will be flipped by the first, fifth, and twenty-fifth people (three times). The thirty-sixth door will be flipped by the first, second, third, fourth, sixth, ninth, twelfth, eighteenth, and thirty-sixth people (nine times).

It should be clear here that the number of times the nth door is flipped is the number of unique divisors that n has.

For any non-perfect square n, for any divisor p, n/p = q is another divisor not equal to p. So non-perfect square numbers have an even number of divisors.

Perfect square numbers are the only numbers that have an odd number of divisors, which in this game corresponds to being flipped an odd number of times.

You could take this a step further. For any number of lockers/kids, if you start at 1 and square each number until you get a number that exceeds the number of lockers/kids, you've found all of your perfect squares in that range. Which, of course, is the square root of your original number, rounded down to the nearest whole number.

So, for any number of lockers/kids, n, the number of open doors is simply floor(sqrt(n)).

One easy way to see this: if d is a factor of n, then n/d is a factor of n (since d divides n evenly). So, for any integer, we have pairs of factors (d and n/d) and thus an even number of factors, except in the case when d and n/d are the same.

When are they the same? When d = n/d, or d^2 = n (n is a perfect square). Therefore, only perfect squares have an odd number of factors (2 * the number of pairs of factors + 1).

Where can I find math problems like this? I'm taking Calculus 2 would like to challenge myself with similar problems.

Reply on news.ycombinator.com