There are 4 mathematicians m1;m2;m3;m4 and 4 computer scientistsc1; c2; c3; c4. mi and ci are enemies for each i = 1; 2; 3; 4 (i.e.m1 and c1 are enemies, m2 and c2 are enemies etc.). By the end ofpart (d), we ought to know how many ways there are to line up these8 people so that no enemies are next to each other.
(a) How many ways are there to line up the 8 people with norestriction?
(b) How many ways are there to line up the 8 people such that m1and c1 ARE next to each other? Hint: there are 2 ways to arrange m1and c1 between themselves. Then once we have done that, we canimagine them as “glued together". So there are now 7 objects topermute (6 people and 1 glued pair).
(c) How many ways are there to line up the 8 people so that m1and c1 ARE next to each other AND m2 and c2 are next to each other?Hint: use the gluing idea again.
(d) For i = 1; 2; 3; 4 let Ai represent the set of permutationsof the people where mi and ci are next to each other (note in part(b), you found |A1|. Use inclusion-exclusion to find the number ofbad permutations |A1 U A2 U A3 U A4|. Then conclude the number ofgood permutations.
