Maths Olympiad Prep

Library / /100 of 520

Combinatorics Difficulty 6.5 National olympiad Find the answer

Find the maximum number of subsets from {1,...,n}\left \{ 1,...,n \right \} such that for any two of them like A,BA,B if ABA\subset B then BA3\left | B-A \right |\geq 3. (Here X\left | X \right | is the number of elements of the set XX.)

Solution

To solve the problem, we need to find the maximum number of subsets of {1,2,,n}\{1, 2, \ldots, n\} such that for any two subsets AA and BB, if ABA \subset B, then BA3|B - A| \geq 3. Here, X|X| denotes the number of elements in the set XX.

1. Initial Observation:
- Consider the set {1,2,,n}\{1, 2, \ldots, n\}.
- We need to ensure that for any two subsets AA and BB where ABA \subset B, the difference in their sizes is at least 3.

2. Grouping Subsets:
- Let's group subsets based on their sizes. Specifically, consider subsets with sizes 3i+13i+1 (if nn is even) or 3i+23i+2 (if nn is odd).
- This grouping ensures that the difference in sizes between any two subsets in the group is at least 3.

3. Counting Subsets:
- The number of subsets of size 3i+13i+1 or 3i+23i+2 can be approximated by summing the binomial coefficients (n3i+1)\binom{n}{3i+1} or (n3i+2)\binom{n}{3i+2}.
- The sum of these binomial coefficients is given by:
i=0n3(n3i+1)ori=0n3(n3i+2) \sum_{i=0}^{\left\lfloor \frac{n}{3} \right\rfloor} \binom{n}{3i+1} \quad \text{or} \quad \sum_{i=0}^{\left\lfloor \frac{n}{3} \right\rfloor} \binom{n}{3i+2}
- This sum is approximately 2n(1)n3\frac{2^n - (-1)^n}{3}.

4. Inductive Proof:
- Base Case: For n=4n = 4, we can manually verify that the maximum number of subsets satisfying the condition is 6. The subsets are {1,2}\{1, 2\}, {2,3}\{2, 3\}, {1,3}\{1, 3\}, {1,4}\{1, 4\}, {2,4}\{2, 4\}, and {3,4}\{3, 4\}.
- Inductive Step: Assume the result holds for n1n-1. We need to prove it for nn.
- Split the subsets into two groups: those that do not contain the element 1 and those that do.
- The first group has at most 2n1(1)n13\frac{2^{n-1} - (-1)^{n-1}}{3} subsets by the inductive hypothesis.
- The second group can be considered by removing the element 1 from each subset, resulting in at most 2n1(1)n13+1\frac{2^{n-1} - (-1)^{n-1}}{3} + 1 subsets (including the subset {1}\{1\}).
- Combining these, we get the total number of subsets as 2n1(1)n13+2n1(1)n13+1=2n(1)n3\frac{2^{n-1} - (-1)^{n-1}}{3} + \frac{2^{n-1} - (-1)^{n-1}}{3} + 1 = \frac{2^n - (-1)^n}{3}.

5. Correction:
- For n=4n = 4, the actual number of subsets satisfying the condition is 6, not 5.
- Therefore, the correct maximum number of subsets is 2n3\left\lceil \frac{2^n}{3} \right\rceil.

The final answer is 2n3\left\lceil \frac{2^n}{3} \right\rceil.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.