4 ms·

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

• swang 10y ago
  16: 1 2 4 8 16 (5) 25: 1 5 25 (3) 36: 1 2 3 4 6 9 12 18 36 (9)
  • sfbay 10y ago
    So is this the right answer?
    • birken 10y ago
      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]
• deleted 10y ago
  [deleted]
• shaldengeki 10y ago
  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.
  • bryondowd 10y ago
    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)).
• lavrov 10y ago
  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).