Permutation Puzzles and Logic Problems

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 Enumclaw.

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? 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

Is there a systematic way of approaching problems of this kind? 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

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

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

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

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

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.

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 constraints on the allowable permutations. These computational aspects could be arbitrarily difficult - or even practically impossible - to resolve. For example, it might be specified that person A lives in city D if and only if the 100 trillionth decimal digit of π 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.

For another example of a permutation puzzle, with a slightly different character, consider the following well-known “story problem”:

There are 5 houses in 5 different colors in a row. In each house lives a person with a different nationality. The 5 owners drink a certain type of beverage, smoke a certain brand of cigar, and keep a certain pet. No owners have the same pet, smoke the same brand of cigar, or drink the same beverage. One of them owns a fish. Other facts:

1. The Brit lives in the red house.

2. The Swede keeps dogs as pets.

3. The Dane drinks tea.

4. The green house is on the immediate left of the white house.

5. The green house's owner drinks coffee.

6. The owner who smokes Pall Mall rears birds.

7. The owner of the yellow house smokes Dunhill.

8. The owner living in the center house drinks milk.

9. The Norwegian lives in the first house.

10. The owner who smokes Blends lives next to the one who keeps cats.

11. The owner who keeps the horse lives next to the one who smokes Dunhill.

12. The owner who smokes Bluemasters drinks beer.

13. The German smokes Prince.

14. The Norwegian lives next to the blue house.

15. The owner who smokes Blends lives next to the one who drinks water.

The question is: WHO OWNS THE FISH?

In this puzzle it is stipulated that the five houses are lined up in a row, so we can consider a 5x5 array, with the columns represent the houses (numbered 1 to 5 for convenience) and the rows corresponding to the attributes, designated as N, C, D, S, and P for the attributes of Nationality, Color, Drink, Smoke, and Pet. Now, it should be noted that there is an ambiguity in the clues, because Clue 9 refers to the “first” house, but doesn’t specify if this is the left-most or the right-most house, and yet Clue 4 refers to the leftward relation. So, we will need to consider the two possible left/right assignments. To begin, we will assume the “first” house is the left-most house, which we designate as house 1. On this basis, clues 9, 14, and 8 lead to the assignments N1 = Nor, C2 = Blu, and D3 = Milk. Then the combination of clues 5 and 4 leads to the further conclusions C4 = Green, C5 = White, D4 = Coffee. It then follows from Clue 1 that C3 = Red, C1 = Yel, N3 = Bri, and hence Clue 7 implies S1 = Dunhill. Once these assignments have been made, Clue 11 implies P2 = Horse. The conclusions up to this point are summarized in the array shown below:

The nationalities of the residents of houses in positions 2, 4, and 5 are still undetermined. They must be populated with the Swede, Dane, and German, and we have three clues to help decide their placement.

2. The Swede keeps dogs.

3. The Dane drinks tea.

13. The German smokes Prince.

Clue 2 implies that the Swede can’t be in house 2, because he keeps Dogs whereas house 2 has a horse. Likewise Clue 3 implies the Dane can’t be in house 4, because he drinks Tea, whereas the resident of house 4 drinks Milk. Therefore, there are only three possible cases to consider for the nationalities in those three houses: 245 = DSG, GSD, or DGS.

Case DSG:

This case is ruled out, because Clue 12 says the owner who smokes Bluemasters drinks beer, whereas in this case the only remaining houses for Bluemasters smoke are 2, 3, or 4, but those are already assigned drinks, and none of them are beer.

Case GSD:

This case, too, is ruled out by Clue 12, because the only remaining houses for Bluemasters are 3, 4, or 5, and those are already assigned drinks, none of them beer.

Case DGS:

This is the only case that is consistent with Clue 12, and it implies that Bluemasters and Beer are in house 5, so we have D5 = Bee and S5 = Blu. Also, Clue 6 implies that Pall Mall and birds go together, but the only house that isn’t already assigned either a different smoke or a different pet is house 3, so we have S3 = Pal and P3 = Bir. After filling in these results, there is only one house without a drink, and one without a smoke, so we must have D1 = Wat and S2 = Ble. This leaves open only the pets for houses 1 and 4, but Clue 10 says Blends is in the house next to Cats, so we have P1 = Cat and therefore P4 = Fis, which completes the solution shown below.

In this solution we did not make use of Clue 15, which states that the owner who smokes Blends lives next to the one who drinks water, although this condition is met by the solution.

As noted above, there is an ambiguity in the problem statement, between Clue 9 referring to the “first” house (without specifying whether it is the left-most or right-most), and Clue 4 referring to the leftward direction. Because of Clue 4, we cannot simply reflect the entire solution deduced above, because that would reverse left and right, so Clue 4 would not be satisfied. We can just as well seek a solution based on defining the “first” house as the right-most house, which we designate as house 5. On this basis, clues 9, 14, and 8 lead to the assignments N5 = Nor, C4 = Blu, and D3 = Milk. However, unlike the previous case, the combination of clues 5 and 4 now does not uniquely imply the positions of Green, White, and Coffee. Instead, we have two possible choices. One of those options (putting C2 = Green, C3 = White, and D2 = Cof) leads to just two possible arrangements for the remaining nationalities, but it can be shown that those both lead to contradictions with other clues. The other viable option is to put C1 = Gre, C2 = Whi, and D1 = Cof. It then follows from Clue 1 that C3 = Red, C5 = Yel, N3 = Bri, and hence Clue 7 implies S5 = Dunhill. Once these assignments have been made, Clue 11 implies P4 = Hor. From this point the solutions proceeds similarly to what was described previously, and we arrive at the alternative solution

Again we did not make use of Clue 15, which states that the owner who smokes Blends lives next to the one who drinks water, but this condition is met by the solution. This solution is just the left-right reflection of the previous solution, except that the German and Swedish houses are transposed. Thus the answer to the original question (“Who owns the fish?”) is the German in both solutions. On the other hand, if we ask how many houses are between the Fish and the Cat, the answer would be either two or three, depending on whether we interpret “first” to be left-most or right-most.

Return to MathPages Main Menu