flipping rows on a matrix in F2

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

w

15 users

TOPICS

No tags match your search

M

No tags match your search

M

flipping rows on a matrix in F2

G H J

Reveal topic tags

linear combination

L

G H BBookmark kLocked kLocked NReply

Source: Croatia TST 2016

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

99 posts

#1 h Apr 27, 2016, 5:21 PM • 3 Y

Y by nguyendangkhoa17112003, Adventure10, Mango247

Let $N$ be a positive integer. Consider a $N \times N$ array of square unit cells. Two corner cells that lie on the same longest diagonal are colored black, and the rest of the array is white. A move consists of choosing a row or a column and changing the color of every cell in the chosen row or column.
What is the minimal number of additional cells that one has to color black such that, after a finite number of moves, a completely black board can be reached?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3212 posts

#2 h Apr 28, 2016, 11:33 AM • 9 Y

Y by baopbc, ineX, NTA1907, jev2001, tpdtthltvp, cookie112, bluedragon17, Adventure10, KK_1729

Answer

Solution

This post has been edited 4 times. Last edited by shinichiman, Apr 28, 2016, 1:08 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

91 posts

#3 h Apr 30, 2016, 1:40 AM • 2 Y

Y by vjdjmathaddict, Adventure10

Inductive solution. We prove that at least $2N-4$ additional squares must be colored black. Number the rows $1$ to $N$ from bottom to top and columns $1$ to $N$ from left to right. Initially cells $(1,1)$ and $(N, N)$ are black.

Lemma. Every $2 \times 2$ square must contain an even number of black squares to begin with.
Proof. A move does not change the parity of the number of black squares within a $2 \times 2$ square since we either change $1, -1 \longleftrightarrow -1, 1$ or $1, 1 \longleftrightarrow -1, -1$ . $\blacksquare$

Let $(i, j)_S$ denote the square containing cells $(i, j), (i+1, j), (i, j+1), (i+1, j+1)$ .

Finally, proceed by induction. Base case $N = 2$ is trivial. Consider an $N \times N$ board. The squares $(1,1)_S$ and $(N-1, N-1)_S$ must contain at least one other black cell. Suppose cell $(2,2)$ (or $(N-1, N-1)$ symmetrically) is colored. If there are two black cells in the first row or first column, we can invoke the induction hypothesis to get that there are at least $2(N-1) - 2 + 2 = 2N-2$ black cells on the board to begin with. If, collectively, row $1$ and column $1$ contain only one black cell (on $(1,1)$ ) we can consider the two sequence of squares $(1, 2)_S \rightarrow (1,3)_S \rightarrow \cdots \rightarrow (1, N-1)_S$ and $(2,1)_S \rightarrow (3, 1)_S \rightarrow \cdots \rightarrow (N-1, 1)_S$ to get that there are at least $2(N-1)+1 = 2N-1$ black squares on the board. So we can assume that neither $(2,2)$ nor $(N-1, N-1)$ are colored.

WLOG $(1,2)$ is colored black. If $(N, N-1)$ is also coloured, we consider $(1, 2)_S \rightarrow (1,3)_S \rightarrow \cdots \rightarrow (1, N-1)_S$ and $(N-1,N-2)_S \rightarrow (N-1, N-3)_S \rightarrow \cdots \rightarrow (N-1, 1)_S$ to get that there are at least $2N$ black squares (each square in the sequences above 'adds' a black cell, creating a snake-like pattern extending across the board. Note that by adding a black cell to $(1, k)_S$ we also add one to $(1, k+1)_S$ because otherwise $(2,2)$ must be colored black). Hence (since $(N, N-1)$ and $(N-1, N-1)$ are both white) $(N-1, N)$ is colored black. This allows us to consider $(1, 2)_S \rightarrow (1,3)_S \rightarrow \cdots \rightarrow (1, N-2)_S$ and $(N-1, N-1)_S \rightarrow (N-2, N-1) \rightarrow \cdots \rightarrow (2, N-1)$ to conclude that at least $2(N-1) = 2N-2$ squares are colored unless the cell $(2, N-1)$ , the overlap of $(1, N-2)_S$ and $(2, N-1)_S$ , is black. But then cell $(1, N)$ must be colored black so that $(1, N-1)_S$ contains two black cells. In all cases we must have at least $2N-2$ squares colored black in order for the procedure to work. The construction is noted in the post above.

This post has been edited 3 times. Last edited by SFScoreLow, Apr 30, 2016, 1:48 AM
Reason: typos

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6882 posts

#4 h Aug 4, 2020, 3:57 AM • 9 Y

