Let $k, N, m \in \mathbb{N}$ such that $k \leq N$.


What is the maximal number $e$ of strings $\sigma\_1, \sigma\_i, \dots, \sigma\_e$, each of length $N$ such that 
$$
\forall j < k, \left(\sum\_{i=1}^e \sigma\_i[j]\right) \leq 2^{N-k}(m-1)
$$


For example if $m=3$, $k=4$, $N=5$, we have $e = 14$. An example of such a set is
$$
\begin{array}{cc}
\sigma\_1 & \underbrace{\overbrace{0000}^{k}0}\_{N}\\\\
\sigma\_2 & 00001\\\\
\sigma\_3 & 10000\\\\
\sigma\_4 & 10001\\\\
\sigma\_5 & 01000\\\\
\sigma\_6 & 01001\\\\
\sigma\_7 & 00100\\\\
\end{array}
\hspace{20pt}
\begin{array}{cc}
\sigma\_8 & 00101\\\\
\sigma\_9 & 00010\\\\
\sigma\_{10} & 00011\\\\
\sigma\_{11} & 11000\\\\
\sigma\_{12} & 11001\\\\
\sigma\_{13} & 00110\\\\
\sigma\_{14} & 00111\\\\
\end{array}
$$


By a few trials, it seems that the following holds



> 
> * If $k \leq m$ then $e = 2^{N-k} + 2^{N-m}k$
> * If $k \geq m$ then $e = 2^{N-k} + 2^{N-m}m$
> 
> 
> 


Has this problem been already studied ? 


My intuition is that the following exchange lemma holds:



> 
> Let $S$ be a set of strings verifying previous properties. Then there exists a set $S'$ of same cardinality such that if $\sigma \in S'$ has $n$ bits at 1 at the $k$'s first positions, then all strings having strictly less than $n$ bits at 1 at the $k$'s first positions are in $S'$.
> 
> 
> 


But I don't know how to prove this.



Maximal number of binary strings given constraints
This is a counterexample to the formula $e = 2^{N-k} + 2^{N-m}m$ for the maximum number of strings satisfying the given constraints. The parameters of the example are $N = 6$, $k = 5$, and $m = 4$. The constraint is that the columns sum to no more than $6$. The conjectured formula predicts that 18 is the maximum number of strings.
$$
\begin{array}{cc}
\sigma\_1 & 000000\\\\
\sigma\_2 & 000001\\\\
\sigma\_3 & 100000\\\\
\sigma\_4 & 100001\\\\
\sigma\_5 & 010000\\\\
\sigma\_6 & 010001\\\\
\sigma\_7 & 001000\\\\
\sigma\_8 & 001001\\\\
\end{array}
\hspace{20pt}
\begin{array}{cc}
\sigma\_9 & 000100\\\\
\sigma\_{10} & 000101\\\\
\sigma\_{11} & 000010\\\\
\sigma\_{12} & 000011\\\\
\sigma\_{13} & 110000\\\\
\sigma\_{14} & 110001\\\\
\sigma\_{15} & 001100\\\\
\sigma\_{16} & 001101\\\\
\end{array}
\hspace{20pt}
\begin{array}{cc}
\sigma\_{17} & 100010\\\\
\sigma\_{18} & 100011\\\\
\sigma\_{19} & 011000\\\\
\sigma\_{20} & 011001\\\\
\sigma\_{21} & 000110\\\\
\sigma\_{22} & 000111\\\\
\end{array}
$$
If $C(k, \ell)$ denotes the number of $k$-strings with $\ell$ 1's, and all such strings are included with all possible $N-k$ suffixes, then the total contribution to the column sum from $C(k, \ell)$ (when $\ell > 0$) is $2^{N-k}\binom{k-1}{\ell - 1}$. In this example, all strings from $C(5,0)$ and $C(5,1)$ were included, but, not all strings from $C(5,2)$ could be included. If the exchange lemma is correct, this idea can be used to at least predict lower and upper bounds for $e$.


