Advanced book on Mathematics Olympiad

766 Combinatorics and Probability

895.(a) For fixedx ∈A, denote byk(x)the number of setsB ∈Fthat containx.
List these sets asB 1 ,B 2 ,...,Bk(x). ThenB 1 {x},B 2 {x},...,Bk(x){x}are disjoint
subsets ofA{x}. Since eachBi{x}hasn−1 elements, andA{x}hasn^2 −1 elements,
k(x)≤n

(^2) − 1
n− 1 =n+1. Repeating the argument for allx∈Aand adding, we obtain
∑
x∈A
k(x)≤n^2 (n+ 1 ).
But
∑
x∈A
k(x)=

∑

B∈F

|B|=n|F|.

Therefore,n|F|≤n^2 (n+ 1 ), which implies|F|≤n^2 +n, proving (a).
For (b) arrange the elements 1, 2 ,...,9 in a matrix

123

456

789

and choose the sets ofFas the rows, columns, and the “diagonals’’ that appear in the
expansion of the 3×3 determinant:

{ 1 , 2 , 3 },{ 4 , 5 , 6 },{ 7 , 8 , 9 },{ 1 , 4 , 7 },{ 2 , 5 , 8 },{ 3 , 6 , 9 },

{ 1 , 5 , 9 },{ 2 , 6 , 7 },{ 3 , 4 , 8 },{ 3 , 5 , 7 },{ 2 , 4 , 9 },{ 1 , 6 , 8 }.

Itis straightforward to check that they provide the required counterexample.
(Romanian Team Selection Test for the International Mathematical Olympiad, 1985)

896.At every cut the number of pieces grows by 1, so afterncuts we will haven+ 1
pieces.
Let us evaluate the total number of vertices of the polygons afterncuts. After each
cut the number of vertices grows by 2 if the cut went through two vertices, by 3 if the cut
went through a vertex and a side, or by 4 if the cut went through two sides. So aftern
cuts there are at most 4n+4 vertices.
Assume now that afterNcuts we have obtained the one hundred polygons with 20
sides. Since altogether there areN+1 pieces, besides the one hundred polygons there
areN+ 1 −100 other pieces. Each of these other pieces has at least 3 vertices, so the
total number of vertices is 100· 20 +(N− 99 )·3. This number does not exceed 4N+4.
Therefore,

4 N+ 4 ≥ 100 · 20 +(N− 99 )· 3 = 3 N+ 1703.

We deduce thatN≥1699.