An $n×n$ chart, where n≥4 with "+","−" signs On an $n\times n$ chart, where $n \geq 4$, stand "$+$" signs in the cells of the main diagonal and "$-$" signs in all the other cells. You can change all the signs in one row or in one column, from $-$ to $+$ or from $+$ to $-$. Prove that you will always have $n$ or more $+$ signs after finitely many operations.
I am looking for a solution by induction.
I tried to solve it but I wasn't able to continue to a solution.you can also get help from:
https://artofproblemsolving.com/community/c6h609872
as it's available in links this question is from Russian Olympiad 2010.
I tried to answer it by induction but the base case isn't trivial but I suppose it's true and I continued my solution:
Suppose we have done a number of operations on the board. Clearly, we can assume that we did at most one operation on each row or column. By the hypothesis, the lower right $(n-1)\times(n-1)$ sub board contains at least $n-1$ pluses. If the union of the first row and the first column contains a plus, then we're done. Suppose otherwise. Assume WLOG that we did the operation on the first row, but not on the first column. Therefore we did the operation on all columns except the first, and we did not do the operation on any rows except the first. Now it is easy to check that the lower right $(n-1)\times(n-1)$ sub board contains at least $n$ pluses, and we're done.
please help me to prove the base case.
 A: The proof for the base case suggests a proof in general - however I'll stick to just $n=4$ for this answer.
First, we need an observation you hint at in the inductive step. I'll use matrix notation for indexing into the board, which I'll denote $B$. Think of the elements of the board as integers modulo $2$, with $1$s representing $+$ and $0$ representing $-$. Then each of our moves is equivalent to adding a matrix like: $$\begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix}$$ to $B$. A matrix with all $1$'s along some row or column. Since this is addition modulo $2$ in each entry, these operations are commutative and associative, so all that matters is which rows/columns have been modified an odd number of times. 
Let $r_i$ be $1$ if the ith row has been added to $B$, and likewise $c_i$ for columns. Then the i,jth entry of $B$ is equal to $$r_i + c_j + 1_{i=?j}$$ modulo $2$, where $1_{i=?j} = \begin{cases} 1 &\text{ if } i = j \\ 0 &\text{ else}\end{cases}$. Thus the total number of $1$s (or equivalently, pluses) is $$\sum_{i \neq j} (r_i + c_j)\%2 + \sum_k (r_k + c_k + 1)\%2$$
(I'm using %2 to indicate the additions in the parens are modulo 2, while the greater additions are in $\mathbb{Z}$). 
And now we can consider the sum in parts. The second term is just the number of $+$ symbols along the diagonal of $B$. There are $3$ cases:
If there are zero $+$ signs along the diagonal then we have $r_i \neq c_i$ for every $i$. Consider any $3$ rows, it must be that $2$ of them have $r_i = r_j$, which implies that $r_i \neq c_j$ and $r_j \neq c_i$, giving us $2$ plus signs in the first term. Further, this is true for any triple. In particular the triple $[1,2,3,4] - [i]$, which will give a different pair of $+$ signs than the above. This gives us at least $4$ total plus signs, as desired.
Suppose there is some number of $+$ signs between $0$ and $4$. Let $i$ be such that $r_i = c_i$ and $j$ be such that $r_j \neq c_j$. Then we have either $r_j \neq c_i = r_i$ or $c_j \neq c_i = r_i$, because their different, and there are only $2$ possible values. And so $B_{i,j}$ or $B_{j,i}$ is a plus sign. Note this is true for every pair $i,j$ satisfying the above, and in any of these cases there will be at least $3$ such pairs. Additionally all such pairs give distinct $B_{i,j}$. Hence we have at least $4$ plus signs.
Suppose there are four $+$ signs along the diagonal. Then we're done, we've found our $4$ plus signs.
A: Let's consider the problem in the following way.By this, the number of $+$ and $-$ can be determined in any step.Consider, the matrices of binary numbers.
$A=(a_{ij})_{n\times n}$ where $a_{ij}= \left\{ \begin{array}{ll} 1 & \mbox{if $i=j$};\\ 0& \mbox{if $i\ne j$}.\end{array} \right. $ 
$R_{\alpha }=(e_{ij})_{n\times n}$ where $e_{ij}= \left\{ \begin{array}{ll} 1 & \mbox{if $i=\alpha $};\\ 0& \mbox{if $i\ne \alpha $}.\end{array} \right.$ 
$C_{\beta }=(d_{ij})_{n\times n}$ where $d_{ij}= \left\{ \begin{array}{ll} 1 & \mbox{if $j=\beta $};\\ 0& \mbox{if $j\ne \beta $}.\end{array} \right.$
Now consider the functions $r_\alpha ,c_\beta $ on matrices defined by, $r_\alpha A=A+R_\alpha$, $c_\beta A=A+C_\beta$
Now, $r_\alpha c_\beta A=r_\alpha c_\beta (a_{ij})_{n\times n}$
$=r_\alpha (a_{ij}^\prime )_{n\times n}$ where $a_{ij}^\prime  = \left\{ \begin{array}{ll} a_{ij}+1 & \mbox{if $j=\beta $};\\ a_{ij} & \mbox{if $j\ne \beta$}.\end{array} \right.$
$=(a
_{ij}^{\prime \prime })_{n\times n}$ where, $ a_{ij}^{\prime \prime}= \left\{ \begin{array}{ll} a_{ij}^\prime +1 & \mbox{if $i=\alpha $};\\ a_{ij}^\prime  & \mbox{if $i\ne \alpha $}.\end{array} \right.$
Hence, $ a_{ij}^{\prime \prime } = \left\{ \begin{array}{ll} a_{ij} & \mbox{if $(i,j)=(\alpha ,\beta )$ or  ($i\ne \alpha $ and $j\ne \beta )$};\\ a_{ij}+1 & \mbox{if $(i=\alpha $ and $j\ne \beta )$ or $(i\ne \alpha $ and $j=\beta )$}.\end{array} \right. $
Also, $c_\beta r_\alpha A=c_\beta r_\alpha (a_{ij})_{n\times n}$
$=c_\beta (a_{ij}^{\prime \prime \prime })_{n\times n}$ where $a_{ij}^{\prime  \prime \prime }= \left\{ \begin{array}{ll} a_{ij}+1 & \mbox{if $i=\alpha $};\\ a_{ij} & \mbox{if $i\ne \alpha $}.\end{array} \right. $
$=(a_{ij}^{\prime \prime \prime \prime })_{n\times n}$ where, $ a_{ij}^{\prime \prime \prime \prime }= \left\{ \begin{array}{ll} a_{ij}^{\prime \prime \prime } +1 & \mbox{if $j=\beta $};\\ a_{ij}^{\prime \prime \prime }& \mbox{if $j\ne \beta $}.\end{array} \right.$
Hence, $a_{ij}^{\prime \prime \prime \prime } = \left\{ \begin{array}{ll} a_{ij} & \mbox{if $(i,j)=(\alpha ,\beta )$ or  ($i\ne \alpha $ and $j\ne \beta )$};\\ a_{ij}+1 & \mbox{if $(i=\alpha $ and $j\ne \beta )$ or $(i\ne \alpha $ and $j=\beta )$}.\end{array} \right. $
So, $r_\alpha c_\beta =c_\beta r_\alpha $. Also, $r_\alpha r_\beta =r_\beta r_\alpha $ and $c_\alpha c_\beta =c_\beta c_\alpha $.
Now consider any finite number of $r_{\alpha }^{'s}$ and $c_{\beta }^{'s}$ are applied on $A$.Then the resulting matrix can be written as $r_{\alpha _1}r_{\alpha _2}...r_{\alpha _k}c_{\beta _1}c_{\beta _2}...c_{\beta _t}A$ where $\alpha_i\ne \alpha_j$ and $\beta_i\ne \beta_j$ for $i\ne j$(the distinct $r_{\alpha _i}^{'s}$  are taken as if $r_{\alpha _i}=r_{\alpha _j}$ then $r_{\alpha _i}r_{\alpha_j}$ does not effect the elements of $A$, similar reson is for $\beta_i^{'s}$)
Now, $r_{\alpha _1}r_{\alpha _2}...r_{\alpha _k}c_{\beta _1}c_{\beta _2}...c_{\beta _t}=(b_{ij})_{n\times n}$ where 
$b_{ij}=\left\{ \begin{array}{ll} a_{ij} +1& \mbox{when $\mathbf {either}$ $ i\in \{\alpha _1,\alpha _2,...,\alpha _k\}$ $\mathbf {or}$ $j\in  \{\beta _1,\beta _2,...,\beta _t\}$ };\\ a_{ij} & \mbox{otherwise}.\end{array} \right. $
Let $R=\{\alpha _1,\alpha _2,...,\alpha _k\}$;$T=\{\beta  _1,\beta _2,...,\beta _t\}$. So, $\mid R\mid=k,\mid T\mid=t$ and $\mid R\cap T\mid=q$ ,say.
So, $b_{ij}=0$ if $\mathbf {either}$, 
$i=j$ and $(i,j)\in (R\times T^c)\cup (R^c\times T)$ $\mathbf {or}$ $i\ne j$ and $(i,j)\in (R\times T)\cup(R^c\times T^c)$ 
$b_{ij}=1$ if $\mathbf {either}$, $i=j$ and $(i,j)\in (R\times T)\cup (R^c\times T^c)$ $\mathbf {or}$  $i\ne j$ and $(i,j)\in (R\times T^c)\cup(R^c\times T)$
So, $b_{ij}=0$ for $\mid R\cap T^c\mid +\mid R^c\cap T\mid +\mid R\mid \mid T\mid -\mid R\cap T\mid +\mid R^c\mid \mid T^c\mid -\mid R^c\cap T^c\mid=n^2-n(k+t+1)+2(k+t)+2kt-4q$ values of $(i,j)$ and 
$b_{ij}=1$ for $\mid R\cap T\mid +\mid R^c\cap T^c\mid +\mid R\mid \mid T^c\mid -\mid R\cap T^c\mid +\mid R^c\mid \mid T\mid -\mid R^c\cap T\mid =n(k+t+1)-2(k+t)-2kt+4q$ values of $(i,j)$
Now, using the facts the that $0\le k,t\le n$ and $k+t-n\le q\le min(k,t)$ the desired result follows.
