Link: The Prison Problem
This problem didn’t take me too long to figure out. I knew that I had seen it before (though in a different context) so I had hints of strategies floating around my brain. Before going into any math though, I thought about what conditions would leave a cell open and would conditions would leave it closed. Everything was opened first. Then, multiples of 2 would have closed them, and so on with other multiples. So, if a number has an even number of factors, it would end up closed and if it has an odd number of factors, it would end up open. This gave me a direction with which to carry out my trials. All I needed to do was figure out how many factors each number between 1 and 100 had!
As always I started off by organizing my information and doing a trial run of some numbers in hopes to identify a pattern. The idea of calculating how many factors all the numbers between 1 and 100 had would be way too time consuming so I sought out an easier and more mathematical route. I tried out the escapist’s strategy on what would be the first 20 prison cells to give me a starting point. Once I had numbers I was able to confirm my theory that an odd number of factors leaves it open and an even number of factors left it closed. There was a hint in my brain somewhere that was telling me that prime factorization would help out with this problem, so I also went about writing out the prime factorizations of these as well. I couldn’t see the connection right away, but I had remembered something of a theorem from my Elementary Number Theory class a few years ago that would tell me how many factors a number has. I looked this up and that was the last bit I needed before I was able to clearly see how to finish off this problem. The theorem states that the number of factors of a number is the product of the (exponents+1) in its prime factorization. So the next question I asked myself was: how can I use this information to create an odd number? Below is my progress of thinking to reach my conclusion:
- How can a product equal an odd number? It must have no even numbers in it
- The product is determined by the exponents+1, so my exponents can ONLY be even numbers
- SO! All perfect squares are open
- Any other case can be rewritten as the product of perfect squares, because my exponents are only even numbers
- The product of perfect squares is once again a perfect square so I can conclude that only situation in which a prison cell is open is if it’s cell number is a perfect square!