Combinatorics problem - Counting Colors and Objects There are $2n$ colors and $2n$ objects. If we take any two objects, there are exactly $n$ colors that are on one and not on the other. Prove that if we take any two colors, there are exactly $n$ objects that have one, but not the other one.
Be $O_m$ the set describing the colors of the object $o_m$, and $C_m$ the set describing the objects that have the color $c_m$.
So for any i,j, $|(O_i\cup O_j)\setminus(O_i\cap O_j)|=n$, prove that $|(C_i\cup C_j)\setminus(C_i\cap C_j)|=n$.
I tried Double Counting, but I wasn't able to solve it. I also tried solving it using the Extremal Principle.
I'm pretty sure it has to do with counting the colors from the perspecive of themselves, and from the perspective of the objects, but I've not been able to do it.
 A: This is a really classical example of linear algebraic method in combinatorics.
I have forgotten the origin of the problem(I read the problem on the math competition magazine "中等数学" published in Chinese about $10$ years ago), but the proof(from the official solution) goes like this: if $A$ is the $2n \times 2n$ matrix such that $A_{ij}$ is $1$ if $o_i$ is colored with $c_j$ and $-1$ otherwise, then the condition $\lvert (O_i \cup O_j) \backslash (O_i \cap O_j)\rvert = n, \forall i \neq j$ is equivalent to the fact that $AA^T = 2n I$. So we must have $A^T A = 2nI$ because $A^T = 2n \cdot A^{-1}$, which is equivalent to the fact that $\lvert (C_i \cup C_j) \backslash (C_i \cap C_j)\rvert = n, \forall i \neq j$.
By the way, this implies that the matrix $A$ must be a Hadamard Matrix, which explains why there is no construction with odd $n > 1$, since Hadamard matrices are known to exist only in dimensions $1,2,4m(m \in \mathbb{N})$ (whether they actually exists in these dimensions is a huge open problem. )
I heard from a friend that there is another proof using induction, but it sure isn't as elegant as this.
