You have 100 lockers, all closed, and 100 students. The first student goes and opens every locker. The second student toggles every second locker (i.e., closes lockers 2, 4, 6, …, 100). The third student toggles every third locker (i.e., opens if closed, closes if open, for lockers 3, 6, 9, …, 99), and so on, until all 100 students have passed.
At the end, which lockers will remain open?
Previous iteration: #749797 (several stackers answered correctly this time). I also updated the full answer to the integral problem from two days ago (see #750702).
Lockers 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 are open at the end, all others are closed.
I.e. the square numbers!
Code
I'd love some intuition for this result.
I get that the primes will all be closed, because only the corresponding prime'th student will toggle that locker, but I don't see a clever argument for just the squares being left.
I think the answer is in Why do perfect squares have a odd amount of factors
The squares are exactly those numbers with an odd amount of factors. Because the amount is odd, they are now open.
That makes a ton of sense
Indeed! 👍
There is an intuitive argument. But I'll give it some more time before divulging it.
Fair enough
I was about to confidently type 1, but I neglected the description about how people needed to open the lockers when they were closed during their turn. Darn it!
TIL: a one liner to toggle a variable between values of 0 and 1. Elegant.
a[j] = 1 - a[j]42 is open. The rest are closed.
Alright, let me put it simply like I’d explain it to a friend:
You’ve got 100 lockers and 100 students. Each student changes the state (open/close) of lockers based on their number — like student #5 toggles every 5th locker.
Now, here's the fun part: a locker ends up open only if it's toggled an odd number of times. And guess what? That only happens if the locker number has an odd number of divisors.
And which numbers have an odd number of divisors? Perfect squares.
Because divisors usually come in pairs like (2 × 6 = 12), but perfect squares have one unpaired divisor (like 4 × 4 = 16).
So the lockers that stay open at the end are:
1, 4, 9, 16, 25, 36, 49, 64, 81, 100 the perfect squares up to 100.
10 lockers in total stay open.
that is open, there may not be any.
deleted by author