One Hundred Lockers?

Question

Imagine you are at a school that still has student lockers. There are 100 lockers, all shut and unlocked, and 100 students.

Here's the problem:

1. Suppose the first student goes along the row and opens every locker.

2. The second student then goes along and shuts every other locker beginning with number 2.

3. The third student changes the state of every third locker beginning with number 3. (If the locker is open the student shuts it, and if the locker is closed the student opens it.)

4. The fourth student changes the state of every fourth locker beginning with number 4.

Imagine that this continues until the hundred students have followed the pattern with the hundred lockers. At the end, which lockers will be open and which will be closed? Why?

Answer 1

Each locker has a number which can be factored.

Each locker will be opened at least once.

Each locker's state will be changed each time one of their unique factors (not necessarily prime) come up.

So lockers with an even number of factors will be closed.

Lockers with an odd number will be open.

Examples:
1 has one unique factor: 1, so it will be open.
2 has two unique factors: 1 and 2, so it will be closed.
3 has two unique factors: 1 and 3, so it will be closed.
4 has three unique factors: 1,2 and 4, so it will be open.
......
49 has three unique factors: 1, 7, 49, so it will be open.
......
60 has 12 unique factors: 1,2,3,4,5,6,10,12,15,20,30,60, so it will be closed.
......
100 has 9 unique factors: 1, 2, 4, 5, 10, 20, 25, 50, 100, so it will be open.


If you were to do this with enough numbers, you will find that only the perfect squares will be open. This is because unique factors are paired with another unique factor. With perfect squares, however, one of the unique factors is paired with itself.

So -- 1, 4, 9, 16, 25, 36, 49, 64, 81 and 100 will all be open, and the rest will be closed. And this is because perfect squares have an odd number of unique factors.

Answer 2

Your question doesn't quite make sense. What does the 10th student do? There are no locker numbers that begin with a "10". There are only 9 possible digits that a locker can begin with. So, I'm assuming what you actually meant was that the 10th student simply switched the state of every 10th locker, the 9th student switched the state of every 9th locker, etc.

I wrote a program to essentially brute-force the problem (actually perform every single operation described).

I started with an array of 100 values. Every value begins as 1 (closed). Then a student goes through and opens every locker whose value is a multiple of 1 (which is every locker). I multiply all those values in the array by -1. A locker with a value of -1 corresponds to being open. Then I go through and do the same thing to every locker with a number that's a multiple of two. Then every locker that's a multiple of three. Et cetera.

Here's the result, displayed so that 1 = closed, and 0 = open:

0110111101
1111101111
1111011111
1111101111
1111111101
1111111111
1110111111
1111111111
0111111111
1111111110

With careful inspection, you will see that all lockers are closed except lockers 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100. All these numbers are perfect squares.

Answer 3

all primes will be closed
the factors: 1,p (open, then closed)

the composite numbers will be closed if the number of factors, including 1 & itself is even.

Otherwise the locker is open. d: