The Locker Problem Extended

The original locker problem shows us that the lockers with numbers that have an odd number of divisors stay open. Since the lockers are closed at the start all the lockers that are handled by odd number of students will remain open.

The perfect squares are the only numbers that can have an odd number of divisors. So the students with square numbers have to be absent.

Since they are absent, all the multiples of the square numbers will also have to be absent.

Let us see why. The square number 4 has 3 divisors 1,2 ,4 so 4 must be absent. Since 4 is absent consider what happens to 8. The divisors of 8 are 1, 2, 4, 8. Since 4 is absent, 8 now has an odd number of divisors so 8 also has to be absent. Same for 12 and all multiples of 4. For eg 16 has divisors 1, 2, 4, 8,16. we know 4 and 8 are both absent so 16 now has 3 divisors and therefore must also be absent.

These numbers are called Squareful numbers. In other words all the numbers that have repeated factors will all be absent.

Multiples of 4 --- 25 numbers

Multiples of 9 --- 9 numbers not counting 36 and 72

Multiples of 25 ---3 numbers not counting 100

Multiples of 49 -- 2 numbers

Total 39 students were absent.

Let $s(n) = 1$ if student $n$ is present, and $0$ is student $n$ is absent.

It's not too difficult to see that Locker $n$ is closed if and only if an even number of students change its state. Also, the state of Locker $n$ is changed by Student $k$ if and only if $k | n$ . Hence, for each locker $n \neq 1$ , we must have $s(k) = 1$ for an even number of numbers $k$ which are factors of $n$ .

$\underline{Lemma:}$ $s(n) = 1$ if and only if the integer $n$ is square-free. (square-free means it is not divisible by any perfect square $\ge 4$ ).

$\underline{Proof:}$

I will use strong induction to prove this fact.

Base Case: When $n = 1$ , the only factor of $1$ is $1$ . So, since Locker $1$ is opened, Student $1$ must be there to open it. Hence $s(1) = 1$ .

Strong Induction Hypothesis: Suppose that for all $1 \le i < k$ for some fixed $k$ , we have $s(i) = 1$ if and only if $i$ is square-free.

Case (1) : Suppose $k$ is square-free

Since $k$ is square-free and $k > 1$ , it must have an even number of divisors, and logically all of its divisors are also square-free. By the induction hypothesis, all of its proper divisors are not absent, and there is an odd number of them. Hence, in order for Locker $k$ to be closed, $k$ must also not be absent, so $s(k) = 1$ .

Case (2): Suppose $k$ is not square-free.

Let $f(n)$ represent the product of all primes $p$ which divide $n$ . (for example, $f(72) = 2 * 3 = 6$ ). We can quickly derive three important properties: (a) All square-free factors of $n$ are also factors of $f(n)$ ; (b) All factors of $f(n)$ are square-free, including $f(n)$ itself; and (c) if $n$ is not square-free, then $1 < f(n) < n$ .

By the induction hypothesis, proper divisors of $k$ are not absent if and only if they are square-free, and by (a) and (b), these numbers are exactly the factors of $f(k)$ . Now since $f(k)$ is square-free and $f(k) > 1$ , then $f(k)$ has an even number of divisors. Hence, $k$ has an even number of proper divisors that are not absent. Therefore, for Locker $k$ to be closed, Student $k$ must be absent. Hence $s(k) = 0$ .

Therefore $s(k) = 1$ if and only if $k$ is square-free. Hence the induction is complete.

QED

If $n \ge 1$ , suppose that the prime factorization of $n$ is $n \; = \; p_1^{a_1}p_2^{a_2} \cdots p_k^{a_k} \;.$ The factors of $n$ which themselves have no repeated prime factors are of the form $\prod_{i\in S} p_i$ for any subset $S$ of $\{1,2,\ldots,k\}$ . Thus $n$ has $2^k$ (an even number of) such factors.

Thus, if the students who are present are precisely those whose index has no repeated prime factor, then every door with index greater than $1$ will have its state changed an even number of times, and end up closed. On the other hand, the first door will only have its state changed once, so will end up open.

The students who are absent are those whose index has a repeated prime factor. There are $39$ such numbers between $1$ and $100$ .

Once again, not a true number theory answer, but Octave/Matlab brute forced answer:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

% 0 = open
% 1 = closed

% i is locker number (a(i) is locker state)
% j is "current student" and multiples

% Student 1 is skipped for convinience (a = zeros, i =/= 1)

a = zeros(100,1);
b = 0;

for i = 2:100

    if a(i) == 0

        for j = 1:100

            if rem(j,i) == 0 % every multiple of student number

                if a(j) == 0 % close if open
                    a(j) = 1;
                elseif a(j) == 1% open if closed
                    a(j) = 0;
                else
                    disp 'error: a(j) =/= 0 or 1'
                end

            end
        end

    elseif a(i) == 1
        b = b + 1; % Student was absent, add one to count.

    else
        disp 'error: a(i) =/= 0 or 1'

    end
end

b

OUTPUT: b = 39

I chose not to include variable 'a' here, but I did check it to make sure it was '0' followed by 99 '1's.