1.1 A Row of Glass Cabinets

A Puzzle to Begin

The curator of a science museum, Meera, set up a challenge for a visiting group of 100 students. Along one long corridor stood 100 glass cabinets, numbered 1 to 100, every one of them shut. She handed each student a numbered badge from 1 to 100 and gave the rule:

Student 1 walks down the row and opens every cabinet.
Student 2 visits every 2nd cabinet and flips it (shuts an open one, opens a shut one).
Student 3 flips every 3rd cabinet (the 3rd, 6th, 9th, …).
Student 4 flips every 4th cabinet, and so on, until all 100 students have walked the corridor.

When the dust settled, only a handful of cabinets were left open, and a card inside each open cabinet spelled out a secret word. One student, Arjun, announced the answer before a single cabinet had been touched. How did he know?

The trick is to ask how many times each cabinet gets flipped. Cabinet number k is visited exactly by those students whose badge number is a factor of k. So:

\text{number of flips of cabinet } k \;=\; \text{number of factors of } k.

A cabinet finishes open only if it is flipped an odd number of times. The whole puzzle therefore reduces to one question: which numbers have an odd number of factors?

Factors normally arrive in matching pairs, because each factor multiplied by its partner rebuilds the number. Take cabinet 12:

12 = 1\times 12 = 2\times 6 = 3\times 4 \quad\Rightarrow\quad \text{factors } 1,2,3,4,6,12 \;(\text{six, even}).

For most numbers every factor has a distinct partner, so the count is even and the cabinet ends shut. But something special happens for numbers like these:

1 = 1\times 1,\qquad 4 = 2\times 2,\qquad 9 = 3\times 3.

Here one “pair” is a number times itself. That factor has no separate partner, so it is counted only once, leaving an odd number of factors.

The Key Idea A number that can be written as some number multiplied by itself, 1\times1,\ 2\times2,\ 3\times3,\dots, is called a square number. The squares are the only numbers with an odd number of factors. So the cabinets left open are exactly the square-numbered ones.

The open cabinets are therefore:

1,\ 4,\ 9,\ 16,\ 25,\ 36,\ 49,\ 64,\ 81,\ 100.

Meera’s card added a twist: “The secret word sits in the cabinets that were touched exactly three times.” When is a cabinet flipped exactly three times? Only when its number has exactly three factors. A little thought shows this happens precisely for the square of a prime, for instance 49 = 1\times 7 \times 49 has just the three factors 1, 7, 49. The first such numbers are

\boxed{4,\ 9,\ 25,\ 49,\ 121,\ \dots} \qquad (=2^2,\,3^2,\,5^2,\,7^2,\,11^2,\dots).

That little discovery, a number has exactly three factors exactly when it is a prime squared, is a perfect doorway into the rest of the chapter.