Find the sharpest lower bound $c$ 
Fix an even number $n$. The random variables $X_1 , X_2 ,...,X_n$ take values in the set {−1, 1}. There is a constant $c$ so that, for $i \neq j$, $E[X_i X_j ] = c$. Find the sharpest
  lower bound you can for $c$. 

I think $c$ should be greater than or equal to zero, but cannot prove it. Can you give me some ideas?
PS: Please don't downvote my problem if you don't have any ideas. This problem does make sense, since it's a problem in an ivy school's prelim exam. Thank you!
 A: The random variable $(X_1+\dots+X_n)^2$ is non-negative, hence
$$ 0\leq \mathbb{E}[(X_1+\dots+X_n)^2]=\sum_{i=1}^n\mathbb{E}[X_i^2]+\sum_{i\neq j}\mathbb{E}[X_iX_j]=n+n(n-1)c$$
This implies that $c\geq -\frac{1}{n-1}$.
Thus it is enough to show that this bound is optimal. To do so, let $\Omega$ be the subset of $\{-1,1\}^n$ consisting of those sequences with an equal number of $1$s and $-1$s. Note that if $n=2k$ then $|\Omega|={n\choose k}$ since an element of $\Omega$ is determined by the positions of the $1$s.
Give $\Omega$ the uniform probability law, and let $X_i(\omega)$ be the $i$th entry of $\omega$. To compute $\mathbb{E}[X_iX_j]$, observe that there are ${n-2\choose k-2}$ elements of $\Omega$ such that $X_i(\omega)=1=X_j(\omega)$, ${n-2\choose k}$ elements of $\Omega$ such that $X_i(\omega)=-1=X_j(\omega)$, and $2{n-2\choose k-1}$ elements of $\Omega$ such that $X_i(\omega)$ and $X_j(\omega)$ have opposite signs. Therefore
$$ \mathbb{E}[X_iX_j]=\frac{{n-2\choose k}+{n-2\choose k-2}-2{n-2\choose k-1}}{{n\choose k}}$$
and this simplifies to $\frac{-1}{n-1}$ after some algebra if we recall that $n=2k$.
A: Say you have $a$ of the variables being $1$ and $n-a$ being $-1$.  Then for $i \neq j$, $E[X_iX_j]=\frac {a(a-1)+(n-a)(n-a-1)-a(n-a)}{n(n-1)}$  This will be minimized (you need to justify this) when $a=\frac n2$ which will give you your bound.
