xxix. 100 Doors (Lockers)

Problem. $n$ closed doors; on pass $k=\mathrm{1..}n$ you toggle every $k$-th door. Which doors end open?

Answer: exactly the perfect squares, so $\lfloor \sqrt{n}\rfloor$ doors (10 of 100).

long long openDoors(long long n) { long long r = sqrtl((long double)n); while (r * r > n) r--; while ((r + 1) * (r + 1) <= n) r++; return r; }

Proof: door j is open iff j is a perfect square

Door $j$ is toggled once for every divisor $k$ of $j$, so it ends open iff $d(j)$ is odd. Divisors pair up as $(k,j/k)$; the pairing is perfect unless $k=j/k$, i.e. $j$ is a square, which leaves one unpaired divisor. Hence $d(j)$ is odd iff $j$ is a perfect square. Checked by simulation for all $n\le 2000$.

Related: Arithmetic Functions.