Principle of Inclusion and Exclusion

Question

Annually, the 65 members of the maintenance staff sponsor a “Christmas in July” picnic for the 400 summer employees at their company. For these 65 people,

• 21 bring hot dogs,
• 35 bring fried chicken,
• 28 bring salads,
• 32 bring desserts,
• 13 bring hot dogs and fried chicken,
• 10 bring hot dogs and salads,
• 9 bring hot dogs and desserts,
• 12 bring fried chicken and salads,
• 17 bring fried chicken and desserts,
• 14 bring salads and desserts,
• 4 bring hot dogs, fried chicken, and salads,
• 6 bring hot dogs, fried chicken, and desserts,
• 5 bring hot dogs, salads, and desserts,
• 7 bring fried chicken, salads, and desserts, and
• 2 bring all four food items.

Those (of the 65) who do not bring any of these four food items are responsible for setting up and cleaning up for the picnic. How many of the 65 maintenance staff will

(a) help to set up and clean up for the picnic?

(b) bring only hot dogs?

(c) bring exactly one food item?

What I have so far is:

• $c_1=$ Staff members who bring hot dogs
• $c_2=$ Staff members who bring fried chicken
• $c_3=$ Staff members who bring salads
• $c_4=$ Staff members who bring desserts

$$N=65$$ $$N(c_1)=21,\quad N(c_2)=35,\quad N(c_3)=28,\quad N(c_4)=32$$ $$N(c_1c_2)=13,\quad N(c_1c_3)=10,\quad N(c_1c_4)=9,\quad N(c_2c_3)=12,\quad N(c_2c_4)=17,\quad N(c_3c_4)=14$$

Am I on the right track or way off course?

Answer 1

You need to complete the list and apply the formulas, but you seem to be on the right track.

Using the Generalized Principle of Inclusion-Exclusion, we compute:

$N(0)=65$
$N(1)=21+35+28+32=116$
$N(2)=13+10+9+12+17+14=75$
$N(3)=4+6+5+7=22$
$N(4)=2=2$

$65\binom{0}{0}-116\binom{1}{0}+75\binom{2}{0}-22\binom{3}{0}+2\binom{4}{0}=4$ bring nothing
$\hphantom{65\binom{0}{1}-}116\binom{1}{1}-75\binom{2}{1}+22\binom{3}{1}-2\binom{4}{1}=24$ bring one item
$\hphantom{65\binom{0}{1}-116\binom{1}{1}+}75\binom{2}{2}-22\binom{3}{2}+2\binom{4}{2}=21$ bring two items
$\hphantom{65\binom{0}{1}-116\binom{1}{1}+75\binom{2}{2}-}22\binom{3}{3}-2\binom{4}{3}=14$ bring three items
$\hphantom{65\binom{0}{1}-116\binom{1}{1}+75\binom{2}{2}-22\binom{3}{3}+}2\binom{4}{4}=2$ bring four items

Counting only people who brought hot dogs (and possibly other items):

$N(0)=21+0+0+0=21$
$N(1)=13+10+9+0+0+0=32$
$N(2)=4+6+5+0=15$
$N(3)=2=2$

$21\binom{0}{0}-32\binom{1}{0}+15\binom{2}{0}-2\binom{3}{0}=2$ bring nothing else (just hot dogs)
$\hphantom{21\binom{0}{1}-}32\binom{1}{1}-15\binom{2}{1}+2\binom{3}{1}=8$ bring one item (in addition to hot dogs)
$\hphantom{21\binom{0}{1}-32\binom{1}{1}+}15\binom{2}{2}-2\binom{3}{2}=9$ bring two items (in addition to hot dogs)
$\hphantom{21\binom{0}{1}-32\binom{1}{1}+15\binom{2}{2}-}2\binom{3}{3}=2$ bring three items (in addition to hot dogs)

Answers:

a) $4$ people brought nothing
b) $2$ people bring only hot dogs
c) $24$ people bring only one food item