Y by Mathematicsislovely, CALCMAN, v4913, hakN, Executioner230607, HamstPan38825, Mango247, Mango247, MS_asdfgzxcvb

Solution from Twitch Solves ISL:

The answer is $2n-4$ additional cells.

We'll do the usual reduction: all the moves commute with each other and doing the same move twice does nothing. Also, it'll be more natural to get from all-white to the ``starting'' state; we'll do so as they are equivalent anyways.

Thus, we may as well assume (by permuting rows/columns)

we operated on the first $a$ rows;
we operated on the first $b$ columns.

The given hypothesis is equivalent to saying that if we do this operation on an initially empty board, then we got $k$ black cells, and at least two of them are not in the same row or column. The problem asks for the smallest possible value of $k-2$ .
However, the point is that we have the explicit value $k = a(n-b) + b(n-a).$ It will be more economical actually to write $n^2 - k = ab + (n-a)(n-b) \le \sqrt{ \left( a^2+(n-a)^2 \right) \left( b^2+(n-b)^2 \right)}.$ We now analyze two cases:

If any of $a$ or $b$ are $0$ or $n$ , we may directly check we need $k \ge 2n$ in order to have two black cells not in the same row or column.
Otherwise, $x^2 + (n-x)^2 \le 1 + (n-1)^2$ for $1 \le x \le n-1$ , so $n^2 - k \le 1^2 + (n-1)^2$ which means $k \ge 2n-2$ .

In conclusion, $k-2 \ge 2n-4$ ; and moreover equality occurs at $a=b=1$ , which is checked to indeed work.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

87 posts

#5 h Apr 12, 2022, 1:34 AM

Y by

This is a very badly written solution, I am sorry for that

. Also, my solution is almost the same solution as shinichiman's but I did not use the notation he used.
The answer is $2N-4$ .

$N=2$ is trivial, so we let $N\ge3$ .
Let $a_{k}$ be the number of times we change the colors in the $k$ th column(and similarly $b_k$ for the rows.) For any cell $(i,j)$ we have,
$\Rightarrow a_{i} + b_{j} = 2k$ (if $(i,j)$ is black)
or
$\Rightarrow a_{i} + b_{j}= 2k+1$ (if $(i,j)$ is white )

$\textbf{Case:1}$ There is exactly one black cell in the first column.

So except for this cell, $a_1 + b_j$ is odd for all $j>1$ . But since $(n,n)$ is initially black, we need all of the cells in the $n$ th column to be black which gives us $N-2$ more cells( $b_j$ have the same parity). Also, notice that for any $k$ th row, $a_k+b_j$ has the same parity, so initially, they are either all black or all white. (leaving the first cell in all the columns). To minimize we keep $1$ black cell in all these columns, so we get another $N-2$ from here giving us a total of $2N-4$ $\blacksquare$

$\textbf{Case:2}$ There is more than one black cell in the first column.

$a_1+b_j$ is again odd, so $b_j$ has the same parity but only for the black cells and of course, $j>1$ .. So all the cells in the rows of these black cells are either all black or all white, we set all of them to be white to minimize. Thus, if we have $k\geq2$ additional black cells in the first column, we basically have $N-k$ additional black cells in the rest of the columns except for the last one. Using the same parity argument for the last column, we see that we atleast need $k-2$ additional black cells taking account of the fact that $(N,N)$ is already black.
$\Rightarrow$ $k+(N-2)(N-k) + k-1 \geq k + 2(N-2) + k-2 > 2N-4$ $\blacksquare$

This post has been edited 4 times. Last edited by bluedragon17, Apr 13, 2022, 12:46 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1080 posts

#6 h Feb 24, 2023, 4:58 AM • 1 Y

Y by centslordm

Denote the square in the $i$ th row and $j$ th column as $(i,j)$ . WLOG let $(1,1)$ and $(n,n)$ be the diagonally painted squares. We claim the answer is $2n-4$ , which works when we paint the symmetric difference of the first column and last row. Swapping the last row and all the columns after the first gives a fully painted grid.

If we end up swapping $a$ rows and $b$ columns, we begin with $ab+(n-a)(n-b)$ painted squares. This is because $(i,j)$ must begin painted if and only if both row $i$ and column $j$ are swapped or they are both not swapped.

Consider when $a=0$ . Then, we cannot swap the first or last column since $(1,1)$ and $(n,n)$ need to be swapped an even number of times. Hence, all of the first and last column need to be painted, resulting in at least $2n$ painted squares. If $a=n$ , we must paint the first and last column so we again have at least $2n$ painted squares. Similarly, $b=0$ and $b=n$ yield at least $2n$ painted squares.

