==> 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)