The input of my problem is an integer $n\geq 3$.


The output is an integer $r\geq 1$ which must be **as small as possible** such that there is a $(n\times r)$ matrix verifying the following constraints:


* the entries of the matrix are $0$ or $1$.
* all the rows are differerent.
* in each row, there are exactly $\lfloor r/2 \rfloor$ entries equal to $1$.
* for every pair of adjacent rows (and the pair composed of the first and the last rows), there are exactly $\lfloor r/2 \rfloor-1$ common positions where the entries are equal to $1$.
* if we take two pairs of adjacent rows, the pattern must also be distinct between these two pairs (see the example with $r=5$ for $n=7$).


For example, with $n=6$, I have the following matrix with $r=5$:


$M\_{6,5}=\begin{pmatrix}1 & 1 & 0 & 0 & 0\\
 1 & 0 & 0 & 0 & 1\\
 0 & 0 & 0 & 1 & 1\\
 0 & 0 & 1 & 0 & 1\\
 0 & 1 & 1 & 0 & 0\\
 0 & 1 & 0 & 1 & 0\end{pmatrix}$


There are $\lfloor 5/2 \rfloor=2$ entries which are equal to $1$ in every row. And for each pair of adjacent rows, there is $\lfloor 5/2 \rfloor-1=1$ common position where an entry is equal to $1$.
For example, if we take the $5$th and the $6$th rows
$\begin{pmatrix}0 & \color{red}{1} & 1 & 0 & 0\\
 0 & \color{red}{1} & 0 & 1 & 0\end{pmatrix}$, there is an entry where both rows are equal to $1$.


The following matrix respects the first four constraints but not the last one:
$M\_{7,5}=\begin{pmatrix}0 & 0 & 1 & 0 & 1\\
 0 & 0 & 0 & 1 & 1\\
 1 & 0 & 0 & 1 & 0\\
 1 & 0 & 0 & 0 & 1\\
 0 & 1 & 0 & 0 & 1\\
 1 & 1 & 0 & 0 & 0\\
 1 & 0 & 1 & 0 & 0\end{pmatrix}$


Indeed, the pair formed by the rows 2 and 3 has the pattern $\begin{pmatrix}1 & 0 & 0 & 1 & 1\end{pmatrix}$ which is also equivalent to the pattern of the pair composed of the rows 3 and 4. So this matrix $M\_{7,5}$ is not valid.



> 
> For a given $n$, how could I find the smallest possible value $r$ such that a $(n\times r)$ matrix as described exists?
> 
> 
> 



FInd smallest value $r$ such that a $n\times r$ matrix exists
There are plenty of ways to list all the $\lfloor r/2\rfloor$-subsets of $\lbrace 1,2,\ldots,r\rbrace$ such that adjacent members of the list have intersection $\lfloor r/2\rfloor-1$ (see "gray codes for subsets"). Use these as the rows of the matrix and just chop off the rows past the $n$-th.


So the answer is the minimum value of $r$ such that $\binom{r}{\lfloor r/2\rfloor}\ge n$.


ADDED: Gerhard correctly points out that I didn't notice the requirement that the first and last rows need to be minimally different. This means we are looking at whether the [Johnson graph](https://en.wikipedia.org/wiki/Johnson_graph) $J(r,\lfloor r/2\rfloor)$ has a cycle of length $n$. I see a claim [here](http://www.b-paper.com/hamiltonian-connectivity-pancyclicity-and-edge-deletion-preserving-the-diameter-of-johnson-graphs-2.html) that this graph is pancyclic, meaning it has a cycle of every length greater than 2. If true, the answer remains that same. But I don't see an author or citation there; what sort of paper is it?


