All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Buddy System (Posted on 2005-09-22)
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?

 No Solution Yet Submitted by Sam Rating: 4.3333 (6 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution -- computer assisted | Comment 3 of 8 |

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                 3206952010                  3628800                61664085011                 39916800              1305466470012                479001600             30200583105013               6227020800            758339241660014              87178291200          20546501480505015            1307674368000         597551763258450016           20922789888000       18568757781899325017          355687428096000      614040539937224400018         6402373705728000    21530403323223119325019       121645100408832000   797902979206078295550020      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
Please log in:
 Login: Password: Remember me: Sign up! | Forgot password

 Search: Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information