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.