308 6 Combinatorics and Probability896.A sheet of paper in the shape of a square is cut by a line into two pieces. One of
the pieces is cut again by a line, and so on. What is the minimum number of cuts
one should perform such that among the pieces one can find one hundred polygons
with twenty sides.
897.Twenty-one girls and twenty-one boys took part in a mathematics competition. It
turned out that
(i) each contestant solved at most six problems, and
(ii) for each pair of a girl and a boy, there was at least one problem that was solved
by both the girl and the boy.
Show that there is a problem that was solved by at least three girls and at least
three boys.6.2.4 The Inclusion–Exclusion PrincipleA particular counting method that we emphasize is the inclusion–exclusion principle,
also known as the Boole–Sylvester formula. It concerns the counting of the elements in
a union of setsA 1 ∪A 2 ∪···∪An, and works as follows. If we simply wrote
|A 1 ∪A 2 ∪···∪An|=|A 1 |+|A 2 |+···+|An|,we would overcount the elements in the intersectionsAi∩Aj. Thus we have to subtract
|A 1 ∩A 2 |+|A 1 ∩A 3 |+···+|An− 1 ∩An|. But then the elements in the triple intersections
Ai∩Aj∩Akwere both added and subtracted. We have to put them back. Therefore, we
must add|A 1 ∩A 2 ∩A 3 |+···+|An− 2 ∩An− 1 ∩An|. And so on. The final formula is|A 1 ∪A 2 ∪···∪An|=∑
i|Ai|−∑
i,j|Ai∩Aj|+···+(− 1 )n−^1 |A 1 ∩A 2 ∩···∩An|.Example.How many integers less than 1000 are not divisible by 2, 3, or 5?Solution.To answer the question, we will count instead how many integers between 1
and 1000aredivisible by 2,3, or 5. Denote byA 2 ,A 3 , andA 5 be the sets of integers
divisible by 2,3, respectively, 5. The Boole–Sylvester formula counts|A 2 ∪A 3 ∪A 5 |as|A 2 |+|A 3 |+|A 5 |−|A 2 ∩A 3 |−|A 2 ∩A 5 |−|A 3 ∩A 5 |+|A 2 ∩A 3 ∩A 5 |=⌊
1000
2
⌋
+
⌊
1000
3
⌋
+
⌊
1000
5
⌋
−
⌊
1000
6
⌋
−
⌊
1000
10
⌋
−
⌊
1000
15
⌋
+
⌊
1000
30
⌋
= 500 + 333 + 200 − 166 − 100 − 66 + 33 = 734.
It follows that there are 1000− 734 =266 integers less than 1000 that are not divisible
by 2,3, or 5.