Suppose you are given an ordered sequence consisting of $n$ pairs of length-$N$ bit vectors (i.e., each entry in each vector is $0$ or $1$), say
$$(b_{0,0},b_{0,1}),(b_{1,0},b_{1,1}),\ldots,(b_{n-1,0},b_{n-1,1}).$$
Each pair $(b_{i,0},b_{i,1})$ satisfies the invariant that the parity/Hamming weight of $b_{i,0}$ is even and of $b_{i,1}$ is odd. Moreover, all $2n$ vectors are pairwise distinct. But we cannot say anything more about how the vectors might be related. Also assume that $n>1$ (think $n=80$ or so) and $2^n\gg N$.
Apart from what is given above, assume nothing about these vectors.
Now, for each $n$-bit number $i=i_{n-1}i_{n-2}\cdots i_0$, define the length-$N$ vector of $n$-bit numbers obtained by forming the $n$-by-$N$ bit matrix
$$\left[\begin{array}{c}b_{0,i_{n-1}}\\b_{1,i_{n-2}}\\\vdots\\b_{n-1,i_0}\end{array}\right],$$
and then reading off its columns. That is, each column of the matrix is interpreted as an $n$-bit integer.
I am hoping to show that it is always possible to select a set of at most $N$ numbers $i$ such that the matrix formed by stacking these vectors on top of each other has an invertible submatrix (of rank $> 1$).
Actually, what I ultimately hope to show is that one can select a sufficiently large (albeit polynomial in $n$) set of $i$ that suffice to find such an invertible submatrix with very high probability.
(The setting is a cryptographic protocol. If everybody is following the protocol, then the $b_{i,j}$ vectors have a very special form that makes it trivial to find invertible submatrices. If one party is cheating, they can strategically choose the $b_{i,j}$ in an attempt to thwart that. The step that exists to prevent such cheating is annoyingly costly, so we're trying to see if it is actually necessary.)