1. Suppose you have a set of men {A, B, C, D, E, F, G} and a set of women {a, b, c, d, e, f, g}. Suppose that: Man A is compatible with women a c d e f Man B is compatible with women b c e g Man C is compatible with women b c e Man D is compatible with women a b c d f g Man E is compatible with women b c g Man F is compatible with women b e g Man G is compatible with women c e g a) Execute the matching algorithm, showing your steps, from the point of view of the men. The algorithm will lead you to the conclusion that there exists no way to match each man to a compatible woman. Specifically, the algorithm produces a set of men compatible only with women in an even smaller set (what we've been calling a fussy bunch of men.) b) Which men belong to this set? c) Draw the alternating tree from which you arrive at this set d) Now the matching algorithm from the point of view of the women. e) Find a set of women only compatible with a smaller set of men. Answer: a) Provisionally match A to a; provisionally match B to b; provisionally match C to c; provisionally match D to d; provisionally match E to g; provisionally match F to e. Now G is compatible only with provisionally matched women, so build a tree: G (! shows a provisional match) / | \ c e g ! ! ! C F E | b ! B Since B, F and E are only compatible with women already in the tree, the algorithm halts. b) {B C E F G} form a fussy bunch since these men are compatible only with (some of) the women in the set {b c e g}. c) See the last step in a) above. d) Provisionally match a to A Provisionally match b to B Provisionally match c to C Provisionally match d to D Provisionally match e to F Now f is compatible only with men A and D who are already provisionally matched, so build a tree: f / \ A D ! ! a d Since a and d are only compatible with men already in the tree, the algorithm halts. e) {a d f} are only compatible with men in {A,D}. 2. Consider the following variation on our card trick: The view selects 6 cards from a deck. The assistant places three cards of his choice face up in an order of his choice. From only this information the magician determines the other three cards. How large could the deck be? Answer: The number of three-card-suites from a deck of n cards equals PP(3,n)=n x n-1 x n-2 . The number of six-card-hands from a deck of n cards equals C(6,n) = n x n-1 x n-2 x n-3 x n-4 x n-5 /6! . For the trick to be possible, the number of three-card-suites must be no less than the number of six-card-hands (otherwise the assistant wouldn't have enough codes to signal all the possible situation even if the three-card-suite didn't have to come from the six-card-hand. So we need n x n-1 x n-2 >= n x n-1 x n-2 x n-3 x n-4 x n-5 /6! ( here >= means ``greater than or equal to'' ). We can cancel n x n-1 x n-2 from both sides and clear the denominator, getting 720 >= n-3 x n-4 x n-5 . Since 720 = 10 x 9 x 8 on the nose, we have equality with n = 13. 3. How many necklaces can you make using 4 beads having one of n colors? Answer: One can subject a 4-bead-necklace to 8 motions, rotations by 0, 90, 180, 270 degrees, two flips on axes that pass through bead, two flips on axes that pass between beads. 4 0 degree rotation: n necklaces remain unchanged (all of them, n choice for each bead) 90 degree rotation: n necklaces remain unchanged (all beads must have the same color) 2 180 degree rotation: n necklaces remain unchanged (opposite beads must have the same color) 270 degree rotation: n necklaces remain unchanged (all beads must have the same color) 3 flip on axis through beads: n necklaces remain unchanged (pick a color for each stationary bead and one for the interchanging pair) 2 flip on axis between beads: n necklaces remain unchanged (pick one color for each interchanging pair) Putting it all together we get the formula 4 2 3 2 3 2 n + n + n + n + n + n + n + n _____________________________________________ 8