25
$\begingroup$

There are 1000 lockers in a high school with 1000 students. The problem begins with the first student opening all 1000 lockers; next the second student closes lockers 2,4,6,8,10 and so on to locker 1000; the third student changes the state (opens lockers closed, closes lockers open) on lockers 3,6,9,12,15 and so on; the fourth student changes the state of lockers 4,8,12,16 and so on. This goes on until every student has had a turn.

How many lockers will be open at the end?

I worked out this problem by doing it for 10 lockers. The pattern was obvious (1,4,9 remained open).It's easy to then say that 31 lockers remain open at the end. I don't quite understand why only square numbers remain open at the end. Is there some deeper reason?

$\endgroup$
1
  • 1
    $\begingroup$ You should check out this video from mathematician James Grime. He basically repeats the answers below, but his explanation is entertaining. $\endgroup$ – Cody Nov 17 '16 at 0:09
31
$\begingroup$

Squares are the only integers which have an odd number of divisors.

All other (non-square) integers have an even number of divisors.


A deeper insight:

Given an integer $n$, for every integer $d$ which divides $n$, the integer $n/d$ also divides $n$.

If $n$ is non-square, then for every integer $d$ which divides $n$, the integer $n/d \neq d$.

So we can split the divisors of $n$ into pairs, hence $n$ has an even number of divisors.

If $n$ is square, then for every integer $d\neq\sqrt{n}$ which divides $n$, the integer $n/d \neq d$.

So we can split the divisors of $n$ except $\sqrt{n}$ into pairs, hence $n$ has an odd number of divisors.

$\endgroup$
4
  • $\begingroup$ I know I'm being stupid, but I have to ask - doesn't 30 = 2 * 3 * 5 have an odd number of divisors? What am I missing? $\endgroup$ – TV's Frank Nov 17 '16 at 15:02
  • 4
    $\begingroup$ @TV'sFrank: $30$ has $3$ distinct prime factors ($2,3,5$) and $8$ divisors ($1,2,3,5,6,10,15,30$). $\endgroup$ – barak manos Nov 17 '16 at 15:07
  • $\begingroup$ Aha! Thanks! :) $\endgroup$ – TV's Frank Nov 17 '16 at 15:26
  • $\begingroup$ How do you find out "Given an integer n, for every integer d which divides n, the integer n/d also divides n." ? It is obvious, but without this obvious start, concluding that squares are the only integers which have an odd number of divisors is not forcely straighforward $\endgroup$ – Edmondo1984 Aug 26 '18 at 20:33
14
$\begingroup$

If a locker number has an even number of factors, it will be alternatively opened and closed and even number of times, ending in the same configuration it started.

Square numbers have a odd number of factors.

$\endgroup$
7
$\begingroup$

The idea here is that it is easy to identify pairs of students who will open and close a locker (well, as easy as any interesting math problem ever is!). If any given student will open or close a locker, it means their number is a divisor of the locker's number.

Consider locker X. Let's assume there is a student Y who toggles the locker. This means we know X/Y is an integer. This also means that student X/Y will also toggle the locker.

Take locker 12, with factors 1, 2, 3, 4, 6, and 12. If I rearrange them into pairs, (1, 12) (2, 6) (3, 4) we can see that for every student who opens a locker, there will be one that closes the locker.

Now, Let's look at a square. Let's take 16, with factors 1, 2, 4, 8, 16. If I rearrange them into pairs I get (1, 16) (2, 8) (4, 4)... but wait... I just had to use 4 twice. I had to do that because it was a square. However, student 4 is only going to toggle locker 16 once. Thus, the locker will be left open at the end of the day!

$\endgroup$
5
$\begingroup$

Locker number $n$ is toggled once for each divisor of $n$. If $n$ is not a square, then the map $d \to n/d$ is a bijective map on the set of divisors $S_n$ of $n$. Thus $S_n$ has an even number of elements; it is the disjoint union of the sets of the form $\{d, n/d\}$, each of which contains $2$ elements. If $n$ is a square, then $S_n$ is the union of sets $\{d, n/d\}$ for $d^2\not = n$ and a singleton set $\{\sqrt{n}, \sqrt{n}\}$. Hence the size of $S_n$ is odd. Toggling a closed locked $n$ times leaves it closed if $n$ is even and open if $n$ is odd.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.