Question about members in sets Let $A_1,A_2,...,A_n$ be sets with $k$ members in $A_i$ for every $1\le i\le n$. Suppose that the $A_i$ satisfy:
1) $|A_i\cap A_j| = 1$ for all $i\ne j$,
2) $A_1\cap A_2\cdots\cap A_n =\emptyset$.
What is the largest $n$ for every $k\in \mathbb{Z}^+$?
Somebody told me that the largest $n$ is $(k-1)^2+k$ when $k=1,2,3,4$. How can one prove this?
 A: I haven't come up with a general construction yet, but I believe the answer is $n=k^2-k+1$. I will prove that $n \leq k^2-k+1$. I will edit in the construction in a while when I get it.
WLOG let $A_1=\{1, 2, \ldots , k\}$, and let $x_a$ be the number of $j \not =1$ such that $a \in A_j$, where $1 \leq a \leq k$.
Observe that if $x_a \geq k$, then WLOG let $a \in A_{j}$ for $2 \leq j \leq x_a+1$.
By condition 1), each $A_j, 1 \leq j \leq x_a+1$ has only $a$ in common.
By condition 2), $x_a+1<n$. Consider any $l>x_a+1$, then $A_l$ does not contain $a$. Thus $A_l \cap (A_j \setminus a)=\{a_j\}, 1 \leq j \leq x_a+1$, where $a_j$ are distinct. 
Therefore $|A_l| \geq x_a+1 \geq k+1$, a contradiction.
Thus $x_a \leq k-1$, so $n=1+\sum\limits_{a=1}^{k}{x_a} \leq 1+k(k-1)$.
A: We can follow @Ivan's answer, to give a construction with $k(k-1)+1$ sets. It was shown that each element cannot be present in more than $k$ sets, this construction has each element occurring in exactly $k$ sets.
Let $A_1 = \{1,2,\ldots ,k\}$. Let the next $k-1$ sets $A_2, A_3, \ldots , A_k$ contain element $k$. As they all now have a common element $k$, the remaining $(k-1)^2$ elements must be distinct. Let them be $k+1, k+2, \ldots , k+(k-1)^2$, distributed among the $k-1$ sets sequentially, i.e., for $j=2,3, \ldots k$, $A_j = \{j(k-1)+2, j(k-1)+3, \ldots , j(k-1)+k\}$.
The remaining $(k-1)^2$ sets $A_{i(k-1)+j+1}$ (where $i,j=1,2, \ldots , k-1$) are described by 


*

*$i \in A_{i(k-1)+j+1}$

*$p,q \in A_{i(k-1) + j+1} \Leftrightarrow (p-q) \mod (k+j-2) \equiv 0$


i.e., $A_{i(k-1)+j+1} = \{[i+r(k+j-2)] \mod ((k-1)^2 + k): r=0,1,\ldots ,k-2\}$. It is easy to verify that these sets satisfy the required constraints.
A: 
Somebody told me that the largest $n$  is
  $(k−1)^2+k$ when $k=1,2,3,4$. How can one prove this?

That is the bound from taking the sets to be the $q^2+q+1$ lines in a projective plane with coordinates from the field with $q$ elements, with $q=k-1$.  The finite field exists when $k-1$ is a prime power, which covers the cases $k=3,4,5,6$.  Your informant was thinking of this construction for the special case where $q$ is prime so that one can use integers mod $q$ as coordinates instead of talking about finite fields.  This works for $q \leq 3$, or $k=3,4$.  There is no solution for $k=1$ and the solution for $k=2$ satisfies the same bound.  This explains why your source gave the answer up to $k=4$ only.
