MathDB

3

Part of 2013 Greece National Olympiad

Problems(1)

Minimum number of sets!

Source: Greek MO 2013 - P3

5/12/2013
We define the sets A1,A2,...,A160A_1,A_2,...,A_{160} such that ∣Ai∣=i\left|A_{i} \right|=i for all i=1,2,...,160i=1,2,...,160. With the elements of these sets we create new sets M1,M2,...MnM_1,M_2,...M_n by the following procedure: in the first step we choose some of the sets A1,A2,...,A160A_1,A_2,...,A_{160} and we remove from each of them the same number of elements. These elements that we removed are the elements of M1M_1. In the second step we repeat the same procedure in the sets that came of the implementation of the first step and so we define M2M_2. We continue similarly until there are no more elements in A1,A2,...,A160A_1,A_2,...,A_{160}, thus defining the sets M1,M2,...,MnM_1,M_2,...,M_n. Find the minimum value of nn.
combinatorics proposedcombinatorics