Let $n$ be a positive integer and $A=\{ 1,2,\ldots ,n\}$. A subset of $A$ is said to be connected if it consists of one element or several consecutive elements. Determine the maximum $k$ for which there exist $k$ distinct subsets of $A$ such that the intersection of any two of them is connected.
Problem
Source:
Tags: floor function, ceiling function, combinatorics proposed, combinatorics
25.02.2011 02:53
First, a lower bound: we can achieve $k = \left\lfloor\frac{n + 1}{2}\right\rfloor \cdot \left\lceil\frac{n + 1}{2}\right\rceil$ by taking the set of intervals of the form $[i, j]$ with $i \leq \left\lfloor\frac{n + 1}{2}\right\rfloor \leq j$. Second, this is tight: for any subset $X \subset A$, define $f(X)$ to be the smallest interval containing $X$, i.e., the interval $[\min(X), \max(X)]$. Observe that for two sets $X$ and $Y$, if $\min X = \min Y$ and $\max X = \max Y$ and $X \cap Y$ is an interval then necessarily $X = f(X) = Y$. Consequently, if $X$ and $Y$ are two sets from our collection, we must have $f(X) \neq f(Y)$. Now replace every set $X$ in our collection with the set $f(X)$. These sets are all intervals and every pair intersect, so every pair intersect in an interval, and in particular the modified collection satisfies our conditions. Now the problem is reduced to collections of intervals. A collection of intervals with pairwise nonempty intersection actually has the property that the intersection of all elements in the collection is nonempty; in particular, it contains some point $t$. Thus, a maximal collection is of the form "all the intervals containing point $t$." The size of such a collection is maximized when $t = \left\lfloor \frac{n + 1}{2}\right\rfloor$ or $t = \left\lceil \frac{n + 1}{2}\right\rceil$; in either case, the resulting collection has the size given above. A variation is to define "connected" so as to include the empty set as well. In this case, the same sort of argument applies (actually, life is easier in this case) and we have that the resulting maximum size is $\binom{n}{2} + \binom{n}{1} + \binom{n}{0}$, achieved when we include all intervals and the empty set in our collection.