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
_____________________________________________

Coin Patterns

Date: 08/26/2003 at 23:22:10
From: Dawn
Subject: Patterns

There are four rows of coins. Each row has exactly one penny, one 
nickel, one dime, and one quarter. No row, either horizontal, 
vertical, or diagonal, has more than one coin of each kind. How are 
the coins arranged?

I know there is a formula but I can't remember it.


Date: 08/28/2003 at 10:42:47
From: Doctor Ian
Subject: Re: Patterns

Hi Dawn,

There isn't a formula, actually. But there are systematic ways you
can approach this kind of problem.  

I'm going to use a, b, c, and d to represent the coins, just because
they're easier to think about than P, N, D, and Q.  At first, any coin
could be anywhere:

   abcd | abcd | abcd | abcd
   -----+------+------+-----
   abcd | abcd | abcd | abcd
   -----+------+------+-----
   abcd | abcd | abcd | abcd
   -----+------+------+-----
   abcd | abcd | abcd | abcd

For fun, let's make the first row a-b-c-d.  Since we haven't really
decided which coins are represented by which letters, there's no way
for this to be wrong. 

   a    |  b   |   c  |    d
   -----+------+------+-----
   abcd | abcd | abcd | abcd
   -----+------+------+-----
   abcd | abcd | abcd | abcd
   -----+------+------+-----
   abcd | abcd | abcd | abcd

Having made this choice, we can rule out some other possibilities. For 
example, we can't have an a in the first place in any other row, 
right? Similarly, we can't have b, c, or d in the second, third, or
fourth places:

   a    |  b   |   c  |    d
   -----+------+------+-----
    bcd | a cd | ab d | abc 
   -----+------+------+-----
    bcd | a cd | ab d | abc 
   -----+------+------+-----
    bcd | a cd | ab d | abc 

We also know that a and d can't appear elsewhere in the diagonals:

   a    |  b   |   c  |    d
   -----+------+------+-----
    bcd |   cd | ab   | abc 
   -----+------+------+-----
    bcd | a c  |  b d | abc 
   -----+------+------+-----
    bc  | a cd | ab d |  bc 

Now we've narrowed things down some, but not enough to get a unique
solution yet. Let's look at the final row. How many possibilities
remain? The first place can be b or c:

  b _ _ _
  c _ _ _

The second place can be a, c, or d; except we can't repeat a letter
within the row:

  b a _ _
  b c _ _
  b d _ _
  c a _ _
  c d _ _

The third place can be a, b, or d, again without repeats:

  b a d _
  b c a _
  b c d _
  b d a _
  c a b _
  c a d _
  c d a _
  c d b _

In each case, there's only one possible letter left, if we can't have
repeats:

  b a d c
  b c a d
  b c d a
  b d a c
  c a b d
  c a d b
  c d a b
  c d b a

But the final letter has to be a b or a c, so we can throw away any
row where this isn't true:

  b a d c
  b d a c
  c a d b
  c d a b

That leaves us with only four possibilities. Now, maybe only one of
these will work. Maybe all four will work. The only way to find out
is to try each one of them. For example, let's try 'badc' in the
final row: 

   a    |  b   |   c  |    d
   -----+------+------+-----
    bcd |   cd | ab   | abc 
   -----+------+------+-----
    bcd | a c  |  b d | abc 
   -----+------+------+-----
    b   | a    |    d |   c 

Now we can rule out those same letters in the same places in the other
rows:

   a    |  b   |   c  |    d
   -----+------+------+-----
     cd |   cd | ab   | ab  
   -----+------+------+-----
     cd |   c  |  b   | ab  
   -----+------+------+-----
    b   | a    |    d |   c

Now we know where c and b have to be in the third row, so we can
remove them everywhere that would cause a conflict (i.e., elsewhere in
the same row and column):

   a    |  b   |   c  |    d
   -----+------+------+-----
     cd |    d | a    | ab  
   -----+------+------+-----
      d |   c  |  b   | a   
   -----+------+------+-----
    b   | a    |    d |   c

And now we know where a and d must be in the second row, so we can do
the same thing:

   a    |  b   |   c  |    d
   -----+------+------+-----
     c  |    d | a    |  b  
   -----+------+------+-----
      d |   c  |  b   | a   
   -----+------+------+-----
    b   | a    |    d |   c

Now, the question is: Do the other possibilities also work, or is
this the only one? Can you work that out for yourself? 

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/ 
Associated Topics:
High School Permutations and Combinations
High School Puzzles
Middle School Puzzles

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/