Simple question that I can't solve

Question

Here is a relatively simple question that I'm unable to solve :/

There are $10000$ closed lockers in a hallway. A man begins by opening all $10000$ lockers. Next, he closes every $2^{nd}$ locker. Then he goes to every $3^{rd}$third locker and closes it if it is open or opens it if it is closed. After his $10000^{th}$ pass in the hallway, in which he toggles only locker number $10000$, how many lockers are open?

Any insight anyone?

Answer 1

Hint: Locker $n$ will be toggled on pass $k$ if and only if $k$ divides $n$. For every $k$ that divides $n$, you can try to pair $k$ with $n/k$ so the locker toggles generally come in pairs, canceling each other out. For given $n$, almost all $k$ will be paired with a $n/k$ distinct from $k$. When can it happen that a $k$ dividing $n$ does not produce a distinct pair?

Answer 2

Others are helping you get the (nice) mathematical solution. Here is a Python 3 code with which you can test your result:

n = int(input("How many lockers? "))
lockers = [1]*n
for i in range(2, n+1):
    for j in range(i-1, n, i):
        lockers[j] = 1 - lockers[j]
print(sum(lockers))

A bit more informative is this:

n = int(input("How many lockers? "))
lockers = [1]*n
for i in range(2, n+1):
    for j in range(i-1, n, i):
        lockers[j] = 1 - lockers[j]
    print(lockers)
print(sum(lockers))