I think it should be largest N(n)

kwanglee123456 wrote: I think it should be largest N(n) Oh yes thanks.

The answer is \[N = \begin{cases*} n^2 & $n$ even\\ n^2 - n + 1 & $n$ odd. \end{cases*}\]We interpret the board state as an element of $\mathbb{F}_2^{n \times n}$. First of all if $n$ is even then it is easy to see that every state is possible, so the answer is $n^2$. Indeed, toggling all of the colored cells only flips the red cell. [asy][asy] int n = 6; int a = 0, b = 0; for (int i = 0; i < n; i += 1) if (i != a) fill(shift(i, b) * unitsquare, cyan); for (int j = 0; j < n; j += 1) if (j != b) fill(shift(a, j) * unitsquare, cyan); fill(shift(a, b) * unitsquare, red); for (int i = 0; i < n; i += 1) { for (int j = 0; j < n; j += 1) { draw(shift(i, j) * unitsquare, black+1pt); }} [/asy][/asy] Now we focus on the case $n$ odd. First, we exhibit a construction which shows $n^2 - n + 1$ cannot be improved. Consider the matrix with ones only in the bottom row, but not in the bottom-left corner: \[ \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 1 & 1 & 1 & 1 \end{bmatrix}.\]We claim this cannot be modified into a table with more than $n^2 - n + 1$ zeroes. Observe that every move toggles the sum of every line (row and column). If there are an odd number of toggles, then every row will contain a one, hence at most $n^2 - n$ zeroes. If there are an even number of toggles, then the right $n-1$ columns will all contain a one, hence at most $n^2 - n + 1$ zeroes. Now we present an algorithm to obtain $n^2 - n + 1$ zeroes. First, we claim that it is possible to zero out the top-right $(n - 1) \times (n - 1)$ submatrix $A$. To do so, note that toggling the three colored cells flips the dark blue cell, but no other cell in $A$. [asy][asy] int n = 7; int a = 3, b = 4; fill(shift(a, b) * unitsquare, blue); fill(shift(a, 0) * unitsquare, lightblue); fill(shift(0, b) * unitsquare, lightblue); for (int i = 0; i < n; i += 1) { for (int j = 0; j < n; j += 1) { draw(shift(i, j) * unitsquare, black+1pt); }} draw((1, 1)--(n, 1)--(n, n)--(1, n)--cycle, black+2pt); [/asy][/asy] Thus we may zero out the entirety of $A$. Finally, note that by toggling the lower-left cell, we may ensure that at most half of the remaining $2n-1$ cells are ones. This gives at least $n^2 - n + 1$ zeroes, as desired.

The answer is $$N(n)=\begin{cases}n^2-n+1&\text{if n is odd}\\ n^2&\text{if n is even}\end{cases}$$We will consider everything modulo $2$. Firstly we will show that if $n$ is odd then $N(n)\leq n^2-n+1$. Indeed, let $r_1,r_2,...,r_n,c_1,c_2,...,c_n$ be the sum of numbers in the rows and columns. Then notice that in each operation all of the variables are changed from $0$ to $1$ or vice versa. Therefore if originally the numbers are $$\begin{pmatrix}0&1&1&...&1\\0&0&0&...&0\\ ...&...&...&...&...\\0&0&0&...&0\end{pmatrix}$$then we have $(r_1,...,r_n,c_1,..,c_n)=(0,...,0,0,1,...,1)$, after one operation this vector becomes $(1,...,1,1,0,...,0)$, and $(0,...,0,0,1,...,1)$ after another operation, hence there are at least $n-1$ odd numbers every time. Secondly we will show that the claimed value of $N(n)$ is attainable. We will first show this for the case where $n$ is even. CLAIM. It is possible to change the parity of one cell and fix all other numbers in the board. Proof. By symmetry we will assume that this cell is the top left corner. Notice that by applying the operation to any $n$ cells in which none of them lies in the same row or column, the parity of these $n$ cells are changed while all other numbers in the board are fixed, call this operation $II$. Denote the cell in the $i^{th}$ row and $j^{th}$ column by $(i,j)$. Now apply the operation $II$ to each of the following $n$-tuples $$(1,1),(i,1),(1,i),...(i-1,i-1),(i+1,i+1),...,(n,n), 2\leq i\leq n$$Then all the cells in the first column and first row except the bottom left corner are changed while the other cells are fixed, apply the given operation to the bottom left corner and we are done. $\blacksquare$ Now suppose $n$ is odd, then apply the algorithm for even numbers to the bottom right $(n-1)\times (n-1)$ subboard. Now if the first column and first row contains less than $n-1$ odd number then we are done, otherwise we apply an operation to the top left corner and we are done.

CantonMathGuy wrote: The answer is \[N = \begin{cases*} n^2 & $n$ even\\ n^2 - n + 1 & $n$ odd. \end{cases*}\]We interpret the board state as an element of $\mathbb{F}_2^{n \times n}$. \[ \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 1 & 1 & 1 & 1 \end{bmatrix}.\] Here's a different way to show that the above construction guarantees at least $n-1$ odd numbers. Denote by $S(i,j)$ the set of all cells in the $i$th row and $j$-th column, excluding $(i,j)$. Note any move would toggle an even number of cells of $S(i,j) ~ \forall ~ i,j$. Note that $S(i,k)$ is odd originally for all $1 \le i \le n$ and $2 \le k \le n$. Now consider any position. If each of $k$-th column ($k \ge 2$) contains a odd number, we are fine. Otherwise, if some $k$-th row doesn't contain an odd number, then consider $S(i,k) ~ \forall ~ 1 \le i \le n$ gives each row contains an odd number, done! $\blacksquare$

Work mod $2$ For $n$ even, the answer is $n^2$. I claim I can change the parity of any single cell $X$. I can do so by toggling all cells in its column and row. Note this cell is toggled $2n-1$ times so it changed. If a cell is not on the same row or column as $X$ then it has been toggled twice, so it doesn't change. If a cell is on the same row or same column then it has been toggled $n$ times, so it doesn't change. For $n$ odd, the answer is $n^2-n+1$. First I prove this is always doable. We ignore the bottom row and the bottom column. Since we can make all cells zero in an $(n-1) \cdot (n-1)$ board, the only 1's are now in the rightmost column and lowest row. If there are at least $n$ 1's, by toggling the bottom right corner, we can have at most $2n-1-n$ 1's, so we are done. Now we prove this is optimal. We make the bottom row except for the bottom right corner 1 only. I claim it is impossible to get fewer than $n-1$ 1's. Note the operation changes the parity of 1's in every row or column. Therefore if I toggle an odd number of times, there is a 1 in every row. If I toggle an even number of times, the leftmost $n-1$ columns all contain a 1.

Casework when $n$ is odd/even. Case1. $n$ is even: my sol is similar to the above ones so no bother posting Case2. $n$ is odd: the theoretical proof of $n\geqslant n^2-n+1$ is simple. Construction: Consider the sum of rows ($s_1,s_2,\cdots,s_n$) and sum of columns ($t_1,t_2,\cdots,t_n$). Any operation will change the parity of all the $s_i$ and $t_i$. WLOG assume that in the beginning we have all the $s_i$ are even while all the $t_i$ are odd. One example here: \[\begin{bmatrix} 0 & \cdots & 0 & 0\\ \vdots & \cdots & \vdots & \vdots \\ 0 & \cdots &0 & 0\\ 1 & \cdots &1 & 0\\ \end{bmatrix}.\]It's easy to see that there are always at least $n-1$ odd numbers in the board. The end.

The answer is $n^2$ if $n$ is even and $n^2-n+1$ if $n$ is odd. Interpret the board modulo $2$. Let a cross at $c$ be the set of cells sharing a row or column with $c$ (including $c$ itself). In general, toggling every cell's cross adds $1$ to all of them. Now if we take a "rook set" of size $n$ and toggle each of its elements' crosses, the rook set (and nothing else) gets toggled. By comparing two rook sets which share exactly $n-2$ elements, we can toggle any four cells which form a rectangle. For $n$ even, we forget to look for simple constructions and instead exhibit the following proof that we can toggle any given cell: By toggling the same row twice but different column, we can also toggle the intersection of any $2$ rows and $n-1$ columns, or $2$ columns and $n-1$ rows. Combined with the previous result about toggling "rectangles", this implies that we can toggle any two cells sharing a row or column, since $n-1$ is odd, so for a given row and column we can break up all the cells aside from their intersection into pairs lying on the same row/column and toggle them, then toggle the row+column, which ends up toggling only the intersection cell. For $n$ odd, we first prove that we can always achieve at least $n^2-n+1$ even numbers. Indeed, consider the top left $(n-1) \times (n-1)$ subgrid: I claim that we can make this into zeroes. For linear algebra reasons, it suffices to prove that the crosses at $c$ for $c$ lying in the $(n-1) \times (n-1)$ subgrid are linearly independent in $\mathbb{F}^{n \times n}_2$, i.e. no nonzero linear combination of them forms the "zero board". Suppose that such a linear combination existed. By considering the cells outside the subgrid, every row and column must have been toggled an even number of times. On the other hand, if we pick a cell $c$ in the subgrid such that the coefficient of the cross at $c$ is nonzero in this linear combination, it is clear that this means $c$ was toggled an odd number of times (since by adding the row and column $c$ lies on, we overcount the cross at $c$ once): contradiction. Now that we have made the $(n-1) \times (n-1)$ subgrid all $0$, we may also choose to toggle the bottom right cross. This will guarantee that at most $\lfloor \tfrac{2n-1}{2}\rfloor=n-1$ of the cells are $1$, as desired. For a construction, we first have to lay down some additional facts. Call two board states linked if they can be reached from each other by a series of normal toggles (i.e. their difference is a sum of crosses), and rect-linked if they can reach each other in a series of of the "rectangle toggles" mentioned above. Observe that for $n$ odd, by breaking an $(n-1) \times (n-1)$ subgrid into $2 \times 2$ squares and using the "rectangle toggle" on each, any board state is rect-linked to its image after its entries are all flipped and then a cross at any cell is added. Therefore, if two board states $A$ and $B$ are linked, then $A$ is either rect-linked with $B$, or the image of $B$ after all its entries are flipped. The construction we will now employ is to set the entire bottom row, except for the rightmost element, to $1$, and the rest of the grid to $0$. If each of its entries are flipped, and then the top-left $(n-1) \times (n-1)$ subgrid is "rectangle toggled", we obtain a board where the rightmost row is all $1$ and the rest of the elements are $0$. Every board linked to the original board is rect-linked to one of these two boards. However, it is clear that "rectangle toggles" don't change the parity of the number of one elements in each row or column, hence any board rect-linked to the first must have $n-1$ columns with an odd number of ones, and any board rect-linked to the second must have $n$ rows with an odd number of ones, hence we always have at least $n-1$ elements in the grid equal to $1$, as desired. $\blacksquare$

Solved with rama1728. We claim that the answer is, \[N(n)= \begin{cases} n^2 & \text{if } n \equiv 0 \pmod{2}\\ n^2-n+1 & \text{if } n \equiv 1 \pmod{2} \end{cases} \]Note that we can simply look at the board $\pmod{2}$. An odd number is replaced by $1$ and an even one by $0$. Then, doing a move on a square simply corresponds to flipping the state of each cell in the same row and column. We first show that these bounds are achievable. For this we define the following algorithm. Algorithm : It is possible to flip the state of one and exactly one cell of this grid using the following algorithm. For an $2k\times 2k$ grid, simply consider the desired cell. Then, we do a move on each cell of the same row and column. Then, every cell which is not on this row/column, wil be flipped exactly twice. Every cell in the same row/column as the chosen cell will be flipped $2k$ times and thus, preserve its state. Meanwhile, the required cell will be flipped $4k-1$ times, and thus, it will change state which is simply the required configuration. Now, by this Algorithm, it is possible to convert all cells of a $n\times n$ grid into $0$ when $n$ is even. Now, if $n$ is odd, we simply consider the $(n-1)\times (n-1)$ grid on the top-left corner. Then, we repeat the algorithm, but only on the cells which are inside this area (we flip only the cells in this area and consider only the squares of the row/column which are inside this area). Then, we are left with a $(n-1)\times (n-1)$ grid of all zeros and the outer $L$ shape. If this has more zeros than ones, we have at least $n$ zeros and if not, simply do a move on the bottom-right corner cell, which guarantees $n$ zeros in this section. Thus, we always have at least \[(n-1)^2+(n+1)=n^2-2n+1+n = n^2-n+1\]zeros which is the desired value. Now, we continue to show, that for odd $n$ it is impossible to have more than $n^2-n+1$ zeros. For this, simply consider the following initial configuration(all rows have all zeros, except last row which has all ones besides the first column). \[ \left[ {\begin{array}{cccc} 0 & 0 & \dots &0 \\ 0 & 0 & \dots & 0 \\ \vdots & \vdots &\vdots &\vdots\\ 0 &0 &\dots &0\\ 0&1&\dots &1 \end{array} } \right] \]Now, we simply look at the parity sums of digits in each row and column. We record this in a $2n-$tuple with $1$ if it is odd and vice versa. Note that, each move flips every element of this tuple since each move adds one to all elements, of said row and column and we have an odd number of rows and columns. We start with $n-1$ ones, and so we always oscillate between $n+1$ and $n-1$ ones in the $2n-$tuple. Thus, we always have at least $n-1$ ones in this $2n-$tuple, which implies that at least $n-1$ row/column must have an odd sum, requiring at least $n-1$ ones to exist in this grid. Thus, it is impossible to have more that $n^2-n+1$ zeros in this grid if $n$ is odd. Thus, the answer is as claimed and we must be done.

nice problem! Casework mod 2 CASE 1: $n$ is even Toggle all the cells in its "hook", it is toggled $2n-1$ times hence it changes, while other remain same, so the answer for $n$ even is $n^2$ CASE 2: $n$ is odd Consider the following $ \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 \end{bmatrix} $, it is easy to see that we cannot ensure more than $n^2-n+1$ 0s To ensure exactly $n^2-n+1$, make $(n-1) \cdot (n-1)$ full of $0's$ then toggle the bottom left corner cell to ensure atleast half are $0's$. Hence we're done.