Combinatorics and Probability 769|A 1 ∪A 2 ∪···∪An|=(
n
1)
(n− 1 )!−(
n
2)
(n− 2 )!+···+(− 1 )n(
n
n)
1 !.
The number of derangements is thereforen!−|A 1 ∪A 2 ∪···∪An|, which is
n!−(
n
1)
(n− 1 )!+(
n
2)
(n− 2 )!−···+(− 1 )n(
n
n)
0 !.
This number can also be written as
n![
1 −
1
1!
+
1
2!
−···+
(− 1 )n
n!]
.
This number is approximately equal tone!.
901.For a vertexx, denote byAxthe set of vertices connected toxby an edge. Assume
that|Ax|≥n 2 +1 for all verticesx.
Now choose two verticesxandysuch thaty∈Ax. Counting with the inclusion–
exclusion principle, we get
|Ax∪Ay|=|Ax|+|Ay|−|Ax∩Ay|.Rewrite this as
|Ax∩Ay|=|Ax|+|Ay|−|Ax∪Ay|.From the fact that|Ax∪Ay|≤nwe find that|Ax∩Ay|is greater than or equal to
2⌊n
2⌋
+ 2 −n≥ 1.If follows that the setAx∩Aycontains some vertexz, and sox, y, zare the vertices of
a triangle.
(D. Bu ̧sneag, I. Maftei,Teme pentru cercurile ̧si concursurile de matematic ̆a(Themes
for mathematics circles and contests), Scrisul Românesc, Craiova)
902.If them-gon has three acute angles, say at verticesA, B, C, then with a fourth vertex
Dthey form a cyclic quadrilateralABCDthat has three acute angles, which is impossible.
Similarly, if them-gon has two acute angles that do not share a side, say at verticesAand
C, then they form with two other verticesBandDof them-gon a cyclic quadrilateral
ABCDthat has two opposite acute angles, which again is impossible. Therefore, the
m-gon has either exactly one acute angle, or has two acute angles and they share a side.
To count the number of suchm-gons we employ the principle of inclusion and exclu-
sion. Thus we first find the number ofm-gons with at least one acute angle, then subtract
the number ofm-gons with two acute angles (which were counted twice the first time).