Given a $(0, 1)$ matrix of order $n\times m$, we say the matrix is valid if it satisfies the following rules:
- Each column has exactly two ones.
- All columns are different.
Question: Given a fixed $n$, what is the maximum $m$ such that it's impossible to construct a valid matrix with less than $m$ columns where all $n$ rows are different? Let's call $m^*$ to such maximum $m$.
I write $(a, b)_c$ to mean that at column $c$ its two $1$s are placed on the rows $a$ and $b$, and I also say that $a$ and $b$ are connected by the column $c$. If the row $r$ has $k$ ones, I say that the degree of $r$ is $k$, and I also say that a row is empty if its degree is $0$.
The trivial facts are that for $n=1$ no valid matrix is possible and that for $n=2$ no matrix with two different rows is possible. So I'm interested on $n\geq 3$ only.
This problem have the property that two rows are equal iff they are both empty or if they have both degree $1$ and connected by the same column (that means that any row with degree $\geq 2$ is guaranteed to be unique). With these properties in mind, this problem can be translated to a graph problem in the following way (the graph doesn't need to be connected):
A valid matrix with $m$ columns and all rows different is a graph with $m$ edges, with at most one isolated vertex and without isolated edges. $m^*$ is then the size of a graph of lowest possible size that still have these properties.
Any such graph can be minimized by removing, for each connected component, any excedent edge until the component becomes a tree. Which means the optimal graph must be a forest. Since the number of edges is irrespective of the specific arrangement of each tree, let's consider that each component is a star graph.
Since any tree of order $x+1$ have $x$ edges under the above procedure, the question is if the optimal graph is one with a maximum number of components/trees (so reducing each $x$), or if there's an "optimal balance" between the number of components and the order of each component.
That's the core of the question.
We can turn this question as an optimization problem in the following way: let $e\in\{0, 1\}$ be a variable that represents the existance of an isolated vertex ($e=0$ means no isolated vertex exists in the graph; $e=1$ means one isolated vertex exists in the graph), and $h_x$ a variable whose value is the number of components with exactly $x$ edges. Since components consisting on a single edge aren't allowed, and no component can have more than $n$ vertices, then $2\leq x\leq n-1$.
So the problem is: $$ \begin{split} \min\quad& m=\sum_{i=2}^{n-1} ih_i\\ \text{s.t.}\quad& n=e+\sum_{i=2}^{n-1} (i+1)h_i \end{split} $$
which has been solved here (but I'd like to know how to shorten the proof or if any other approach is possible): Maximizing a sum of products restricted to another sum of products
The conclusion is that to minimize the number of edges you have to maximize the number of components, which requires maximizing the number of components of order 3 (e.g., claws), and using at most one isolated vertex (when $n$ doesn't divide $3$) and at most one component of order 4 (when the remainder of $n/3$ is 2).
All of this means that it's impossible to build a valid matrix with less than $m^*=\lfloor 2n/3\rfloor$ columns such that all rows are different.