# Let $F$ be a set of subsets of the set $\{1,2,3,…,n\}$ such that:

Problem: (Balkan MO 1989 Theme) Let $F$ be a set of subsets of the set $\{1,2,3,...,n\}$ such that:

1. if $A$ is an element of $F$ then $A$ contains exactly three elements.
2. if $A$ and $B$ are two distinct elements of $F$, then $A$ and $B$ share at most one element.

Let $f(n)$ denote the maximum number of elements in $F$ then show that $$\frac{(n-1)(n-2)}{6}\leq f(n)\leq\frac{n(n-1)}{6}.$$

My Attempt: I began by considering a simpler case, say $n=4.$ Then the sets satisfying the first condition are (written as order pairs): $$(1,2,3)$$ $$(4,1,2),(4,1,3),(4,2,3)$$ Thus we get the total number of subsets as: $$1+3=4.$$ Now we have the choice to delete $1,2$ or $3$ sets, in order to obtain $F.$ In this case notice that we will have to delete any $3$ sets in order to obtain a set that satisfies both the conditions. Hence $f(4)=1.$ However, I suspect that for values of $n>4$ we will have more than one value of $f(n)$ since we would have to delete a minimum number of sets in order to be sure that the remaining sets do not share more than one element.

• $(1,1,1)$ is not a set – user261263 Dec 2 '16 at 8:21
• Why is $(1,1,1)$ not a set? – nls Dec 2 '16 at 8:23
• Sets have distinct elements – user261263 Dec 2 '16 at 8:23
• @Supermario, the close vote (not from me) is for "unclear what you're asking", presumably because before the edits, you seemed to be a little confused about your own problem (and still are, given your last sentence). Perhaps it is easier to understand when phrased like this: Fix $n$. Now write $[n] = \{1,\ldots,n\}$. For $F \subseteq \mathcal P([n])$, we call $F$ good if it satisfies conditions 1 and 2. Then $f(n)$ is defined as the number of elements in the largest good set. Thus, $f : \mathbb N \to \mathbb N$ is a function. The question is then to prove bounds of this function. – Mees de Vries Dec 2 '16 at 8:38

## 1 Answer

First up, start by noticing that a set does not contain repeated element so if $A \in F, n = 4$, as soon as you pick one $A$, you cannot pick any other because there is only one element that was not used, and so a second $B$ would have to reuse at least two of the numbers in $A$ and would break the condition of the problem statement regarding the intersections.

Thus $f(4) = 1$, which fits in the inequalities:

$$\frac{(n-1)(n-2)}{6} \leq f(n) \leq \frac{n (n-1)}{6}\iff\\ 1 \leq 1 \leq 2, n = 4$$