MATLAB script to prove to you that the perfect squares are the switches that are toggled

Evidently, this problem exists in both "switch" and "locker" forms. Assume that there are 100 switches are initially off and numbered from 1 to 100.

• First, you toggle multiples of 1 (i.e., every switch gets turned on),
• and then you toggle multiples of 2 (i.e., every even-numbered switch gets turned off),
• and then you toggle multiples of 3 (i.e., switches 3, 6, 9, 12, ... are toggled),
• ...
• and then you toggle multiples of 99 (i.e., switch 99 is toggled),
• and then you toggle multiples of 100 (i.e., switch 100 is toggled).

After this process, which switches are "on"?

Examining the problem, you notice that switches are toggled the same number of times as they have unique factors. For example, switch 6 is toggled 4 times, which corresponds to its unique factors, 1, 2, 3, and 6. However, switch 4 is toggled only 3 times, which corresponds to its unique factors, 1, 2, and 4 (i.e., even though 4 = 2 × 2, the factor 2 is only represented in the list once because it is duplicated). Moreover, it is only the perfect squares (1, 4, 9, 16, 25, 36, 49, 64, 81, 100) that will have repeated factors (i.e., their whole square roots), and so it is only those switches that will be flipped and odd number of times. Furthermore, it is only those switches that will be "on" after this game.

To verify this to yourself, use a MATLAB script:

% All switches initially off
switches = zeros(1,100);

% Toggle multiples of the current switch, including the current switch
for i = 1:100
% These are the switches to toggle
ivec = i:i:100;

% xor'ing them with 1's toggles them
switches(ivec) = bitxor(switches(ivec), 1);
end

% Show the indexes of the switches that are "on" after this process
% (expect perfect squares: 1 4 9 16 25 36 49 64 81 100)
find( switches )

Running the script results in:

ans =

1     4     9    16    25    36    49    64    81   100

which is what we expected.

Of course, you could also keep track of how many times you made a flip. XOR can help with this too.

% All switches initially off
switches = zeros(1,100);
new_switches = zeros(1,100);
num_flips = zeros(1,100);

% Toggle multiples of the current switch, including the current switch
% (gratuitous use of bitxor as a demo)
for i = 1:100
% These are the switches to toggle
ivec = i:i:100;

% xor'ing them with 1's toggles them
new_switches(ivec) = bitxor(switches(ivec), 1);

% count the flips
% ( num_flips(ivec) = num_flips(ivec)+1  works too)
num_flips = num_flips + bitxor( new_switches, switches );

% commit new_switches to switches to maintain invariant
% (can omit new_switches by not using second bitxor above)
switches = new_switches;
end

% Show the indexes of the switches that are "on" after this process
% (expect perfect squares: 1 4 9 16 25 36 49 64 81 100)
find( switches )

Then, from the console, we can issue commands like:

num_flips( find(switches) )     % shows number of flips for switches ending "on"
num_flips( find(switches==0) )  % shows number of flips for switches ending "off"
find( mod(num_flips,2)==1 )     % verifies odd-count flips have perfect-square indexes

So that's fun.