Making Heads or Tails of Binary Proofs
Date: 03/17/2011 at 18:18:59 From: Jane Subject: Coin turning problem (not coin flipping or tossing) Five coins are all put down on a table showing tails. Can you make them all show heads by turning two at a time? What about if you turn three at a time? four? What about if you start with six coins and do the same? or start with seven coins, and so on? I'm not sure what these questions are even asking. I don't think they have to do with probability, as you are systematically turning two (or however many) coins at a time. The only thing I can think to do is produce a proof that a certain state of heads and tails can't (or can) be reached. For starters, the first scenario (five coins, turned two at a time) can't be done as far as I can see. I convinced myself that this is true by first encoding each tail as 1 and each head as 0, and representing the starting state as the sum 5. I need to reach a final state of 0 by turning (or subtracting and adding) two at a time. Each turn, in other words, changes the total by +/- 2. But doing so always yields an odd number; I can never get to 0. So it is not possible. However, if I start with five coins and turn three at a time, then it can be done using the same reasoning as above. I've tried doing this for many combinations -- changing the number of coins used and the number turned at any one time -- and don't see any pattern. Maybe there isn't one? Am I even on the right track?
Date: 03/18/2011 at 12:12:03 From: Doctor Tom Subject: Re: Coin turning problem (not coin flipping or tossing) Hi Jane, You are exactly on the right track! What you want to do is formulate a proof for each conclusion. For example, if you start with five initial tails and turn two at a time, you can never get them to all heads. An argument like yours, above, is known as a "mathematical invariant." In this case, the invariant is "there are always an odd number of tails showing." Here's a simpler argument based on this invariance: Given an odd number of heads, turning two adds +/- 2 to an odd number, so there are always an odd number of heads; but to solve it, we'd need an even number (zero) of heads. In other cases, it is possible to solve the problem; here, your proof will simply be a description of how to get there. For example, if you've got an even number of coins initially, and you're turning two at a time, just state that whenever there are tails showing, pick two and turn them to heads. To prove that this works, you can use both the idea of an invariant (in this case, "there are always an even number of tails showing"), and the idea of a "monovariant," (in this case, "every time two coins are turned, the number of tails decreases"). So the proof that your solution, based on the monovariant and invariant, comes down to: If you start with a positive even number and continue to reduce it to other even numbers, eventually you'll get to zero. Of course with specific cases, like "5 tails, turning 3 at a time," all you need to do to prove it's possible is to give a specific set of turns to solve the problem, like "turn coins in positions 1, 2, 3; then turn the ones in positions 4, 5, 6; then turn 1, 2, 4; then ..." Another strategy you might use to prove that a certain problem can be solved would be to find a sequence of moves that will leave everything exactly the same, except that it turns one coin and one coin only. Then you could apply that sequence to each of the coins in turn, and you'll eventually get them all turned over. This would not be an efficient way to do it, normally, but it IS a proof that the problem can be solved. Notice that the method I started two paragraphs ago, with the "5 turn 3" problem, uses this one-by-one approach: using your encoding of ones and zeros, it takes three steps to go from 11111 or TTTTT to 11110 or TTTTH. That means there's a 15-move sequence to get from TTTTT to HHHHH. I hope this helps! - Doctor Tom, The Math Forum http://mathforum.org/dr.math/
Date: 03/18/2011 at 14:35:03 From: Jane Subject: Thank you (Coin turning problem (not coin flipping or tossing)) Many thanks for this. I was on the right track but you have helped me out no end. Thank you!!!!
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum