We can prove the number of rows that begin with 1 and the number of rows that begin with 0 is less than n

Quote: show that m \leq 2n sorry .. but .. i don't know what did u mean ... By the way ... what is it ? Quote: k \geq Please explain it to me ... i am a new comer

InToTheRainBow wrote: Quote: show that m \leq 2n sorry .. but .. i don't know what did u mean ... By the way ... what is it ? Quote: k \geq Please explain it to me ... i am a new comer Read first post again (I have edited it)!

If think something like that must work, but computations have to be done : The problem is to construct a maximal number of binary $n$-sequences such that at least two differ in at least $\frac n 2$ positions. Assume $n=4a+1$ or $n=4a+2$. Then two sequences must differ in at least $2a+1$ positions. Let $V_1, \cdots, V_m$ be those sequences. For each $V_i$, let $S_i$ be the set of all possible binary $n$-sequences which differ from $V_i$ in at most $a$ positions. Then $|S_i| = C_n^0+C_n^1 + \cdots + C_n^a = t$. Moreover, the $S_i$'s are pairwise disjoints. And, in another hand, there exactly $2^n$ possible binary $n$-sequences. Thus $t \cdot m \leq 2^n$. It remains to prove that $t \geq \frac 1 n \cdot 2^{n-1}$. I don't know if it is true or not... In the case where $n = 4a+3$ or $n=4a+4$, use the same reasoning but on the last $n$-terms of the sequences. Pierre.

...sniff... Though I promised to not talk with you, but I must said that, of course, I tried such approach and it doesn't work. P.S. It is 2000th post!

So, you are really angry? Come on Myth! Pierre.

i still am not proficient at LaTeX,so this might be slightly painful. let us try to calculate the sum of the Hamming distances between all pairs of distinct rows(Hamming distance d(x,y)=# of positions where the rows x and y differ.) Now if we consider each column-suppose it has m(0) 0's and m(1) 1's,then this column contributes 2m(0)m(1)=m^2-(m(0)^2+m(1)^2) (since m(0)+m(1)=m).and since m(0)^2+m(1)^2 >=m^2/2(C-S if you like).so over all the n columns the sum is atmost nm^2/2. on the other hand if d is the minimum Hamming distance between any 2 rows,then the above sum is atleast dm(m-1).if d>n/2,then dm(m-1)<=nm^2/2 => dm-d<= nm/2 => m<= d/(d-n/2).(here we need that d>n/2). if d>n/2,then d/(d-n/2)<=2n can be easily proved. however if n=2k,d=k this won't work.what we can do there is consider all the rows with the first entry =1 and we prove that there are atmost n such rows,similarly for rows with first entry 0 and hence we are through. to see this consider all m' rows with first entry =1.deleting the 1,we get m' rows of length 2k-1 but d=k!hence by the above bound, m'<=k/(k-(2k-1)/2)=2k=n. the first part of this(the general inequality) is actually called the Plotkin bound in Coding theory and is well known.

Thank you, seshadri!

sam-n wrote: Assume $m\times n$ matrix which is filled with just 0, 1 and any two row differ in at least $n/2$ members, show that $m \leq 2n$. ( for example the diffrence of this two row is only in one index 110 100) Another solution: Replace the 0's in the matrix by -1's. Then, each of the m rows is a nonzero vector in $\mathbb{R}^{n}$. The members of the row are the n coordinates of the vector. Hence, the condition that any two rows differ in at least $\frac{n}{2}$ members is equivalent to saying that any two of these vectors have nonpositive scalar product. (In fact, if we have two row-vectors $a=\left(a_{1};\;a_{2};\;...;\;a_{n}\right)$ and $b=\left(b_{1};\;b_{2};\;...;\;b_{n}\right)$, then their scalar product is $a_{1}b_{1}+a_{2}b_{2}+...+a_{n}b_{n}$. But for any i, we have $a_{i}\in\left\{1;\;-1\right\}$ and $b_{i}\in\left\{1;\;-1\right\}$; hence, the product $a_{i}b_{i}$ can only take the values 1 and -1, and actually, we have $a_{i}b_{i}=1$ if and only if $a_{i}=b_{i}$, i. e. if the vectors a and b coincide at their i-th coordinates, and we have $a_{i}b_{i}=-1$ if and only if $a_{i}\neq b_{i}$, i. e. if the vectors a and b differ in their i-th coordinates. Hence, the scalar product of the two row-vectors, $a_{1}b_{1}+a_{2}b_{2}+...+a_{n}b_{n}$, is nonpositive if and only if the number of indices i such that $a_{i}b_{i}=-1$ is greater or equal to the number of indices i such that $a_{i}b_{i}=1$; using the above, we see that this means that the number of coordinates in which the vectors a and b differ is greater or equal to the number of coordinates at which the vectors a and b coincide; in other words, this means that the vectors a and b differ in at least $\frac{n}{2}$ coordinates, i. e. the two rows differ in at least $\frac{n}{2}$ members.) So our m row-vectors are m nonzero vectors in $\mathbb{R}^{n}$, and any two of these vectors have nonpositive scalar product. But the greatest possible number of nonzero vectors in $\mathbb{R}^{n}$ which pairwisely have nonpositive scalar product is 2n, as it was shown in http://www.mathlinks.ro/Forum/viewtopic.php?t=43211 ; hence, $m\leq 2n$, and the proof is complete. darij

For $n\equiv 1,2,3\pmod 4$, there are better bounds: If $n$ is odd, then $m\le n+1$, while if $n\equiv 2\pmod 4$, then $m\le n+2$.

Here is my solution: Lemma: Assume that an $m\times n$ matrix is filled with $0,1$ such that every 2 rows differ in at least $d$ elements and $2d>n$ then $m\leq\frac{2d}{2d-n}$ Proof: Suppose $A$ is the number of pairs $u,v$ such that $u,v$ are in the same column and their number is different. Suppose $d_{i}$ is the number of $1$'s in the $i$-th column. Then \[A=\sum_{i=1}^{n}d_{i}(m-d_{i})\leq n.\frac{m^{2}}4\] For each 2 rows due to the problem hypothesis there are at least $d$ such pairs. So \[A\geq d\binom{m}{2}\] So $d\binom m2\leq n.\frac{m^{2}}4\Rightarrow \frac{dm(m-1)}2\leq\frac{n.m^{2}}4\Rightarrow m(2d-n)\leq2d\Rightarrow m\leq\frac{2d}{2d-n}.$ Now divide all rows in 2 parts, rows that begin with $1$ (call $A_{1}$ number of such rows) and rows that begin with $0$($A_{2}$). Consider the first group omitting their first element they all differ in at least $\frac{n}{2}$ places. So $A_{1}\leq\frac{2[\frac{n+1}2]}{2[\frac{n+1}2]-(n-1)}\leq n$ . Similarly $A_{2}\leq n$ and $A=A_{1}+A_{2}\leq2n$ Also we could prove grobber's statement that $m\leq n+1$ for odd $n$. Because $A_{1},A_{2}\leq\left[\frac{n+1}2\right]$

$i)$if $n$ was odd: put $d=$the number of pairs of different numbers which are in the same column now we get that(as omid said): $\frac{n+1}{2}\binom{m}{2}\leq d\leq \frac{m^{2}}{4}n$ $\Rightarrow (m-1)(n+1)\leq mn$ $\Rightarrow m\leq n+1$ and we are done... $ii)$now if $n$ was even: assume that $m\geq 2n+1$,now we want to gain a contradiction: we know that the first column has at least $n+1$ elements of the same type...now without loosing the general we can assume that these elements are placed at the first $n+1$ rows... now take the first $n+1$ rows and columns number $2,3,...,n$,now we know that this matrix has the conditions of the problem,and also this matrix is of size $(n+1)(n-1)$ and also we assumed that $n$ is even so $n-1$ is odd,now by $i)$ we get that: $(n+1)\leq (n-1)+1$ $\Rightarrow n+1\leq n$ and this is a contradiction...

grobber wrote: For $n\equiv 1,2,3\pmod 4$, there are better bounds: If $n$ is odd, then $m\le n+1$, while if $n\equiv 2\pmod 4$, then $m\le n+2$. For the sake of completeness (and of reference), let me prove this: Claim 1: If $n$ is odd, then $m\leq n+1$. Claim 2: If $n\equiv 2\mod 4$, then $m\leq n+2$. Proof of Claim 1. Assume that $n$ is odd. Then, $\left\lceil \frac{n}{2} \right\rceil = \frac{n+1}{2} > \frac{n}{2}$, so that $2\left\lceil \frac{n}{2} \right\rceil > n$. Now, recall that any two distinct rows of the matrix differ in at least $\frac{n}{2}$ positions. Since the number of positions in which two rows differ is an integer, this yields that any two distinct rows of the matrix differ in at least $\left\lceil \frac{n}{2} \right\rceil$ positions. Thus, we can apply the Lemma from Omid Hatami's solution to $d=\left\lceil \frac{n}{2} \right\rceil$ (this is allowed since $2\left\lceil \frac{n}{2} \right\rceil > n$), and obtain that $m\leq\frac{2\left\lceil \frac{n}{2} \right\rceil}{2\left\lceil \frac{n}{2} \right\rceil-n}=\frac{2\cdot\frac{n+1}{2}}{2\cdot\frac{n+1}{2}-n}$ (since $\left\lceil \frac{n}{2} \right\rceil = \frac{n+1}{2}$) $= n+1$, and thus Claim 1 is proven. Proof of Claim 2. Assume that $n\equiv 2\mod 4$. In this case, let us denote by $A$ our $m\times n$ matrix. We consider the entries of $A$ as elements of the field $\mathbb F_2$, so $A$ becomes an $m\times n$ matrix over $\mathbb F_2$. For every $i\in\left\{1,2,...,m\right\}$, let $S_i$ denote the sum of the entries of the $i$-th row of the matrix $A$ (as elements of $\mathbb F_2$). Let us now extend the matrix $A$ to an $m\times\left(n+1\right)$-matrix $B$ by appending the column $\left(\begin{array}{c} S_1\\ S_2\\ ...\\ S_m\end{array}\right)$ as an $n+1$-th column to $A$. Then, for every $i\in\left\{1,2,...,m\right\}$, the $i$-th row of the matrix $B$ equals to the $i$-th row of the matrix $A$ with the entry $S_i$ appended at the end. Hence, for every $i\in\left\{1,2,...,m\right\}$, (1) the entries of the $i$-th row of the matrix $A$ are the first $n$ entries of the $i$-th row of the matrix $B$. Now, we are going to prove that (2) for any two distinct elements $i$ and $j$ of the set $\left\{1,2,...,m\right\}$, the $i$-th row and the $j$-th row of the matrix $B$ differ in at least $\frac{n}{2}+1$ entries. Proof of (2). Let $i$ and $j$ be two distinct elements of the set $\left\{1,2,...,m\right\}$. We are going to show that (3) the $i$-th row and the $j$-th row of the matrix $B$ differ in at least $\frac{n}{2}+1$ entries. Recall that the $i$-th row and the $j$-th row of the matrix $A$ differ in at least $\frac{n}{2}$ entries (since any two distinct rows of the matrix $A$ differ in at least $\frac{n}{2}$ entries). Since the number of entries in which two rows differ is an integer, and since $\frac{n}{2}\in\mathbb Z$ (because $n\equiv 2\mod 4$), this yields that we must be in one of the following two cases: Case 1: The $i$-th row and the $j$-th row of the matrix $A$ differ in exactly $\frac{n}{2}$ entries. Case 2: The $i$-th row and the $j$-th row of the matrix $A$ differ in at least $\frac{n}{2}+1$ entries. Let us consider Case 1 first: In this case, denote the entries of the $i$-th row of the matrix $A$ by $x_1$, $x_2$, ..., $x_n$ from left to right. Also, denote the entries of the $j$-th row of the matrix $A$ by $y_1$, $y_2$, ..., $y_n$ from left to right. Then, there are exactly $\frac{n}{2}$ values of $k\in\left\{1,2,...,n\right\}$ such that $x_k\neq y_k$ (because the $i$-th row and the $j$-th row of the matrix $A$ differ in exactly $\frac{n}{2}$ entries). Let $K$ denote the set of all $k\in\left\{1,2,...,n\right\}$ such that $x_k\neq y_k$. Then, $\left|K\right|=\frac{n}{2}$ (since there are exactly $\frac{n}{2}$ values of $k\in\left\{1,2,...,n\right\}$ such that $x_k\neq y_k$), so that $\left|K\right|$ is odd (since $n\equiv 2\mod 4$ yields that $\frac{n}{2}$ is odd). Also, for every $k\in K$, we have $x_k\neq y_k$ (by the definition of $K$). Thus, for every $k\in K$, we have $x_k=1+y_k$ (because $x_k\neq y_k$, and because any two elements $x$ and $y$ of $\mathbb F_2$ such that $x\neq y$ must satisfy $x=1+y$). Besides, $K$ was defined as $K=\left\{k\in\left\{1,2,...,n\right\}\mid x_k\neq y_k\right\}$, so that $\left\{1,2,...,n\right\}\setminus K=\left\{k\in\left\{1,2,...,n\right\}\mid x_k= y_k\right\}$. Thus, for every $k\in \left\{1,2,...,n\right\}\setminus K$, we have $x_k=y_k$. But $S_i=\sum_{k\in\left\{1,2,...,n\right\}}x_k$ (since $S_i$ is the sum of the entries of the $i$-th row of the matrix $A$, and these entries are $x_1$, $x_2$, ..., $x_n$) $= \sum_{k\in K}\underbrace{x_k}_{=1+y_k\text{ (since }k\in K\text{)}} + \sum_{k\in\left\{1,2,...,n\right\}\setminus K}\underbrace{x_k}_{=y_k\text{ (since }k\in\left\{1,2,...,n\right\}\setminus K\text{)}}$ $= \underbrace{\sum_{k\in K}\left(1+y_k\right)}_{=\sum_{k\in K}1+\sum_{k\in K}y_k} + \sum_{k\in\left\{1,2,...,n\right\}\setminus K}y_k$ $= \underbrace{\sum_{k\in K}1}_{=\left|K\right|\cdot 1} + \underbrace{\sum_{k\in K}y_k + \sum_{k\in\left\{1,2,...,n\right\}\setminus K}y_k}_{=\sum_{k\in\left\{1,2,...,n\right\}} y_k}$ $= \underbrace{\left|K\right|\cdot 1}_{=1\text{ (since }\left|K\right|\text{ is odd)}} + \sum_{k\in\left\{1,2,...,n\right\}} y_k = 1 + \sum_{k\in\left\{1,2,...,n\right\}} y_k \neq \sum_{k\in\left\{1,2,...,n\right\}} y_k$. Since $S_j = \sum_{k\in\left\{1,2,...,n\right\}} y_k$ (since $S_j$ is the sum of the entries of the $j$-th row of the matrix $A$, and these entries are $y_1$, $y_2$, ..., $y_n$), this rewrites as $S_i\neq S_j$. By the condition of Case 1, we know that the $i$-th row and the $j$-th row of the matrix $A$ differ in exactly $\frac{n}{2}$ entries. Since the entries of the $i$-th row of the matrix $A$ are the first $n$ entries of the $i$-th row of the matrix $B$ (by (1)), and since the entries of the $j$-th row of the matrix $A$ are the first $n$ entries of the $j$-th row of the matrix $B$ (for a similar reason), this fact rewrites as follows: The $i$-th row and the $j$-th row of the matrix $B$ differ in exactly $\frac{n}{2}$ of their first $n$ entries. But since these rows also differ in their $\left(n+1\right)$-th entries (since $\left(\text{the }\left(n+1\right)\text{-th entry of the }i\text{-th row of the matrix }B\right) = S_i \neq S_j$ $= \left(\text{the }\left(n+1\right)\text{-th entry of the }j\text{-th row of the matrix }B\right)$ ), this yields that these rows differ in a total of $\frac{n}{2}+1$ entries. This proves (3) in Case 1. Next let us consider Case 2: In this case, the $i$-th row and the $j$-th row of the matrix $A$ differ in at least $\frac{n}{2}+1$ entries. Since the entries of the $i$-th row of the matrix $A$ are the first $n$ entries of the $i$-th row of the matrix $B$ (by (1)), and since the entries of the $j$-th row of the matrix $A$ are the first $n$ entries of the $j$-th row of the matrix $B$ (for a similar reason), this fact rewrites as follows: The $i$-th row and the $j$-th row of the matrix $B$ differ in at least $\frac{n}{2}+1$ of their first $n$ entries. Hence, these rows differ in at least $\frac{n}{2}+1$ entries. This proves (3) in Case 2. We thus proved (3) in each of the Cases 1 and 2. This completes the proof of (3) for any two distinct elements $i$ and $j$ of the set $\left\{1,2,...,m\right\}$. In other words, (2) is proven. From (2), we know that any two distinct rows of the matrix $B$ differ in at least $\frac{n}{2}+1$ entries. Since $\frac{n}{2}+1 \geq \frac{n+1}{2}$, this yields that any two distinct rows of the matrix $B$ differ in at least $\frac{n+1}{2}$ entries. Since $n+1$ is odd (because $n\equiv 2\mod 4$), we can thus apply Claim 1 to the matrix $B$ and $n+1$ instead of the matrix $A$ and $n$, and conclude that $m\leq \left(n+1\right)+1=n+2$. This proves Claim 2.