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/