mathmanman wrote: Zeroes and ones are arranged in all the squares of $n\times n$ table. All the squares of the left column are filled by ones, and the sum of numbers in every figure of the form [asy][asy]size(50); draw((2,1)--(0,1)--(0,2)--(2,2)--(2,0)--(1,0)--(1,2));[/asy][/asy] (consisting of a square and its neighbours from left and from below) is even. Prove that no two rows of the table are identical. Nice problem. Let $v=\{v_{1},v_{2},\cdots,v_{n}\}$ a vector of $n$ $0$ or $1$ and $f_{v}(i,j)$, with $i,j$ integers $\in[1,n]$ the function defined by $f(1,j)=v_{j}$, $f(i,1)=f(i-1,1)$ for $i>1$ and $f(i,j)=f(i-1,j-1)\oplus f(i-1,j)$ $\forall$ integers $i,j\in[2,n]$ ($\oplus$ is XOR). The table of the problem is such a function $f()$ with $a_{1}=1$. Let $u_{k}=\{0,0,\cdots,1,\cdots,0\}$, $k$ integer $\in[1,n]$ the vector with $1$ in $k^{th}$ position and zeroes elsewhere. $\oplus$ is associative and so $f_{v}(i,j)=\bigoplus_{k=1}^{n}f(1,k)f_{u_{k}}(i,j)$ But $f_{u_{1}}(i,j)=p(\left(\begin{array}{c}i-1\\j-1\end{array}\right))$ where $p(n)$ is the "parity" function : $p(n)=0$ if $n$ is even and $p(n)=1$ if $n$ is odd. and the convention that $\left(\begin{array}{c}n\\p\end{array}\right)=0$ if $n<p$ And $f_{u_{k}}(i,j)=f_{u_{1}}(i,j-k+1)$ if $j\geq k$ and $0$ if $j<k$ So $f_{v}(i,j)=\bigoplus_{k=1}^{j}f(1,k)f_{u_{1}}(i,j-k+1)$ And $f_{v}(i,j)=\bigoplus_{k=1}^{j}f(1,k)p(\left(\begin{array}{c}i-1\\j-k\end{array}\right))$ So $f_{v}(i,j)=p(\sum_{k=1}^{j}f(1,k)\left(\begin{array}{c}i-1\\j-k\end{array}\right))$ Now, assume lines $q$ and $r>q$ are equal. Then lines $p-1$ and $q-1$ are equal, ... and lines $1$ and $p=r-q+1$ are equal. So $p(\sum_{k=1}^{j}f(1,k)\left(\begin{array}{c}p-1\\j-k\end{array}\right))=f(1,j)$ $\forall$ integer $j\in[1,n]$ So $p(\sum_{k=1}^{j-1}f(1,k)\left(\begin{array}{c}p-1\\j-k\end{array}\right))=0$ $\forall$ integer $j\in[2,n]$ So $\sum_{k=1}^{j-1}f(1,k)\left(\begin{array}{c}p-1\\j-k\end{array}\right)$ is even $\forall$ integer $j\in[2,n]$ For $j=2$, this means $f(1,1)\left(\begin{array}{c}p-1\\1\end{array}\right)$ is even, so $\left(\begin{array}{c}p-1\\1\end{array}\right)$ is even For $j=3$, this means $f(1,1)\left(\begin{array}{c}p-1\\2\end{array}\right)+f(1,2)\left(\begin{array}{c}p-1\\1\end{array}\right)$ is even and, since $\left(\begin{array}{c}p-1\\1\end{array}\right)$ is even, $\left(\begin{array}{c}p-1\\2\end{array}\right)$ is even And, by induction, it is easy to show that $\left(\begin{array}{c}p-1\\m\end{array}\right)$ is even $\forall$ integer $m\in[1,n-1]$ And this is impossible since $p-1\leq n-1$ and $\left(\begin{array}{c}p-1\\p-1\end{array}\right)$ is odd. Remark : it is possible to show that, for $n=2^{a}$, the $n+1^{th}$ line would be equal to the first one. -- Patrick

Something simpler?

VicKmath7 wrote: Something simpler? Solution by Amirhossein Bagheri Jebeli: First define $L(n)$ be the three squares as below: [asy][asy]size(150); draw((12,12)--(13,12)--(13,13)--(12,13)--(12,12)); draw((6,12)--(7,12)--(7,13)--(6,13)--(6,12)); draw((6,12)--(7,12)--(7,13)--(6,13)--(6,12)); draw((12,6)--(12,7)--(13,7)--(13,6)--(12,6));[/asy][/asy] Where the distance between the centre of squares in the same row or column is $2^n$ for example the following is $L(0)$: [asy][asy]size(50); draw((2,1)--(0,1)--(0,2)--(2,2)--(2,0)--(1,0)--(1,2));[/asy][/asy] By putting $3$ of $L(n)$ from its central square in squares of $L(n)$ we can figure out inductively that sum of numbers in $L(n+1)$ is even. imagine that two rows $e,d$ are identical, $e>d$ and $e-d=2^k.l$ where $l$ is odd, now put the left-most square of $L(k)$ on the left-most square of $e$ to conclude that the remaining two squares of this $L(k)$ are of different parity, now put the left-most square of $L(k)$ on the left-most square of $e-2^k$ to conclude that the remaining two squares of this $L(k)$ are of different parity, repeating this process easily implies that the parity of the $2^k$-th squares of $e,d$ are of different parity.