RSS Feed

Mission Possible: The Prison Problem

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!
Advertisements

About Nicole Bencze

I am an awesome newish math teacher who calls Delta School District her home. I'm crazy in love with math and there's no place in this world I'd rather be than in a classroom showing my kidlets how amazing it can be! Outside of teaching I'm quite the coffee addict and I live inside the fandom universe falling in love again and again with Lord of the Rings, Harry Potter, Mortal Instruments, Twilight, Hunger Games, Percy Jackson, Game of Thrones, Sherlock, Doctor Who, and a ton more. My cat is my best friend and I'm way too invested in TV shows!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: