Maths Olympiad Prep

Library / /26 of 48

Combinatorics Difficulty 5.9 AIME, harder Prove it Baltic Way

Problem:
What is the largest possible number of subsets of the set {1,2,,2n+1}\{1,2, \ldots, 2n+1\} such that the intersection of any two subsets consists of one or several consecutive integers?

Solution

Solution:
Consider any subsets A1,,AsA_{1}, \ldots, A_{s} satisfying the condition of the problem and let Ai={ai1,,ai,ki}A_{i} = \{a_{i1}, \ldots, a_{i,k_{i}}\} where ai1<<ai,kia_{i1} < \cdots < a_{i,k_{i}}. Replacing each AiA_{i} by Ai={ai1,ai1+1,,ai,ki1,ai,ki}A_{i}' = \{a_{i1}, a_{i1}+1, \ldots, a_{i,k_{i}}-1, a_{i,k_{i}}\} (i.e., adding to it all "missing" numbers) yields a collection of different subsets A1,,AsA_{1}', \ldots, A_{s}' which also satisfies the required condition.

Now, let bib_{i} and cic_{i} be the smallest and largest elements of the subset AiA_{i}', respectively. Then min1iscimax1isbi\min_{1 \leq i \leq s} c_{i} \geq \max_{1 \leq i \leq s} b_{i}, as otherwise some subsets AkA_{k}' and AlA_{l}' would not intersect. Hence there exists an element a1<i<sAia \in \bigcap_{1 < i < s} A_{i}'.

As the number of subsets of the set {1,2,,2n+1}\{1,2, \ldots, 2n+1\} containing aa and consisting of kk consecutive integers does not exceed min(k,2n+2k)\min(k, 2n+2-k), we have s(n+1)+2(1+2++n)=(n+1)2s \leq (n+1) + 2 \cdot (1+2+\cdots+n) = (n+1)^{2}. This maximum will be reached if we take a=n+1a = n+1.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.