Limited Intersections

To begin with we will show that $f(n) > n$ when $n \geq 10$ . Let us only consider $n \geq 10$ when $n$ is even to begin with. All we have to do is show that we can always make $n+1$ 3 element subsets such that no 2 subsets share more than 1 element. These subsets are shown below: $(1,2,3)$ , $(1,4,5)$ , $(1,6,7)$ , $(1,...,...)$ , $(1,n-2,n-1)$
These are $\dfrac{n-2}{2}$ subsets.

$(n,2,2+\frac{n-2}{2})$ , $(n,3,3+\frac{n-2}{2})$ , $(n,...,...)$ , $(n,\frac{n}{2},n-1)$

These are another $\dfrac{n-2}{2}$ subsets.

Therefore so far we have $2 \times \dfrac{n-2}{2} = n - 2$ subsets. So we need to find 3 more (we should also not that at this point excluding $1,n$ any number has only been in a subset with a number 1 different from itself or $\dfrac{n-2}{2}$ different from itself). Also, for $n \geq 10$ , $5+\dfrac{n-2}{2} \le n-1$ . Therefore the following 3 subsets will also be valid for $n \geq 10$ and even: $(2,4,3+\dfrac{n-2}{2})$ $(3,5,4+\dfrac{n-2}{2})$ $(4,6,5+\dfrac{n-2}{2})$ So, we have shown that if $n \geq 10$ and even then $f(n) > n$ . Now consider if $n \geq 11$ and odd. For any such value, consider adding the element $2x+1$ to the set $(1,2,...,2x)$ . From all the work we just did on even numbers $n \geq 10$ we know that we can break the set $(1,2,...,2x)$ into at least $2x+1$ subsets of 3 elements so that no 2 subsets share more than 1 element. Just as importantly, when we divided these numbers into subsets, $1$ and $2x$ (in our case this was $n$ ) were never in the same subset. Therefore, when we consider the set $(1,2,...,2x,2x+1)$ , we can use all the subsets which we did when considering $(1,2,...,2x)$ as well as the subset $(1,2x,2x+1)$ . So, we now know that $f(2x+1) \geq f(2x) + 1$ $f(2x+1) \geq 2x + 2$ So, we have now also shown that $f(n) > n$ for $n \geq 11$ and odd. Combining our 2 results means we know that $f(n) > n$ for $n \geq 10$
Therefore we must now consider $n \le 9$ . I will set an upper bound on $f(n)$ for such values. In every subset an element is in there are 2 other elements. But no 2 subsets can share 2 elements. So the maximum number of subsets which an element can be in is $\lfloor \dfrac{n-1}{2} \rfloor$ . Since this is true for all elements, $f(n) \le n \times \lfloor \dfrac{n-1}{2} \rfloor$ . However, each subset actually has 3 elements, so we have counted every subset 3 times. Therefore $f(n) \le \lfloor \dfrac{n \times \lfloor \dfrac{n-1}{2} \rfloor}{3} \rfloor$ . Let this bound be $g(n)$ . Evaluating this across the relevant values of $n$ (we consider $n=1,2,3$ to be trivial cases which do not satisfy the conditions): $g(4) = 1$ $g(5) = 3$ $g(6) = 4$ $g(7) = 7$ $g(8) = 8$ $g(9) = 12$ So now we have even fewer cases to consider, only $n=7,8,9$ (since for the other values, the upper bound on $f(n)$ is less than $n$ ). However, we must construct subsets to see if these values can be achieved. For $n=7,8$ the subsets are simple to construct to show that indeed $f(7) = 7$ and $f(8) = 8$ . Fortunately, to disprove it for $n=9$ we just have to show that $f(9) \geq 10$ , which again is quite simple. I leave you to construct these 3 sets of subsets yourself. So the only values of $n$ are 7 and 8, so there are $\fbox{2}$ values

Basing on Point Trouble Problem , we can think of Limited Intersections like:

For how many positive integers $n$ is it true that the maximum number of triangles formed out of $n$ points in the plane such that no three of them are collinear, with the special property that no two triangles have more than one vertex in common is $n.$

I just want to contribute the main idea to solve this problem.

• The number of edges in such graph is $3 \cdot n \leq {n \choose 2} \Rightarrow n \geq 7.$
• $n = 7$ , we have $3 \cdot f(7) \leq {7 \choose 2} \Rightarrow f(7) \leq 7$ . Besides, we can draw a graph containing $7$ triangles satisfying the condition as below figure so $f(7) = 7.$

• $n = 8$ , we have $3 \cdot f(8) \leq {8 \choose 2} \Rightarrow f(8) \leq 9$ .

  However, if $f(8) = 9$ , the graph will have $9 \cdot 3 = 27$ over possible ${8 \choose 2} = 28$ edges. It means that there exists $2$ points unconnected, let's call A, B so there is no triangle satisfying the problem which contains A, B .

  Only $6$ triangles satisfying the problem which contains either A or B are drawn as below picture.

  Basing on the picture, we see that we can not create any triangle satisfying the problem which does not contain A and B .

$\Rightarrow f(8) \neq 9$ .

Besides, we can draw a graph containing $8$ triangles satisfying the condition as below figure so $f(8) = 8.$

• Prove $f(n) > n$ , for all $n \geq 9$ :

The basis step : is illustrated as below picture. We partition $9$ points into three groups, each group forms out a triangle and $9$ others triangles with green, yellow and pink are in the picture.

The inductive step : we divide $n$ point into a group of $n - 1$ points and remaining point.

If every pair of two points in the group of $n - 1$ points is connected, the group contains $\frac {{n - 1 \choose 2}}{3} > n.$

If there exists a pair of two points in the group of $n - 1$ points, $f(n) = f(n - 1) +$ ( $1$ triangle formed out by that pair and the remaining point) $> n.$

Answer: $\boxed{2}$

We want to find an $n$ value s.t $f(n) > n$ . And after doing a while I found an interesting set-up with $n = 9$

1 2 3 
4 5 6 
7 8 9

With this set-up, we have some subsets: $\{1, 2, 3\}, \{4, 5, 6\}, \{7, 8, 9\} \\ \{1, 4, 7\}, \{2, 5, 8\}, \{3, 6, 9\} \\ \{1, 5, 9\}, \{3, 5, 7\}, \\ \{1, 6, 8\}, \{3, 4, 8\}$ and $\{2, 6, 7\}$

This example tells us that $f(9) >= 11 > 9$

Now, we wish to prove that $\forall n > 9, f(n) > n$

Firstly, we divide $(1, 2, 3, \dots, n)$ into two subsequences: $(1,2, \dots, 9)$ and $(10, \dots, n)$ .

The first subsequence gives us $10$ subsets as in above example (notice: we don't count the last subset $\{2, 6, 7\}$ ).

We use the last subset $\{2, 6, 7\}$ for other purpose. For each $i$ in $(10, \dots, n)$ , we generate an subset $\{2, 6, i \}$

So, we will have $f(n) \ge 10 + (n - 10 + 1) = n + 1 > n, \forall n > 9$

Now, we know that $3 \le n < 9$ . With some effort or 3 tries, we got $2$ as the answer

I found two values of n $(n=\boxed{2}): n=7, n=10$ With some subsets with three elements are: $S(7)={(1,2,3),(1,4,5),(1,6,7),(2,4,6),(2,5,7),(3,4,7),(3,5,6)}$ $S(10)={(1,2,3),(1,4,5),(1,6,7),(1,8,9),(2,4,6),(2,5,7),(2,8,10),(3,4,7),(3,5,6),(3,9,10)}$