We claim that $ab+(n-a)(n-b)\ge 2n-2$ when $0<a,b<n$ . Indeed, $0\le (n-a-b)^2=[n^2+2ab-n(a+b)]-[n(a+b)-a^2-b^2]$ so $\begin{align*}[ab+(n-a)(n-b)]-[2n-2]&=2ab+n^2-n(a+b)-2n+2\\&\ge n(a+b)-a^2-b^2-2n+2\\&=[n(a-1)-a^2+1]+[n(b-1)-b^2+1]\\&=(n-a-1)(a-1)+(n-b-1)(b-1)\\&\ge 0\end{align*}$ as desired. $\square$

This post has been edited 1 time. Last edited by Mogmog8, Feb 24, 2023, 8:54 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8877 posts

#7 h Mar 12, 2023, 4:53 AM

Y by

The answer is $2n-4$ . For a construction, color one row that contains one of the corner squares black, a column that contains the other corner square black, and their intersection white. We will look at the problem backwards, where we start from a completely black grid and attempt to leave as minimal black squares left as possible via valid operations.

Claim. Suppose that $k \geq n-1$ rows and columns that are not along the periphery of the grid are chosen. Then the number of intersection points between these rows and columns is at least $(n-2)(k-n+2)$ .

Proof. Tautological. $\blacksquare$

Thus, if $k \geq n-1$ rows and columns are chosen, the number of white squares (squares toggled exactly once) within the interior $(n-2) \times (n-2)$ square is at most $(n-2)^2-(n-2)(k-n+2) = (n-2)(2n-4-k)$ .

On the other hand, the number of squares that are now white that share a row or column with each one of the corner squares is precisely $k$ respectively. Thus, we can guarantee at most $\text{max}(k, 2n-2-k) = k$ more white squares among the non-corner periphery squares, as both of the edge rows and columns can be toggled or neither can be toggled to keep the corner square black. (Note that the two other corners can be made white.) As a result, the total number of white squares is at most $N = (n-2)(2n-k) + 2k + 2 = n(n-2) + 2 - (n-4)(k-n+2) \leq n^2-2n+2.$ This proves the bound for $k \geq n-1$ ; if $k \leq n-2$ , the total number of toggled squares is obviously at most $n^2-2n$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3761 posts

#8 h Nov 14, 2023, 11:45 PM

Y by

solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2534 posts

#9 h Dec 22, 2023, 8:58 PM

Y by

For this solution, denote $(i,j)$ as the square in the $i$ th row and $j$ th column; we will consider getting from the all-white state to our starting position as it is easier to work with.

The answer is $\boxed{2n-4}$ . Letting the original shaded squares be $(1,1)$ and $(n,n)$ , the optimal coloring being the symmetric difference of row $1$ and column $n$ .

For simplicity, denote each row/column as \textit{toggled} if it differs from its original state and \textit{original} otherwise. Suppose we toggle $a$ rows and $b$ columns. For $(i,j)$ , ending up as a white square in the starting position requires both row $i$ and column $j$ to either be both toggled or both original, hence the number of black squares in the starting position is

$n^2-ab+(n-a)(n-b) \ge n^2-\sqrt{(a^2+(n-a)^2)(b^2+(n-b)^2)}$
where the inequality follows by Cauchy. Then, it follows that the RHS is optimized at $a=b=1$ , which corresponds to $2n-2$ squares starting out black. Taking away the corners gives our desired minimum.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1329 posts

#10 h Jan 6, 2024, 3:26 PM

Y by

All moves are commutative, so we only need to invert rows and columns at most once, and order doesn't matter.
$\newline$
Consider starting from an all-white position, and inverting to our starting position.
$\newline$
If we invert $a$ rows and $b$ columns, then the total number of black squares in our starting position is $n^2- (ab + (n - a)(n - b))$ , because a square is left white(and needs to be colored black) if it is inverted $0$ times or $2$ times.
Our goal is to minimize $ab + (n - a)(n - b)$ .
$\newline$
Note that $(ab + (n - a)(n - b)) \leq \sqrt{(a^2 + (n - a)^2)(b^2 + (n - a)^2}$ $\sqrt{(a^2 + (n - a)^2)(b^2 + (n - a)^2} \geq \sqrt{(1^2 + (n - 1)^2)(1^2 + (n - 1)^2} = n^2 - 2n + 2$ .
$n^2 - (n^2 - 2n + 2) = 2n - 2$ .
Subtracting two(because the corner cells are already filled in) gives us $2n - 4$ which is achievable by coloring $n - 2$ cells on the bottom row(without coloring in the corner cell) and then coloring $n - 2$ cells on the left column without coloring in the corner cell.
$\newline$
Swapping the bottom row and then the leftmost column makes everything white, and from there it is easy to swap to make everything black.

This post has been edited 1 time. Last edited by dolphinday, Jan 6, 2024, 3:27 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

802 posts

#11 h Jan 21, 2024, 10:00 PM

Y by

Noting that operations are commutable and that it is useless to operate on a single row/column multiple times, suppose we operate on $x$ rows and $y$ columns, where $0 \leq x, y \leq n$ . Then the number of squares toggled an even number of times is
$ab + (n-a)(n-b) = n^2-(a+b)n+2ab,$
or the number of originally black squares. To minimize this expression, note $(x,y) = (0,n)$ fails, so the next best we can do is $(x,y)=(1,n-1)$ , which is easy to construct. Thus our answer is
$\left(n^2-n \cdot n + 2(n-1)\right) - 2 = \boxed{2n-4}.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

102 posts

#12 h Apr 7, 2024, 1:26 AM

Y by

is this correct?

Let $a_{i,j} \in \{0,1\}$ refer to the color of the cell at the $i$ th row $j$ th column, where $1$ is black and $0$ is white. A move is equivalent to adding one to each cell of a row/column modulo $2$ . Note that applying the move to the same row/column twice is pointless, and the order of the moves doesn't matter. Next, observe that once we've determined whether the first row is flipped, we also determine whether each of the columns are flipped. (If $a_{1,j}$ is currently white, we must flip column $j$ , and otherwise, we don't.) Once we apply these determined moves, each row must be monochromatic (since we've determined everything else).

Let row $1$ have $k$ black cells after we've determined if it's flipped. Then, we'd have to flip $n-k$ columns. For each row, the flipped cells and not flipped cells must initially have different colors in order for the rows to be monochromatic after applying the column moves. Thus, there are either $k$ or $n-k$ black cells in each row (including the first). For a fixed $2\le k\le n-2$ , the least number of additional black cells is
$n\min\{k,n-k\}-2\ge 2n-2$ For $k=1$ or $n-1$ , we actually can't achieve $n$ since it would imply that the original configuration solely consists of the first column black. The next smallest value is
$(n-1) + \underbrace{1 + \cdots + 1}_{n-1} - 2 = 2n-4$ For $k=0$ or $n$ , the original configuration would consist of monochromatic rows, yielding a minimum of $2n$ . Overall, the minimum is $2n-4$ . This may be achieved by coloring $a_{1,k}$ and $a_{k, n}$ black for $2\le k \le n-1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5425 posts

#13 h Apr 27, 2024, 8:15 PM

Y by

Posting solely to commemorate the remarkable idiocy of my solution... I guess that's what happens when you spend less than 25% of the last week asleep :coolspeak:

:coolspeak:

One can reduce any sequence of moves to the states of $2n$ toggles, one for each row and column. The corners being black implies that exactly one of $r_1,c_1$ and exactly one of $r_n,c_n$ are toggled. Whence the answer is $\boxed{2n-4}$ by toggling $r_1,c_n$ (Case 1), in which case optimality follows since pairs of non-vertex points on opposite sides are of opposite states. If $r_1,r_n$ are toggled (or $c_1,c_n$ but WLOG let it be the former; Case 2), ... let's do something silly: label a row by $1$ if it is untoggled and $i$ if it toggled, and let each cell be the product of its row and column. If $r_u$ is the number of untoggled rows and so on, we want to min
$\text{Im}((r_u+r_ti)(c_u+c_ti))=r_uc_t+r_tc_u.$ Here in Case 2, we have $r_t,c_u\ge2$ , at which point the minimum is clearly $2n\ge2n-4$ at, say, $(0,n,n-2,2)$ .

This post has been edited 2 times. Last edited by peace09, Apr 27, 2024, 8:16 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

363 posts

#14 h Aug 4, 2024, 11:37 PM

Y by

For $N = 1$ the answer is trivially $0$ . For $N \ge 2$ we claim the answer is $2N - 4$ .

For construction, define column $i$ as the column with $i - 1$ columns to the left of it. Define similarly for rows from the bottom. Then assign each cell a coordinate $(i, j)$ on column $i$ and row $j$ . WLOG $(1, 1)$ and $(N, N)$ are black. Then color $(i, j)$ black if $1 \le i \le N - 1, j = 0$ or $i = N, 1 \le j \le N - 1$ . Note that this configuration is valid as we can toggle the columns $1, 2, \dots, N - 1$ and row $1$ which turns it all black.

To show it is the actual minimum, consider the all-black array. It suffices to show that if we toggle rows/columns that leaves two opposite corners black, then there must be at least $2N - 2$ black cells on the array. Suppose we toggle $1 \le r \le N$ rows and $1 \le c \le N$ columns, there will be
$rc + (N - r)(N - c) = 2rc - N(r + c) + N^2 = \frac{(2r - N)(2c - N) + N^2}{2}$ black cells. WLOG $r \ge c$ . Then $(2r - N, 2c - N) = (N, -N), (N - 2, -N), (N - 2, -N + 2) \implies (r, c) = (N, 0), (N - 1, 0), (N - 1, 1)$ generate the three smallest possible values of the above quantity in order. Clearly toggling $N$ or $N - 1$ rows cannot form two opposite black corners, but $(N - 1, 1)$ has a valid construction (we described it earlier.) Hence plugging in we have
$(\text{number of black cells}) \ge \frac{(N - 2)(-N + 2) + N^2}{2} = \frac{4N - 4}{2} = 2N - 2$ and we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1757 posts

#15 h Dec 25, 2024, 8:19 PM

Y by

My solution is different from the rest of the solutions on this thread, would appreciate if someone could check it.

Assume that the two diagonally black corners are in the top left and bottom right. The problem is equivalent to coloring the entire grid white as we can then flip the color of every row to get an entirely black grid.

The answer is $\boxed{2n-4}.$ For the construction, we color all the edge pieces on the top and right edges of our grid black, giving $2n - 4$ additional black squares colored. This can be turned into the grid with all black squares as we flip the color of the first row and the last column to get an entirely white grid.

Now we will show that we cannot do better. Assume for the sake of contradiction that at most $2n-5$ additional black squares can be colored so that the grid can be made entirely white. Notice that flipping the color of any row or column twice will do nothing, so we can assume that we flip the color of any row or column at most once.

To turn the bottom right black square into a white square, we must flip the color of exactly one of the last row or the last column. Without loss of generality, suppose that we flip the color of the last row. Then the bottom left corner is now colored black, so we must flip the color of the first column to make it white. Since we use at most $2n-5$ additional black squares and there are $2n-4$ edge squares which we flipped the color of, there is at least one edge square at this point which is now black. Suppose that this edge square is on the bottom row. Since we already flipped the bottom row, we must flip the color of the column of this black square. The result is a shaded square on the top edge. Since we already flipped the column of this new square, we must flip the top row of the grid, which shades the top left corner black. Since we flipped both the top row and leftmost column of the grid, this is a contradiction, and we are done.

This post has been edited 2 times. Last edited by EpicBird08, Dec 26, 2024, 2:28 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

576 posts

#16 h Jan 23, 2025, 4:35 PM

Y by

We claim that the minimum is $2n-4.$ For the construction, pick a corner point not shaded yet and shade everything between this point and a shaded corner, as well as with the other shaded corner. (excluding the endpoints) Then, we can shade the two rows/columns passing through our unshaded corner point to make the entire board white, then we invert the board by inverting every row.

It now suffices to prove the bound. Since every operation is inversible and commutative, it suffices to start from a white board, and find a set of operations that makes at least $2$ squares in two corners black at the end, while minimizing the number of black squares at the end too. Suppose that we toggle $a$ rows and $b$ columns. Then clearly $a+b \geq 2$ in order for it to be possible to choose rows and columns so that the two corner squares are turned black. Similarly we have $a+b \leq n-2.$ Then, observe that after the operations, there are always $na+nb-2ab$ black squares. This also equals $\frac12 \left( n^2-(n-2a)(n-2b) \right).$ It thus suffices to maximize $(n-2a)(n-2b).$ Clearly both of these factors are either positive or negative. If they are both positive, we wish to minimize both $a, b.$ Thus either $(a, b) = (1, 1), (2, 0), (0, 2).$ In the former case we get $2n-2,$ while the other cases yield $n.$ Clearly the maximum is $2n-2$ so in total we would need to add $2n-4$ black squares in the original grid. This result can be similarly found if $(n-2a), (n-2b)$ are both negative. Therefore, the minimum is indeed $2n-4$ black squares.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

980 posts

#17 h Apr 9, 2025, 2:57 AM

Y by

Bad write up

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

637 posts

eg4334

#18 h Apr 26, 2025, 1:27 AM

Y by

sketch

This post has been edited 1 time. Last edited by eg4334, Apr 26, 2025, 1:27 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a