Determine all possible values of positive integer $n$, such that there are $n$ different 3-element subsets $A_1,A_2,...,A_n$ of the set $\{1,2,...,n\}$, with $|A_i \cap A_j| \not= 1$ for all $i \not= j$.
Problem
Source:
Tags: induction, combinatorics proposed, combinatorics
30.10.2010 17:07
Suppose for some $n$ that the above is possible. We will call all of the subsets $A_1, A_2, \ldots, A_n$ "A-sets". Call a pair $\{a, b\}$ "critical" if there exist two A-sets $A_i, A_j$ such that $A_i \cap A_j = \{a, b\}$. The "connections" of a critical pair $\{a, b\}$ are the set of elements $x$ such that $\{a, b, x\}$ is an A-set. For each critical pair $a, b$, consider the number of connections it has. If it has exactly 2 connections $x, y$ we have $X = \{a, b, x\}$ and $Y = \{a, b, y\}$ are two A-sets. Any A-set containing $a$ would have to contain at least one of $b, x$ and at least one of $b, y$; it must be $\{a, x, y\}$ or $X$ or $Y$. Similarly, any A-set containing $b$ would have to be $\{b, x, y\}$ or $X$ or $Y$. Any A-set containing $x$ would have to contain at least one of $a, b$, so it would have to contain both of $a, b$ or one of $a, b$ and $y$, so again it must be $\{a, x, y\}$ or $\{b, x, y\}$ or $\{a, b, x\}$. Similarly for $y$. In short: If the critical pair $a, b$ has 2 connections $x, y$, any A-set containing one of $\{a, b, x, y\}$ must only contain elements from that set. That is, there are at most 4 A-sets inside that set. If the critical pair $a, b$ has more than 3 connections, suppose $x, y, z$ are three of them. Any A-set containing $a$ would have to contain: - at least one of $b, x$ - at least one of $b, y$ - at least one of $b, z$ Since the A-set has 3 elements, it must contain $b$, and its last element must be one of $a, b$'s connections. Similarly for $b$. Any A-set containing $x$ would have to contain at least one of $a, b$. Suppose it contains $a$. Then it would also have to contain at least one of $b, y$ and at least one of $b, z$, and again, $\{a, b, x\}$ is the only possibility. In short: If the critical pair $a, b$ has more than 3 connections, any A-set containing $a$ or $b$ or one of $a, b$'s connections would have to contain both $a$ and $b$. There would therefore be only as many A-sets as connections. Now we use induction on the hypothesis: In a set with size $n$, no more than $n$ A-sets can exist. For $n = 1, 2, 3$ it is trivial. For $n = 4$, you can select all four 3-element subsets as A-sets. For $n > 4$, suppose a selection of $n + 1$ A-sets exists. There must be a critical pair, or all A-sets would be disjoint and we would need $3n+3$ elements. Let $S$ be the set containing a critical pair and all its connections. Then any A-set with an element in $S$ would have to be completely inside $S$. Therefore any A-set must be completely inside $S$ or completely outside $S$. By the above arguments, there are no more than $|S|$ A-sets completely inside $S$, with equality possible only if $|S| = 4$, and by the induction hypothesis, the elements minus $S$ can contain no more than $n - |S|$ A-sets, for a total of no more than $n$ A-sets. To prove that $n$ A-sets exist only if $n$ is a multiple of 4, essentially the same argument on the hypothesis "In a set with size $n$, if $n$ is not a multiple of 4, no more than $n-1$ A-sets can exist" would work. And if $n$ is a multiple of 4, a valid example would be (all 3-subsets of $\{1, 2, 3, 4\}$, all 3-subsets of $\{5, 6, 7, 8\}$, etc., all 3-subsets of $\{n-3, n-2, n-1, n\}$)