pull down to refresh

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!
reply
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!
reply
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.
reply
The squares are exactly those numbers with an odd amount of factors. Because the amount is odd, they are now open.
reply
That makes a ton of sense
reply
Indeed! 👍
reply
There is an intuitive argument. But I'll give it some more time before divulging it.
reply
Fair enough
reply
TIL: a one liner to toggle a variable between values of 0 and 1. Elegant.
a[j] = 1 - a[j]
reply
42 is open. The rest are closed.
reply
that is open, there may not be any.
reply
0 sats \ 0 replies \ @Roll 2 Nov
None
reply