Skip to main content
1 of 2
Antoine Labelle
  • 3.4k
  • 1
  • 8
  • 24

The answer is indeed ${n \choose \lfloor n/2 \rfloor}$, here is a proof. It's equivalent to finding the maximal number of vectors $v$ in the hypercube $H=\{-1,1\}^n$ with all the same dot product with a fixed vector $a$ that has no coordinate zero.

By symmetry, we can assume that $a\in \mathbb{R}_{> 0}^n$. If we associate $v\in H$ to $S_v=\{i:v_i=1\} \subseteq [n]$, note that the $S_v$ form an antichain: indeed, if $(v+d)\cdot a = v\cdot a$ for $d\in \{0,2\}^n$, then $d\cdot a=0$ which is impossible unless $d=0$ (because $a\in \mathbb{R}_{> 0}^n$ and $d\in \mathbb{R}_{\ge 0}^n$). Hence the result follows from Sperner's theorem

Antoine Labelle
  • 3.4k
  • 1
  • 8
  • 24