Skip to content

Square numbers and the locker puzzle

Number theory · level 2, lesson 6 of 6

A question to start

A school has a long hall with 100 lockers, numbered 1 to 100. They are all closed. 100 students walk down the hall, one after another.

  • Student 1 opens every locker.
  • Student 2 goes to every 2nd locker (2, 4, 6, ...) and changes it: if it is open, she closes it; if it is closed, she opens it.
  • Student 3 goes to every 3rd locker (3, 6, 9, ...) and changes it.
  • Student 4 changes every 4th locker, and so on, until student 100 changes only locker 100.

When all 100 students have finished, which lockers are open?

It sounds like you would need to walk the hall 100 times. But the answer is short and beautiful, and by the end of this lesson you will be able to say it without opening a single locker.

The idea

Square numbers

A square number is a number of counters that can make an array that is a square: the same number of rows as counters in each row.

1 × 1 = 1 2 × 2 = 4 3 × 3 = 9 4 × 4 = 16 each new layer is the next odd number: 1, 3, 5, 7
  • 1 × 1 = 1
  • 2 × 2 = 4
  • 3 × 3 = 9
  • 4 × 4 = 16
  • then 5 × 5 = 25, 6 × 6 = 36, 7 × 7 = 49, 8 × 8 = 64, 9 × 9 = 81, 10 × 10 = 100.

So the square numbers up to 100 are 1, 4, 9, 16, 25, 36, 49, 64, 81, 100. There are 10 of them.

Look at the colours in the picture. To grow a square into the next one, you add an L-shaped layer around two of its sides. The layers have 1, 3, 5, 7, ... dots: the odd numbers! That is why adding the odd numbers in order gives the squares:

  • 1 = 1
  • 1 + 3 = 4
  • 1 + 3 + 5 = 9
  • 1 + 3 + 5 + 7 = 16

And the layers grow by 2 each time because each new L has one more dot along the top, one more down the side, and they share the corner: that is 2 more than the L before.

Counting factors: odd or even?

Let us count the factors of some numbers.

Number Factors How many Odd or even count?
6 1, 2, 3, 6 4 even
9 1, 3, 9 3 odd
10 1, 2, 5, 10 4 even
12 1, 2, 3, 4, 6, 12 6 even
16 1, 2, 4, 8, 16 5 odd
18 1, 2, 3, 6, 9, 18 6 even
25 1, 5, 25 3 odd
36 1, 2, 3, 4, 6, 9, 12, 18, 36 9 odd

Do you see it? The numbers with an odd number of factors are 9, 16, 25 and 36: all square numbers. The others have an even number of factors. This is always true, for every number. Here is why.

Why squares have an odd number of factors

Remember from Factors with arrays: factors come in pairs. Each array gives a pair: the number of rows and the number in each row. For 12 the pairs are 1 and 12, 2 and 6, 3 and 4. Pairs, pairs, pairs. Every factor has a partner, so the count is even: 3 pairs is 6 factors. It is the "pairs of socks" idea from level 1 again!

But in a square, one array is special: the square array. For 16 it is 4 rows of 4. The factor 4 is partners with itself.

1 2 4 8 16

In the factor rainbow, 4 stands alone in the middle, with no arc. When you list the factors you write 4 only once. So the factors of 16 are: two pairs (1 and 16, 2 and 8) and one lonely factor (4). Pairs and one lonely one: that is an odd number, 5.

And only squares have a factor that pairs with itself, because "a number times itself" is exactly what a square number is. So:

A number has an odd number of factors exactly when it is a square number.

Solving the locker puzzle

Now back to the hall. Which students touch locker 12?

Student 1 (who touches every locker), student 2 (every 2nd), student 3 (every 3rd), student 4, student 6 and student 12. Students 5, 7, 8, 9, 10 and 11 walk past it, because 12 is not in their skip count.

That is 1, 2, 3, 4, 6, 12: the factors of 12! Student number k touches locker 12 exactly when k is a factor of 12. That is true for every locker: locker number n is changed once for each factor of n.

Here it is for a small hall with just 10 lockers and 10 students. A blue square means "this student changes this locker".

1 2 3 4 5 6 7 8 9 10 student 1 student 2 student 3 student 4 student 5 student 6 student 7 student 8 student 9 student 10 at the end open open open locker number

Now follow one locker. It starts closed. Each change flips it: closed, open, closed, open, ...

  • After an even number of changes, it is back to closed (the changes pair up: open, close, open, close).
  • After an odd number of changes, it is open (one change has no partner to undo it).

So a locker ends open exactly when its number has an odd number of factors: exactly when its number is a square.

In the small hall, lockers 1, 4 and 9 end open. In the big hall with 100 lockers, the open lockers are:

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

That is 10 lockers, and every other locker is closed. Nobody had to walk the hall at all. That is the power of a good reason.

Worked examples

Example 1. Is 49 a square? How many factors?

  1. 7 × 7 = 49, so yes, 49 is a square.
  2. Its factors: 1 and 49 make a pair. 2, 3, 4, 5, 6 do not go into 49. 7 pairs with itself.
  3. So the factors are 1, 7, 49: three factors, an odd number, as the rule says.

Example 2. Locker 30. In the 100-locker puzzle, is locker 30 open or closed at the end? Which students touch it?

  1. 30 is not a square (5 × 5 = 25 and 6 × 6 = 36, so 30 is between two squares).
  2. So it has an even number of factors, and it ends closed.
  3. The students who touch it are its factors: 1, 2, 3, 5, 6, 10, 15, 30. That is 8 students, 4 pairs. Open, close, open, close, open, close, open, close. Closed. ✓

Example 3. Locker 64.

  1. 8 × 8 = 64, so 64 is a square. It ends open.
  2. Check: the factors of 64 are 1 and 64, 2 and 32, 4 and 16, and 8 alone. That is 3 pairs and 1 lonely factor: 7 factors. An odd number of changes, so it is open. ✓

Example 4. Which number below 50 is touched by the most students?

  1. We want the number below 50 with the most factors.
  2. Try numbers with many small factors: 24 has 8 (1, 2, 3, 4, 6, 8, 12, 24). 36 has 9. 48 has 10 (1, 2, 3, 4, 6, 8, 12, 16, 24, 48).
  3. Checking all the numbers below 50 the same way, none has more than 10. So 48 is touched by the most students: 10 of them. (It ends closed: 48 is not a square.)

Try it

  1. Write the square numbers from 1 × 1 to 12 × 12.
  2. What is 1 + 3 + 5 + 7 + 9? Is it a square? Draw it with an L-shaped layer for each odd number.
  3. List the factors of 25. How many are there?
  4. Without listing them, does 81 have an odd or an even number of factors? What about 80?
  5. In the 100-locker puzzle, is locker 50 open or closed? Is locker 81?
  6. Which students touch locker 16? List them.
  7. If the hall had 200 lockers and 200 students, how many lockers would be open at the end?
  8. In the 100-locker puzzle, which lockers are touched by exactly two students? What kind of numbers are they?
Answers
  1. 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144.
  2. 1 + 3 + 5 + 7 + 9 = 25. Yes, 25 = 5 × 5. The five L-shaped layers of 1, 3, 5, 7 and 9 dots build a 5 by 5 square.
  3. 1, 5, 25: 3 factors. 5 pairs with itself.
  4. 81 = 9 × 9 is a square, so it has an odd number of factors (1, 3, 9, 27, 81: five). 80 is not a square (8 × 8 = 64, 9 × 9 = 81), so it has an even number (1, 2, 4, 5, 8, 10, 16, 20, 40, 80: ten).
  5. 50 is not a square (7 × 7 = 49, 8 × 8 = 64), so locker 50 is closed. 81 = 9 × 9 is a square, so locker 81 is open.
  6. The factors of 16: students 1, 2, 4, 8 and 16. Five changes: open, close, open, close, open. It ends open.
  7. The open lockers are the squares up to 200: 1, 4, 9, ..., 196 (14 × 14 = 196; 15 × 15 = 225 is too big). That is 14 lockers.
  8. Numbers with exactly two factors: the primes! Locker 7 is touched only by student 1 (open) and student 7 (close). So every prime locker is touched by exactly two students, and ends closed. There are 25 of them, from 2 up to 97.

Common mistake

Counting the middle factor twice. For 36, the pair "6 and 6" is one factor, not two. Write the factors of 36 as 1, 2, 3, 4, 6, 9, 12, 18, 36: nine factors. If you write 6 twice you get ten and the rule seems to break.

Thinking "odd number" and "odd number of factors" are the same. 15 is odd but has 4 factors (1, 3, 5, 15), an even count. And 16 is even but has 5 factors, an odd count. What matters is being a square, not being odd.

Where it leads