2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $(1,1,1)$ is not a set $\endgroup$ – user261263 Dec 2 '16 at 8:21
  • $\begingroup$ Why is $(1,1,1)$ not a set? $\endgroup$ – model_checker Dec 2 '16 at 8:23
  • $\begingroup$ Sets have distinct elements $\endgroup$ – user261263 Dec 2 '16 at 8:23
  • $\begingroup$ @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. $\endgroup$ – Mees de Vries Dec 2 '16 at 8:38
1
$\begingroup$

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$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.