Maximal number of binary strings given constraints 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.
 A: 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$.
