This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

I took some nephews and nieces to the Zoo, and we halted at a cage marked

Tovus Slithius, male and female.

Beregovus Mimsius, male and female.

Rathus Momus, male and female.

Jabberwockius Vulgaris, male and female.

The eight animals were asleep in a row, and the children began to guess

which was which. "That one at the end is Mr Tove." "No, no! It's Mrs

Jabberwock," and so on. I suggested that they should each write down

the names in order from left to right, and offered a prize to the one

who got most names right.

As the four species were easily distinguished, no mistake would arise in

pairing the animals; naturally a child who identified one animal as Mr

Tove identified the other animal of the same species as Mrs Tove.

The keeper, who consented to judge the lists, scrutinised them carefully.

"Here's a queer thing. I take two of the lists, say, John's and Mary's.

The animal which John supposes to be the animal which Mary supposes to be

Mr Tove is the animal which Mary supposes to be the animal which John

supposes to be Mrs Tove. It is just the same for every pair of lists,

and for all four species.

"Curiouser and curiouser! Each boy supposes Mr Tove to be the animal

which he supposes to be Mr Tove; but each girl supposes Mr Tove to be

the animal which she supposes to be Mrs Tove. And similarly for the oth-

er animals. I mean, for instance, that the animal Mary calls Mr Tove

is really Mrs Rathe, but the animal she calls Mrs Rathe is really Mrs

Tove."

"It seems a little involved," I said, "but I suppose it is a remarkable

coincidence."

"Very remarkable," replied Mr Dodgson (whom I had supposed to be the

keeper) "and it could not have happened if you had brought any more

children."

How many nephews and nieces were there? Was the winner a boy or a girl?

And how many names did the winner get right? [by Sir Arthur Eddington]

logic/zoo.s

Given that there is at least one boy and one girl (John and Mary are

mentioned) then the answer is that there were 3 nephews and 2 nieces,

the winner was a boy who got 4 right.

Number the animals 1 through 8, such that the females are even and the

males are odd, with members of the same species consecutive; i.e. 1 is

Mr. Tove, 2 Mrs. Tove, etc.

Then each childs guesses can be represented by a permutation. I use

the standard notation of a permutation as a set of orbits. For

example: (1 3 5)(6 8) means 1 -> 3, 3 -> 5, 5 -> 1, 6 -> 8, 8 -> 6 and

2,4,7 are unchanged.

[1] Let P be any childs guesses. Then P(mate(i)) = mate(P(i)).

[2] If Q is another childs guesses, then [P,Q] = T, where [P,Q] is the

commutator of P and Q (P composed with Q composed with P inverse

composed with Q inverse) and T is the special permutation (1 2) (3 4)

(5 6) (7 8) that just swaps each animal with its spouse.

