There are $n$ different $3$-element subsets $A_1,A_2,...,A_n$ of the set $\{1,2,...,n\}$, with $|A_i \cap A_j| \not= 1$ for all $i \not= j$. 
Determine all possible values of positive integer $n$, such that there are $n$ different $3$-element subsets $A_1,A_2,...,A_n$ of the set $\{1,2,...,n\}$, with $|A_i \cap A_j| \not= 1$ for all $i \not= j$.

Source: China Western Olympiad 2010

Attempt:
It is quite clear that for $n=4k$ such a system exist. For $n=4$, we have $A_1 =\{1,2,3\}$, $A_2 =\{1,2,4\}$, $A_3 =\{2,3,4\}$,  $A_4 =\{1,3,4\}$. It is not hard to see that induction $n\to n+4$ works. Now I would like to prove that there is no such system if $4\nmid n$. 
I thought about linear algebra approach. Observe the given sets as vectors in $\mathbb{F}_2^n$. Then since $A_i\cdot A_i =1$ and $A_i\cdot A_j = 0$ for each $i\ne j$ these vectors are linear independent:
$$ b_1A_1+b_2A_2+...+b_nA_n = 0\;\;\;\; /\cdot A_i$$
$$ b_1\cdot 0+b_2\cdot 0+...+b_i\cdot 1+...b_n\cdot 0 =0\implies b_i=0$$ 
But now, I'm not sure what to do...
 A: Suppose that there are $n$ such sets $A_1,A_2,\ldots,A_n$, represented by indicator vectors $\mathbf{a}_1,\mathbf{a}_2,\ldots,\mathbf{a}_n\in\mathbb{F}_2^n$.  Equip $\mathbb{F}_2^n$ with the usual inner product $\langle\_,\_\rangle$.  
