Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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!!!!
Associated Topics:
High School Discrete Mathematics
High School Logic

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/