# Determine as many as possible of $F$ elements

Let $$F$$ be a subset family of the set {$$1, 2, ..., 2017$$} such that for any $$A, B \in F$$, worth that $$A \cap B$$ has exactly one element. Determine as many as possible of $$F$$ elements

Solution: Generalization: if the total number set is $$\{1, 2, ..., n\}$$, then the maximum of $$|F|$$ is $$n$$. In the original problem $$n=2017$$, so $$max|F|=\boxed{2017}$$.

1. We claim that $$|F| \leq n$$ Consider a map from one subset $$A$$ of $$\{1, 2, ..., n\}$$ to a $$n$$-dimension vector $$V=(v_1, v_2, ..., v_n)^T$$. For $$1 \leq i \leq n$$, if $$i \in A$$ then $$v_i=1$$, else $$v_i=0$$. Consider the vector set mapped from $$F$$: $$\{V_1, V_2, ..., V_m\}$$. We could prove the vectors are linearly independent. For $$i \ne j$$, $$=V_i^TV_j=1$$, since there is exactly one element included in any two elements of $$F$$. For $$i = j$$, $$=|V_i| \geq 1$$, where $$|V_i|$$ counts the number of $$1$$ appeared in $$V_i$$. Consider $$S=\sum_{k=1}^{m} a_kV_k$$, if $$S=(0,0,...,0)^T$$, then $$=0$$. However, $$=\sum_{i=1}^{m} a_i^2+\sum_{i \ne j} 2a_ia_j=(\sum_{i=1}^{m} a_i)^2+\sum_{i=1}^{m} a_i^2(|V_i|-1) \geq 0$$. So the equality holds only when $$a_i=0$$, that means $$\{V_1, V_2, ..., V_m\}$$ are linearly independent, so that $$m \leq n$$, so that $$|F| \leq n$$.

2. A construction of $$|F|=n$$ Consider $$F=\{\{a,n\} | 1 \leq a \leq n-1\} \cup\{n\}$$. $$|F|=n$$, and any $$A, B \in F$$, $$A \cap B=\{n\}$$.

I didn't understand the logic of this solution

• what does "worth that" mean? – coffeemath Nov 19 '19 at 23:52
• What part don't you get? Just go through the argument line by line. – lulu Nov 19 '19 at 23:57

## 2 Answers

We can rewrite the argument as follows.

(1). Each set in $$F$$ can be represented as a vector. For example, $$\{2,3,6\}$$ is represented by $$(0,1,1,0,0,1,0,0,...)$$ where a "$$1$$" in the $$i$$th position indicates that the set contains "$$i$$".

If $$|F|=m$$, then we now have $$m$$ such vectors $$V_1,V_2,V_3,...V_m.$$ The crucial fact is that for any pair of these vectors, there is one and only one position where they both have a "$$1$$".

Now suppose we could find numbers $$a_1,a_2,a_3,...a_m$$ such that $$W=\sum_1^m a_iV_i=0.$$

Then the scalar product of $$W$$ with itself is, of course, zero.

We also know that if $$i\ne j$$, then $$V_i.V_j=1,$$ whereas $$V_i.V_i$$ is the number of "$$1$$"s in $$V_i$$ which we can denote by $$||V_i||$$. Note that each $$||V_i||\ge 1$$ and only one $$||V_i||$$ can equal $$1$$.

The scalar product of $$W$$ with itself can be considered to be the sum of lots of scalar products of the form $$a_iV_i.a_jV_j$$. Summing these we obtain $$0=\sum_1^m a_i^2||V_i||+\sum_{i\ne j}a_ia_j=\sum_1^m a_i^2(||V_i||-1)+\sum_1^m a_i^2+\sum_{i\ne j}a_ia_j$$

$$=\sum_1^m a_i^2(||V_i||-1)+(a_1+a_2+... +a_m)^2.$$

The only possibility is that each $$a_i=0$$. The vectors $$V_i$$ are therefore linearly independent and therefore there can be at most $$n$$ of them i.e. $$|F|\le n$$.

(2). The upper bound of $$n$$ can be attained since these $$n$$ sets satisfy the conditions:- $$\{1,n\},\{2,n\},\{3,n\},...\{n-1,n\},\{n\}.$$

How is your linear algebra? It is saying we are constructing vectors in a 2017-dimensional space. I will give the example in $$3$$-D. Let $$\{1,2,3\}$$ be the base set, so the subset $$\{1,3\}$$ maps to the vector $$\begin{bmatrix} 1 \\ 0 \\ 1 \\ \end{bmatrix}$$. Look at what happens if we have linear dependence (this means a "good" combination of the non-zero vectors becomes zero) for example:

$$\begin{bmatrix} 1 \\ 1 \\ 0 \\ \end{bmatrix}-\begin{bmatrix} 0 \\ 1 \\ 0 \\ \end{bmatrix}-\begin{bmatrix} 1 \\ 0 \\ 0 \\ \end{bmatrix}=0$$. Now see that this is like saying in terms of our original sets $$\{1,2\} -\{1\} - \{2\} = \emptyset$$. But notice that $$|\{1,2\}\cap \{1\}|=1, |\{1,2\}\cap \{2\}|=1,$$ BUT $$|\{1\}\cap \{2\}|=0$$.

Try to extend this idea of linear dependence requiring the sets to over or under intersect to the full argument given.