We already know that the vectors $\mathbf{a}_1,\mathbf{a}_2,\ldots,\mathbf{a}_n$ are linearly independent.  Therefore, they span $\mathbb{F}_2^n$.  Thus, the vector $\boldsymbol{1}:=(1,1,\ldots,1)$ can be written as
$$\mathbf{a}_{j_1}+\mathbf{a}_{j_2}+\ldots+\mathbf{a}_{j_k}$$
for some $j_1,j_2,\ldots,j_k\in\{1,2,\ldots,n\}=:[n]$ with $j_1<j_2<\ldots<j_k$.  If $k<n$, then there exists $r\in[n]$ such that $r\neq j_\mu$ for all $\mu=1,2,\ldots,k$.  That is,
$$1=\langle \mathbf{a}_r,\boldsymbol{1}\rangle =\sum_{\mu=1}^k\,\langle \mathbf{a}_{j_\mu},\mathbf{a}_r\rangle=0\,,$$
which is a contradiction.  Therefore, $k=n$, whence
$$\boldsymbol{1}=\sum_{j=1}^n\,\mathbf{a}_j\,.\tag{*}$$
Consequently, each element of $[n]$ belongs in an odd number of $A_1,A_2,\ldots,A_n$, whence at least one of the sets $A_1,A_2,\ldots,A_n$.  
Furthermore, it is not difficult to show that every element of $[n]$ must belong in at least two of the $A_i$'s.  (If there exists an element of $[n]$ belonging in exactly one $A_j$, then you can show that there are at most $n-2$ possible $A_i$'s.)  Let $d_j$ be the number of sets $A_i$ such that $j\in A_i$.  Then
$$\sum_{j=1}^n\,d_j=3n\,.\tag{#}$$
Note that $d_j\geq 2$ for all $j\in[n]$.
From (*), we conclude that $d_j\geq 3$ for every $j\in[n]$.  However, (#) implies that $d_j=3$ for all $j\in[n]$; i.e., every element of $[n]$ must be in exactly three of the $A_i$'s.  Write $\mathbf{e}_1,\mathbf{e}_2,\ldots,\mathbf{e}_n$ for the standard basis vectors of $\mathbb{F}^n_2$.  We see that
$$\mathbf{e}_j=\mathbf{a}_p+\mathbf{a}_q+\mathbf{a}_r$$
where $j$ is in $A_p$, $A_q$, and $A_r$.  This shows that
$$A_p=\{j,x,y\}\,,\,\,A_q=\{j,y,z\}\,,\text{ and }A_r=\{j,z,x\}$$
for some $x,y,z\in[n]$.  Since $x$ already belongs in $A_p$ and $A_r$, it must be belong in another $A_s$.  Clearly, $A_s$ must be equal to $\{x,y,z\}$.  From here, we conclude that the four elements $j,x,y,z$ belong in exactly four of the $A_i$'s, which are $\{j,x,y\},\{j,y,z\},\{j,z,x\},\{x,y,z\}$.  The rest is easy.
A: 
Let $n$ be a positive integer.  If $A_1,A_2,\ldots,A_m$ are $3$-subsets of $[n]$ such that $\left|A_i\cap A_j\right|\neq 1$ for $i\neq j$, then the largest possible value of $m$ is
  $$m_\max=\left\{
\begin{array}{ll}
n&\text{if }n\equiv0\pmod{4}\,,\\
n-1&\text{if }n\equiv1\pmod{4}\,,\\
n-2&\text{else}\,.
\end{array}
\right.$$  

Remark:  Below is a sketch of my proof of the claim above.  Be warned that a complete proof is quite long, whence I am providing a sketch with various gaps to be filled in.  I hope that somebody will come up with a nicer proof.  
Proof.  The first two cases follow from my first answer.  I shall now deal with the last case, where $m_\max=n-2$.
Suppose contrary that there are $A_1,A_2,\ldots,A_{n-1}$ satisfying the intersection condition.  Then, proceed as before.  The indicator vectors $\mathbf{a}_1,\mathbf{a}_2,\ldots,\mathbf{a}_{n-1}\in\mathbb{F}_2^n$ are linearly independent.  Thus, there exists $\mathbf{v}\in\mathbb{F}_2^n$ such that $\mathbf{a}_1,\mathbf{a}_2,\ldots,\mathbf{a}_{n-1},\mathbf{b}$ form a basis of $\mathbb{F}_2^n$.  We can assume that $\langle \mathbf{a}_i,\mathbf{b}\rangle=0$ for all $i=1,2,\ldots,n-1$ (otherwise, replace $\mathbf{b}$ by $\mathbf{b}-\sum_{i=1}^{n-1}\,\langle \mathbf{a}_i,\mathbf{b}\rangle \,\mathbf{a}_i$). Observe that $\langle \mathbf{b},\mathbf{b}\rangle=1$.
Note that $$\boldsymbol{1}=\sum_{i=1}^{n-1}\,\mathbf{a}_i+\mathbf{b}\,.$$
Let $B$ be the subset of $[n]$ with the indicator vector $\mathbf{b}$.  Let $X$ denote the set of $i$ such that $A_i$ is disjoint from $B$, and $Y$ the set of $i$ such that $A_i\cap B$ has two elements.  Observe that $X$ and $Y$ form a partition of $\{1,2,\ldots,n-1\}$; moreover,
$$\mathcal{X}:=\bigcup_{i\in X}\,A_i\text{ and }\mathcal{Y}:=\bigcup_{i\in Y}\,A_i$$
are disjoint subsets of $[n]$.
If $X\neq \emptyset$, then we can use induction to finish the proof, noting that $A_i\subseteq [n]\setminus (B\cup\mathcal{Y})$ for all $i\in X$.  From now on, assume that $X=\emptyset$.
Consider a simple graph $G$ on the vertex set $B$ where two vertices $i,j\in B$ ($i\neq j$) are connected by an edge iff $i$ and $j$ belongs in some $A_p$ simultaneously.  If $C$ is a connected component of $G$ and $k\in [n]\setminus B$, then we say that $k$ is adjacent to $C$ if there exists $A_p$ such that $A_p\cap B$ is an edge of $C$ and $k\in A_p$, in which case, we also say that $A_p$ is incident to $C$.  It is important to note that, if $C_1$ and $C_2$ are two distinct connected components of $G$, and $k_1,k_2\in [n]\setminus B$ are adjacent to $C_1$ and $C_2$, respectively, then $k_1\neq k_2$.
Let $C$ be a connected component of $G$ with at least two vertices.  We have three probable scenarios:


*

*$C$ is a type-1 connected component, namely, $C$ is an isolated edge (i.e., it has only two vertices and one edge);

*$C$ is a type-2 connected component, namely, $C$ is a triangle (i.e., $C$ consists of $3$ vertices and $3$ edges);

*$C$ is a type-3 connected component, namely, $C$ is a star graph (i.e., there exists a vertex $v$ of $C$ such that every edge of $C$ takes the form $\{v,w\}$, where $w$ is any vertex of $C$ distinct from $v$).


It can be readily seen that, if $C$ is a connected component of type 2 or type 3 of $G$, then $C$ is adjacent to exactly one element of $[n]\setminus B$.  If $G$ has a connected component $C$ of type 2, then the removal of vertices in $C$ along with the element $j\in[n]\setminus B$ which is adjacent to $C$ reduces the elements of $[n]$ by $4$, whilst ridding of only three sets $A_i$.  Then, we finish the proof for this case by induction.  Suppose from now on that $G$ has no connected components of type 2.
Now, assume that $G$ has a connected component $C$ of type 3, which has $s$ vertices.  Let $j\in[n]\setminus B$ be adjacent to $C$.  Then, the removal of vertices of $C$ along with $j$ from $[n]$ reduces the elements of $[n]$ by $s+1$, whilst ridding of only $s-1$ sets $A_i$.  Therefore, the claim hold trivially.
Finally, assume that $G$ has only connected components of type 1 and possibly some isolated vertices.  Then, it follows immediately that there are at most $n-2t$ sets $A_i$, where $t$ is the number of connected components of type 1.   This shows that $t=0$.  Thus, $G$ has only isolated vertices, but this is a contradiction as well (as $X=\emptyset$ is assumed). 
