Problem:
What is the largest possible number of subsets of the set such that the intersection of any two subsets consists of one or several consecutive integers?
Solution
Solution:
Consider any subsets satisfying the condition of the problem and let where . Replacing each by (i.e., adding to it all "missing" numbers) yields a collection of different subsets which also satisfies the required condition.
Now, let and be the smallest and largest elements of the subset , respectively. Then , as otherwise some subsets and would not intersect. Hence there exists an element .
As the number of subsets of the set containing and consisting of consecutive integers does not exceed , we have . This maximum will be reached if we take .
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.