Question 26952: Imagine you are at a school that has student lockers. There are 1000 lockers all shut and unlocked and 1000 students. Suppose the first goes along the row and opens every locker. Then the second student goes along and shuts every other locker beginning with the second locker. After that the third student changes the state of every third locker beginning with the third licker (if the locker is open the student shuts it, and if the locker is closed the student open it.) Next the fourth student changes the state of every fourth locker starting with the fourth locker. Imagine that this continues until the thousand students have followed the pattern with the thousand lockers. At the end, which lockers will open and which will be closed? and Why?
Found 3 solutions by kj_cheerldr, solver91311, jim_thompson5910:
Answer by kj_cheerldr(3)   (Show Source):
You can put this solution on YOUR website! every other locker would be closed, because the first person opened the 1st locker, the 2nd person closed the 2nd loacker, the 3rd person opened the 3rd locker....and so on.
Answer by solver91311(24713)  (Show Source):
You can put this solution on YOUR website! I haven't quite figured out why yet, but presuming the lockers are numbered consecutively from 1 to 1000, lockers whose numbers are perfect squares will be open and all the rest will be closed.
I solved this by brute force using an Excel spreadsheet on a sub-set of the problem, namely 100 students and 100 lockers.
The first row in the sheet has a zero in every column from 1 to 100, denoting that the first student (row 1) opened every locker (column 1 to 100), zero denoting an open locker and 1 denoting a closed locker.
In every other cell, rows 2 through 100 and column 1 through 100, if the row number is less than or equal to the column number and the row number evenly divides the column number, there is a formula that makes the value of the cell be the opposite (changes 0 to 1 or 1 to 0) of the cell immediately above it.
Looking at the pattern at the bottom of the data, columns 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100 have zeros, and the rest have ones.
Answer by jim_thompson5910(35256) (Show Source):
You can put this solution on YOUR website! It definitely helps to break this problem into smaller pieces and draw a picture.
Lets say we only have 10 people and 10 lockers. If person 1 opens all of the lockers, they're all open. Now person 2 goes, and all of the even numbered lockers are shut. Now it's 3's turn: locker 3 is shut, locker 6 is open again, and 9 is shut. Four takes a shot and locker 4 and 8 are reopened. 5 goes and 5 and 10 are shut. Students 6, 7, 8, and 10 only shut locker 6, 7,8, and 10 respectively; while person 9 opens locker #9.
So if we look at say locker #6, person 1 opens it, person 2 closes it, person 3 opens it, and finally person 6 closes it. So there are 4 people who interact with it (notice how its an even number). While with locker 4, only students 1,2,4 touch it, and it stays open. So by this reasoning, if an even number of people touch it, it stays closed. If an odd number of people touch it, it stays open. To find out how many people touch it, we simply find the number of factors the number has. With 6 there are 4 factors: 1,2,3,6. The four factors simply cancel each other out (one action of opening is undone by another action of closing). While the number 4 has 3 factors: 1,2,4. These factors dont cancel so it stays open. It turns out that every number, except the perfect squares, has an even number of factors. Think about it, to multiply to say 40, one could go 1*40,2*20,4*10,5*8,8*5,10*4,20*2,40*1. All of these factors are paired up, which means there are an even number of factors. Even prime numbers have an even number of factors, they are divisible by their own number and 1 (ie 61=1*61). However, even though perfect squares may seem to have an even number of factors (for instance 9:1*9,3*3,9*1) there is a repeated factor of 3. So there are only 3 factors in this number. This is true for all perfect squares, since there's always a repeated factor of the square root value. So every perfect square locker number will remain open because they have an odd number of factors. This makes it easier to count the number of open lockers since we only have to find perfect squares. So here's the list of perfect squares (and open lockers):
1
4
9
16
25
36
49
64
81
100
121
144
169
196
225
256
289
324
361
400
441
484
529
576
625
676
729
784
841
900
961
And there happens to be 31 perfect squares less than 1000.
So there are 31 lockers left open. I hope this makes sense.
|
|
|
