Permutation Puzzles

Consider five women, Anne, Betsy, Corrine, Donna, and Emily, who live
(not necessarily respectively) in the cities Anaheim, Baltimore, 
Cleveland, Denver, and Enumclaw.  Each woman has exactly one son, and
their names are Andy, Bob, Chuck, Dave, and Edward (again, not 
necessarily in that order).  The ages of the women are 41, 42, 43, 
45, and 46 (again, not necessarily in that order).  We're given the 
following information:

1. Emily lives in Anaheim. She's one year older than Chuck's
   mother who lives in Cleveland.
2. Edward's mother is Donna.  She's one year older than Anne whose
   son isn't Dave.
3. The woman in Denver (who isn't Betsy) is younger than the woman in
4. Andy's mother (not Corrine) is 43.
5. The woman living in Baltimore is 45. 

How old is each woman, who is her son, and where does she live?
Moreover, is there an efficient formal technique for solving problems
like this?  Perhaps if we think about the thought process we would 
use to solve it "by hand", and then think about how we might program
a computer to do the same thing, the process could be formalized.

The most useful information in the particular puzzle stated above
seems to be the ages and their relations to each other.  There are 
two distinct pairs of women whose ages differ by only one, and the 
list of ages contains only three such possibilities.  Furthermore, 
we know Chuck's mother isn't 45 (from her location), so we must have
either [Emily=42,Chuck's=41] or else [Emily=43,Chuck's=42].  Both of
these involve the age 42, so we have Donna=46 and Anne=45, hence 
Anne is in Baltimore.  Also, we must put Donna in Enumclaw to make
its resident older than the woman in Denver, who must be Corrine.
Then we see Andy must be Emily's son, so she is 43, and the rest 
falls into place.  The result is

    Emily     Anne        Betsy       Corrine    Donna
    43        45          42          41         46
    Andy      Bob         Chuck       Dave       Edward
    Anaheim   Baltimore   Cleveland   Denver     Enumclaw

There are probably many different and equivalent ways of expressing
and formalizing the constraints.  One way is in terms of compositions
of permutations.  We have four groups (names, ages, son's names, and
locations) of five elements, and we can arbitrarily assign the numbers
1 to 5 to the elements of each group as shown below

             City        Woman       Son         Age

      1     Anaheim      Anne        Dave         41
      2     Baltimore    Donna       Chuck        42
      3     Cleveland    Emily       Bob          43
      4     Denver       Betsy       Andy         45
      5     Enumclaw     Corrine     Edward       46

We seek permutations of these four sets that, when aligned, satisfy
certain conditions.  The solution can be expressed by the following
set of four permutations

                     Cities      12345 I
                     Women       31452
                     Sons        43215
                     Ages        34215

These permutations match each city with the resident woman, her 
son, and her age.  Of course, there are really 120 distinct ways of
permuting the five columns, and they all represent the same logical
solution.  I just arbitrarily chose to arrange the columns so that 
the cities have the identity permutation 12345.  Three other ways of
expressing the same solution are

    Cities  25134        Cities  43215        Cities  43125
    Women   12345 I      Women   54132        Women   54312
    Sons    35421        Sons    12345 I      Sons    12435
    Ages    45321        Ages    12435        Ages    12345 I

where "I" denotes the category that has the identity permutation.
Obviously if the permutation from Cities to Women (for example) is
31452, then the inverse is 25134.  Notice that the composition of 
any permutation and its inverse is the identity permutation.  More
generally, the composition of any "loop" of permutations must yield
the identity, and this fact can be used to infer information about
some of the permutations given information about some of the others.
To illustrate, consider the three categories Cities, Ages, and Women,
and note that we have the permutations

           Cities to Women:  31452
           Women to Sons:    35421
           Sons to Cities:   43215

The composition of these three permutations, in sequence, necessarily
gives the identity.  To show how this establishes conditions on the
solution, recall that we were told explicitly that Emily is in Anaheim,
so the permutation from Women to Cities is of the form {**1**}.  In
addition, as noted above, the numerical clues about the Ages exclude
all but two permutations from Cities to Ages, namely, {24135} and 
{34215}.  Taking the second of these, we have

           Cities to Ages:  3****
           Ages to Women:   *****
           Women to Cities: **1**

The composition of these three permutations must be the identity
permutation, which clearly requires that the permutation from Ages 
to Women must be of the form {**3**}.  In other words, we've deduced
that the 43 year old woman is Emily, which determines the rest of
the solution.  

Of course, there's nothing profound going on here.  The leading "3" 
in the permutation from Cities to Ages signifies that the woman in 
Anaheim is 43, and the middle "1" in the permutation from Women to 
Cities signifies that Emily is in Anaheim.  These two facts in 
combination obviously imply Emily is 43.  This just illustrates how
information on one basis is related to information on other bases.

It's important to recognize that there are three distinct aspects of
puzzles of this kind.  The first is just general computation.  For 
example, the particular puzzle above required making use of numerical
relations between a given set of numbers.  More generally, conditions
could be imposed such as "The age of person A has exactly two prime 
divisors in common with the age of person B".  Before even beginning
to solve the puzzle, we must first resolve all the computational 
"clues" of this kind, and express them as constrants on the allowable
permutations. These computational aspects could be arbitrarily 
difficult - or even practically impossible - to resolve.  Fro example,
it might be specified that person A lives in city D if and only if 
the 100 trillionth decimal digit of pi is 7.  This is a perfectly
deterministic and well-defined "clue", but it is practically useless.

Assuming we can solve the computational aspects of the puzzle, the 
second task is to determine which permutations between two given sets
are allowed based on a set of clues.  This has nothing to do with 
transferring information from one basis to another.  It is essentially
just the classical "satisfiability problem", i.e., given a set of 
logical variables feeding into a fixed system of logic gates with a
single logical output variable, determine which (if any) input states
set the output TRUE.  (It is this kind of reasoning that enables us
to say the permutation from Cities to Ages must be either {24135} or
{34215}, without even taking any other information into account.) 
This is known to be NP-complete, so we can't expect there to exist
any simple recipe that would work in polynomial time in all cases.  

The third task involved in solving such puzzles is to relate the
information that has been provided on different bases.  It is only
this third task (the simplest of the three) that can be formalized 
in terms of the compositions of permutations.

Return to MathPages Main Menu