[3] If P represents a boy, then P*P = I (I use * for composition, and

I for the identity permutation: (1)(2)(3)(4)(5)(6)(7)(8)

[4] If P represents a girl, then P*P = T.

[1] and [4] together mean that all girl's guesses must be of the form:

(A B C D) (E F G H) where A and C are mates, as are B & D,

E & F G & H.

So without loss of generality let Mary = (1 3 2 4) (5 7 6 8)

Without to much effort we see that the only possibilities for other

girls "compatible" with Mary (I use compatible to mean the relation

expressed in [2]) are:

g1: (1 5 2 6) (3 8 4 7) g2: (1 6 2 5) (3 7 4 8) g3: (1 7 2 8) (3 5 4 6) g4: (1 8 2 7) (3 6 4 5)

Note that g1 is incompatible with g2 and g3 is incompatible with g4.

Thus no 4 of Mary and g1-4 are mutually compatible. Thus there are at

most three girls: Mary, g1 and g3 (without loss of generality)

By [1] and [3], each boy must be represented as a product of

transpostions and/or singletons: e.g. (1 3) (2 4) (5) (6) (7) (8) or

(1) (2) (3 4) (5 8) (6 7).

Let J represent John's guesses and consider J(1).

If J(1) = 1, then J(2) = 2 (by [1]) using [2] and Mary J(3) = 4, J(4) =

3, and g1 & J => J(5) = 6, J(6) = 5, & g3 & J => J(8) = 7 J(7) = 8

i.e. J = (1)(2)(3 4)(5 6)(7 8). But the [J,Mary] <> T. In fact, we

can see that J must have no fixed points, J(i) <> i for all i, since

there is nothing special about i = 1.

If J(1) = 2, then we get from Mary that J(3) = 3. contradiction.

If J(1) = 3, then J(2) = 4, J(3) = 1, J(4) = 2 (from Mary) =>

J(5) = 7, J(6) = 8, J(7) = 5, J(8) = 6 => J = (1 3)(2 4)(5 7)(6 8)

(from g1)

But then J is incompatible with g3.

A similar analysis shows that J(1) cannot be 4,5,6,7 or 8; i.e. no J

can be compatible with all three girls. So without loss of generality,

throw away g3.

We have Mary = (1 3 2 4) (5 7 6 8)

g1 = (1 5 2 6) (3 8 4 7)

The following are the only possible boy guesses which are compatible

with

both of these:

B1: (1)(2)(3 4)(5 6)(7)(8) B2: (1 2)(3)(4)(5)(6)(7 8) B3: (1 3)(2 4)(5 7)(6 8) B4: (1 4)(2 3)(5 8)(6 7) B5: (1 5)(2 6)(3 8)(4 7) B6: (1 6)(2 5)(3 7)(4 8)

Note that B1 & B2 are incombatible, as are B3 & B4, B5 & B6, so at most

three of them are mutually compatible. In fact, Mary, g1, B1, B3 and

B5 are all mutually compatible (as are all the other possibilities you

can get by choosing either B1 or B2, B3 or B4, B5 or B6. So if there

are 2 girls there can be 3 boys, but no more, and we have already

eliminated the case of 3 girls and 1 boy.

The only other possibility to consider is whether there can be 4 or

more boys and 1 girl. Suppose there are Mary and 4 boys. Each boy

must map 1 to a different digit or they would not be mutually

compatible. For example if b1 and b2 both map 1 to 3, then they both

map 3 to 1 (since a boy's map consists of transpositions), so both

b1*b2 and b2*b1 map 1 to 1. Furthermore, b1 and b2 cannot map 1 onto

spouses. For example, if b1(1) = a and b is the spouse of a, then

b1(2) = b. If b2(1) = b, then b2(2) = a. Then b1*b2(1) = b1(b) = 2

and b2*b1(1) = b2(a) = 2 (again using the fact that boys are all

transpostions). Thus the four boys must be:

B1: (1)(2)... or (1 2).... B2: (1 3)... or (1 4) ... B3: (1 5) ... or (1 6) ... B4: (1 7) ... or (1 8) ...

Consider B4. The only permutation of the form (1 7)... which is

compatible

with Mary ( (1 3 2 4) (5 7 6 8) ) is:

(1 7)(2 8)(3 5)(4 6)

The only (1 8)... possibility is:

(1 8)(2 7)(3 6)(4 5)

Suppose B4 = (1 7)(2 8)(3 5)(4 6)

If B3 starts (1 5), it must be (1 5)(2 6)(3 8)(4 7) to be compatible

with B4. This is compatible with Mary also.

Assuming this and B2 starts with (1 3) we get B2 = (1 3)(2 4)(5 8)(6 7)

in order to be compatible with B4. But then B2*B3 and B3*B2 moth map 1

to 8. I.e. no B2 is mutually compatible with B3 & B4.

Similarly if B2 starts with (1 4) it must be (1 4)(2 3)(5 7)(6 8) to

work with B4, but this doesn't work with B3.

Likewise B3 starting with (1 6) leads to no possible B2 and the

identical reasoning eliminates B4 = (1 8)...

So no B4 is possible!

I.e at most 3 boys are mutually compatiblw with Mary, so 2 girls & 3

boys is optimal.

Thus:

Mary = (1 3 2 4) (5 7 6 8) Sue = (1 5 2 6) (3 8 4 7) John = (1)(2)(3 4)(5 6)(7)(8) Bob = (1 3)(2 4)(5 7)(6 8) Jim = (1 5)(2 6)(3 8)(4 7)

is one optimal solution, with the winner being John (4 right: 1 2 7 & 8)

Continue to: