The Lockers

Number Theory Level 2

There is a school with 1,000 students and 1,000 lockers. On the first day of term the head teacher asks the first student to go along and open every single locker, he asks the second to go to every second locker and close it, the third to go to every third locker and close it if it is open or open it if it is closed, the fourth to go to the fourth locker and so on.

The process is completed with the thousandth student. How many lockers are open at the end?

The answer is 31.

2 solutions

Isaac Wright
Jan 8, 2016

The only lockers that remain open are square numbers (1,4,9 etc) because these are the only numbers divided by an odd number of numbers. Therefore they will be changed by an odd number of students and left open at the end. Each number with a square root of 31 or less will be left open. $32^{2}$ =1024>1000, and is hence out of the question).

Funny story, one time my math class solved this problem, but they had to do it with actual lockers! But they only used 100. Luckily I was smart enough and figured it out on paper! Lol!

Colin Carmody - 5 years, 5 months ago

K T
Jan 26, 2020

Note that a particular locker will be open at the end, if it has been changed by an odd number of students. That is, if the number n of that locker has an odd number of divisors.
For any divisor $d$ of $n$ , there is another divisor $n/d$ . So divisors always come in pairs, unless... $n/d=d$ .
Those cases, where $n=d^2$ , occur exactly when n is a perfect square. So the squares (and only the squares) have an odd number of divisors. The number of open lockers is the number of perfect squares upto 1000, which is $\lfloor\sqrt{1000}\rfloor =\boxed{31}$ .

The Lockers

The answer is 31.

2 solutions

0 pending reports