Skip to main content
1 of 2
Fedor Petrov
  • 108.8k
  • 9
  • 264
  • 459

The answer is $2^{q+o(q)}$ (well, there are rooms for improvement).

Example: consider all strings with $2q$ at the first place and $(q-1)/2$ pairs of one's chosen from $(1,2)$, $(2,3),\dots$, $(2q-3,2q-2)$. It is a family of cardinality $\binom{q-1}{(q-1)/2}$.

For the estimate, choose index $j$ so that at least half of your strings has 1 at position $j$. Consider only them and remove this position from them. We have $2q-1$ positions, and intersection of any two strings is even. There may be at most $2^{q-1}$ such strings, this is already well known. Indeed, consider the space generated by these strings over $\mathbb{F}_2$. This space is contained in its own orthogonal complement, hence its dimension does not exceed $q-1$.

Fedor Petrov
  • 108.8k
  • 9
  • 264
  • 459