Maths Olympiad Prep

Library / /10 of 19

Combinatorics Difficulty 6.3 National olympiad Find the answer

For each interger n4n\geq 4, we consider the mm subsets A1,A2,,AmA_1, A_2,\dots, A_m of {1,2,3,,n}\{1, 2, 3,\dots, n\}, such that
A1A_1 has exactly one element, A2A_2 has exactly two elements,...., AmA_m has exactly mm elements and none of these subsets is contained in any other set. Find the maximum value of mm.

A number or a short expression. Spacing and $ signs are ignored.

Solution

To find the maximum value of m m , we need to evaluate the constraints given by the problem, specifically that none of the subsets A1,A2,,Am A_1, A_2, \ldots, A_m is contained in any other subset. Each subset Ai A_i has exactly i i elements.

Let's consider the key points to derive the maximum value of m m :

1. Condition on Subsets:
- There are n n distinct elements in total.
- Subset A1 A_1 contains exactly 1 element, A2 A_2 contains exactly 2, and so on, up to Am A_m , which contains exactly m m elements.
- No subset Ai A_i is contained within another subset Aj A_j .

2. Binomial Coefficient Representation:
- The total number of ways to choose subsets of varying sizes from a set with n n elements is given by the binomial coefficients.
- Therefore, for subset Ai A_i , a key constraint is that (ni)\binom{n}{i} must account for at least i i elements being distinct in the choice so that none of the subsets are contained within another.

3. **Deriving the Maximum m m :**
- To adhere to the condition that none of these subsets is contained in any other subset, the sum of sizes of all subsets cannot exceed n n , the total number of distinct elements:
1+2++mn 1 + 2 + \dots + m \leq n
- The left hand side is the sum of the first m m positive integers, which is m(m+1)2\frac{m(m + 1)}{2}.
- So, we form the inequality:
m(m+1)2n \frac{m(m + 1)}{2} \leq n

4. Solving the Inequality:
- Multiply both sides by 2 to clear the fraction:
m(m+1)2n m(m + 1) \leq 2n
- This quadratic inequality can be solved for m m by rearranging and setting up the quadratic equation:
m2+m2n=0 m^2 + m - 2n = 0
- Using the quadratic formula:
m=1±1+8n2 m = \frac{-1 \pm \sqrt{1 + 8n}}{2}
- Since m m has to be a positive integer and we want the maximum m m , we use the floor function:
m=1+1+8n2 m = \left\lfloor \frac{-1 + \sqrt{1 + 8n}}{2} \right\rfloor

Thus, the maximum value of m m is:
1+1+8n2 \boxed{\left\lfloor \frac{-1 + \sqrt{1 + 8n}}{2} \right\rfloor}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.