This problem was very intriguing, as I never really enjoyed these sorts of math puzzle problems. But after four years of doing math in university and taking many discrete math courses, this problem can't be harder than my math assignments right? To begin, I initially wanted to shorten this problem from 1000 to 10 and brute force my way through the 10 students. However brute forcing by using a smaller sample and then later extending it to a larger sample misses the point of being able to solve this problem without any brute force. So I thought about it a bit more and came up with a solution. Initially every locker is open. For each locker number n ranging from 1 to 1000, the question is how many times the state of each locker is changed after all 1000 students had their turn. That turns out to be the number of positive factors n has. For example, for locker 12, the students who will affect it will be student 1, 2, 3, 4, 6, and 12. So that will be 6 changes. Since 6 is even, the locker will in the end be open, since the doors alternate from open and shut, and here we initially started at open. Students with numbers greater than 12 will not affect locker 12 as they'll start off with locker numbers bigger than 12. So this method can be done with every number n from 1 to 1000. If the number of positive factors n has is even, locker n will be open in the end, and if odd, locker n will be shut in the end. I could go in more detail on how to find the number of positive factors n has, but not going into too much detail right now (the explanation requires prime factorization and the fundamental counting principle). In the end, the lockers with numbers that are perfect squares will be closed as when you write out the factors, the square root of that perfect square will be repeated twice. However that counts as one factor, which means in the end a perfect square will have an odd number of factors. Thus it will be closed. For example, the number 36 has factors 1,2, 3, 4, 6 (6 only counted once), 9,12,18,36. 36 has 9 (odd) distinct factors so it will be closed in the end.
Also interesting to note: my SA does math riddles at the start of her lessons, and on my second day of practicum she showed the class this riddle from Ted Talk.
Good as far as you've taken it! I like your challenge to yourself not to go with brute force methods, even with a much smaller sample -- although there is nothing really wrong with that approach as a starting point, and of course many of your students will start that way. However, you have not completed this explanation because you haven't mentioned which locker numbers have an odd number of factors and why! You don't need to invoke a heavy apparatus of number theory, etc. to explain this. Please complete your explanation and let me know when it's done so that I can read it and mark it as complete!
ReplyDeleteThanks for the update, Michael. And how interesting that your SA used this same riddle with the class -- with the additional 'clues' about prime numbers. Cool TED talk riddle! I might use this extra add-on about the primes in future too.
ReplyDelete