1
$\begingroup$

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, V_j>=V_i^TV_j=1$, since there is exactly one element included in any two elements of $F$. For $i = j$, $<V_i, V_i>=|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 $<S, S>=0$. However, $<S, S>=\sum_{i=1}^{m} a_i^2<V_i, V_i>+\sum_{i \ne j} 2a_ia_j<V_i, V_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

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

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\}.$$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\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.