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 singlesex 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*w1) people; the first alphabetically of the 2*w2 remaining pupils could be paired with any of 2*w3 students, etc. So with unrestricted pairing, there'd be
(2*w1)*(2*w3)*(2*w5)* ... * 1 possible sets of pairings.
But there must be at least one mixedsex 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 outthe completely mixedsex ones. Well, the pairings that involve Matilda/Susie together are just the ways of pairing the others:
(2*w3)*(2*w5)* ... * 1
So we get
(2*w1)*(2*w3)*(2*w5)* ... * 1  w!  (2*w3)*(2*w5)* ... * 1
which can be simplified to
(2*w2)*(2*w3)*(2*w5)* ... * 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 halfclasssize 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 halfclasssize 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*Num2
40 for I=2*Num3 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 20050922 19:25:02 