Help on the following combinatorial problem?
I've rethought this and my initial bound was correct. In the worst case, $|S| = \Theta(m \; 2^\frac{m}{\lg m})$

Proof is in two parts. Firstly, $|S| = O(m \; 2^\frac{m}{\lg m})$. Consider the possible values of $s$ of a trajectory which ends at $v_x$. Every bit $s[j]$ for $j \ge x$ is 0, and every bit $s[j]$ for $j &lt; x - \frac{m}{\lg m}$ is 1. Therefore there are only $2^\frac{m}{\lg m}$ values which $s$ can take. Multiply up by the number of $v_x$ and we have the upper bound.

Secondly, consider


    0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
    0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
    0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1
    0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1
    0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1
    0 0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1
    ...
    0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1
    0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1



I assert that this scheme gives you $|S| = \Omega(m \; 2^\frac{m}{\lg m})$. For each column $v_x$ consider also the $(\frac{m}{\lg m}-2)$ columns to its right. Each of the $2^{\frac{m}{\lg m}-2}$ combinations of them gives a different $s$, and in each of those $s$ the top set bit is the top set bit of $v_x$, so there is no double-counting between different $v_x$.