Skip to main content
added 36 characters in body
Source Link
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$$1$ at the first placelast position and $(q-1)/2$ pairs of one's chosen from possible pairs of positions $(1,2)$, $(2,3),\dots$$(3,4),\dots$, $(2q-3,2q-2)$. It is a family consisting of cardinality $\binom{q-1}{(q-1)/2}$ strings.

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$.

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$.

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

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

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$.

Source Link
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$.