Finding an algorithm to fill in a matrix subject to conditions I have a combinatorics problem and I am asking for a solution or a reference in order to solve it.
Since the problem is rather long, I will translate it mathematically.
Suppose I have a $n \times m$ matrix with no entries.
I want to fill the matrix with entries equal to $0$ or $1$, subject to some conditions.
We define a sum operation, which I denote by $\vee$, which is the or operation (attention: not XOR / $\oplus$ / addition modulo $2$ / exclusive-or operation):
\begin{array}{c|c|c|c|}
\vee& 0 & 1  \\ \hline
 0 & 0 & 1 \\ \hline
 1 & 1 & 1 \\ \hline
\end{array}
We will use the same symbol $\vee$ to sum rows of a matrix component by component. The result is thus a row vector.
Let $t \in \{1,\ldots,n\}$.
Condition 1: For each subset $S \subseteq \{1,\ldots,n\}$ of cardinal $t$, the sum of the $S$-rows is equal to $(1,\ldots,1)$.
Condition 2: For each subset $S \subseteq \{1,\ldots,n\}$ of cardinal $t-1$, the sum of the $S$-rows is not equal to $(1,\ldots,1)$.
Trivial consequence: Each column has to have at least $t$ ones.
And that's it! Brute-force is not an option, since in worst-case it would take $\binom{n}{t}^m$ attempts. If, for example, $t=\frac{n}{2}$, brute-force is exponential-time. I am looking for a polynomial-time algorithm. On the other hand, I could simply randomly generate a matrix with entries equal to $0$ or $1$ and check the conditions. But again, by the same reason, checking the conditions would be exponential-time.
Thanks in advance.
 A: Let $M$ be your matrix.
For each $S \subset \{1,\ldots,n\}$, let $Z(S) = \{j \in \{1,\ldots,m\}: \sum_{i \in S} M_{ij} = 0\}$.  The condition says $Z(S)$ is nonempty if $|S|=t-1$, but empty if $|S|=t$.  In particular, for any distinct $S_1, S_2$ with $|S_1| = |S_2| = t-1$, $Z(S_1)$ and $Z(S_2)$ are disjoint.  Thus we need $m \ge {n \choose t-1}$.
Conversely, if $m \ge  {n \choose t-1}$ we can construct such an $M$. For 
simplicity, suppose $m={n \choose t-1}$ (we can always add more columns of all $1$'s).  Namely, let $S_1, \ldots, S_{m}$ be an enumeration of the subsets of $\{1,\ldots,n\}$ of cardinality $t-1$, and define $M_{ij} = 0$ if $i \in S_{j}$, $1$ otherwise.
A: This is very similar to Robert Israel's answer, but reworded.
For each subset $S$ of size $t-1$, there must be at least one column, $c$, where all the entries in $c$ whose row is in $S$ are $0$. Furthermore, all the other entries in $c$ must be $1$, since for every superset $S'$ of $S$ of size $t$, there is at least one $1$ in some row in $S'$ in $c$, and it cannot occur in $S$. 
Therefore, for each of the $\binom{n}{t-1}$ possibilities for $S$, a particular column must exist; one with zeroes in $S$ and ones elsewhere. This means there must be at least $\binom{n}{t-1}$ columns. In particular, a simple algorithm to construct the matrix is this; list all of the subsets of $S$, and for each one, add a column to the matrix which is zero for the rows in $S$ and one elsewhere. Then pad the matrix to $m$ columns by adding columns of ones. 
