100 Lockers, 100 StudentsDate: 8/16/96 at 14:39:22 From: Anonymous Subject: 100 Lockers, 100 Students Open/Close... There are 100 closed lockers in a hall, and 100 students. Student 1 walks down the hall and opens all 100 lockers. Student 2 closes all even-numbered lockers. Student 3 looks at every third locker (a multiple of 3), and if it is open closes it, or vice-versa (this student changes the condition of the locker). Student 4 repeats the action of student 3, but only changes the condition of lockers that are a multiple of 4. This goes on with every student doing the same routine for his or her number. After 100 students go through, how many lockers are open? And are the open lockers even or odd? Date: 8/30/96 at 17:0:58 From: Doctor James Subject: Re: 100 Lockers, 100 Students Open/Close... Basically you have a system of 100 states, each of which is binary (either open or closed). Each binary 'cell' (b1, b2, b3,...,b100) can either be 0 (closed) or 1 (open). All start out 0, and each operation changes its value. Now, since each cell is acted on whenever the student number (1 to 100) is a factor of it, the cell changes state a number of times equal to the number of its factors, right? And if it changes state an even number of times, it ends up closed, and if it changes state an odd number of times, it ends up open. So this question boils down to: How many numbers from 1 to 100 have an even number of factors, and how many have an odd number of factors? The factors of a number are those numbers that the original number is evenly divisible by. In all cases, the result of such a division is also a factor (I will call this a 'cofactor'). This means that unless one of the factors is the square root of the number, the number will have an even number of factors. If one of the factors is the square root of the number, then the cofactor is itself. For all other factors, there will be a cofactor, and thus an even number of them. Since an even number plus 1 is an odd number, any perfect square, and only a perfect square, will have an odd number of factors. So, all that mess means the following: Every locker whose number is a perfect square will be open. This means that lockers 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100 will be open, for a total of 10. There is no correlation between evenness or oddness and being open. If I made it too confusing, please write back and let me try again. -Doctor James, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/