The 1000 Lockers...

Probability Level 2

A high school has a strange principal. On the first day, he asks his students to perform an odd opening day ceremony:

There are one thousand lockers and one thousand students in the school.

The principal asks the first student to go to every locker and open it. Then he has the second student go to every second locker and close it. The third goes to every third locker and, if it is closed, he opens it, and if it is open, he closes it. The fourth student does this to every fourth locker, and so on.

After the process is completed with the thousandth student, how many lockers are open?

This problem is a part of the set brain games

32 29 30 31 33

A Former Brilliant Member by A Former Brilliant Member

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Discussions for this problem are now closed

The only lockers that remain open are perfect squares (1, 4, 9, 16, etc) because they are the only numbers divisible by an odd number of whole numbers; every factor other than the number's square root is paired up with another. Thus, these lockers will be "changed" an odd number of times, which means they will be left open. All the other numbers are divisible by an even number of factors and will consequently end up closed.

So the number of open lockers is the number of perfect squares less than or equal to one thousand.

So the answer is 31

14 Helpful 0 Interesting 0 Brilliant 0 Confused

:/ Could not understand.

Ritvik Chaturvedi - 6 years, 3 months ago

Practical example: - Locker 15: 1st student opens it, 3rd student closes it, 5th student opens it again, 15th student closes it again. So it ends up closed. - Locker 16: 1st student opens it, 2nd student closes it, 4th student opens it again, 8th student closes it again, 16th student opens it again. So it ends up open. Finally, we can conclude the only lockers that end open at the end of the process are those whose number is a perfect square. Since 31² < 1000 and 32² > 1000, the answer is 31.

Fabio Gama - 6 years, 3 months ago
Brock Brown
Feb 21, 2015

Python simulation: 

1
2
3
4
5
6
7
8
 
students = range(1, 1001)
closed = [True] * 1000
for student in students:
    pos = student - 1
    while pos < 1000:
        closed[pos] = not closed[pos]
        pos += student
print "Answer:", closed.count(False)

3 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...