Miss Honey and Miss Wormwood were taking their classes out on an outing. The two classes were of different sizes, but in each class there were the same number of girls as boys.

Miss Honey told the children in her class to form pairs, each consisting of a boy and a girl. For her own amusement, mentally calculated the number of different ways this could be done.

Miss Wormwood also told her class to form into pairs, but with at least one single-sex pair. She also insisted that the girls Matilda and Susie did not pair up together as they were the most troublesome of her girls. She too calculated the number of different ways that this could be done.

Both teachers arrived at the same answer. How many children were in each class?

If Miss Honey's class size is 2*h (h boys and h girls), and Miss Wormwood's class size is 2*w (w boys and w girls), then:

The number of pairings in Miss Honey's class is just h!, as the boys can be lined up alphabetically and there are h! ways of arranging the girls next to them.

In Miss Wormwood's class, if any pairing would do, the first person alphabetically could be paired with any of (2*w-1) people; the first alphabetically of the 2*w-2 remaining pupils could be paired with any of 2*w-3 students, etc.  So with unrestricted pairing, there'd be

(2*w-1)*(2*w-3)*(2*w-5)* ... * 1 possible sets of pairings.

But there must be at least one mixed-sex pairing. That eliminates w!, as that's analagous to what we calculated for Miss Honey.

But all pairings that involve Matilda being paired with Susie must also be eliminated.  Fortunately these pairings are mutually exclusive with the other set we're subtracting out--the completely mixed-sex ones.  Well, the pairings that involve Matilda/Susie together are just the ways of pairing the others:

(2*w-3)*(2*w-5)* ... * 1

So we get

(2*w-1)*(2*w-3)*(2*w-5)* ... * 1 - w! - (2*w-3)*(2*w-5)* ... * 1

which can be simplified to

(2*w-2)*(2*w-3)*(2*w-5)* ... * 1 - w!

noting that the first two factors in the first term differ by only 1, but the rest differ by two, from one to the next.

We can tabulate the values by half-class-size for the Honey formula and the Wormwood formula:

 1                        1                       -1
 2                        2                        0
 3                        6                        6
 4                       24                       66
 5                      120                      720
 6                      720                     8730
 7                     5040                   119700
 8                    40320                  1851570
 9                   362880                 32069520
10                  3628800                616640850
11                 39916800              13054664700
12                479001600             302005831050
13               6227020800            7583392416600
14              87178291200          205465014805050
15            1307674368000         5975517632584500
16           20922789888000       185687577818993250
17          355687428096000      6140405399372244000
18         6402373705728000    215304033232231193250
19       121645100408832000   7979029792060782955500
20      2432902008176640000 311627759338231702616250

If both were allowed the same class size, each could have 6 students (twice the half-class-size of 3), and there'd be 6 ways each.  But the puzzle disallows them having the same class size.

That leaves 720 as the only number appearing in both columns, with Miss Honey having a class size of 6*2=12, and Miss Wormwood having 5*2=10.

   10   for Num=1 to 20
   15   print using(3,0),Num;
   20   print using(25,0),!(Num);
   30   T=2*Num-2
   40   for I=2*Num-3 to 1 step -2
   45    T=T*I
   50   next
   60   T=T-!(Num)
   90   print using(25,0),T
  100   next

Posted by Charlie on 2005-09-22 19:25:02