98 clicks!

Neat problem. Indeed, the answer is $98$, but it's nicer to have a proof posted, isn't it? I just hope this one's correct. Let's prove a moregeneral assertion: given an $m\times n$ board, in the same conditions, the answer to the same question is $\left\lfloor\frac m2\right\rfloor+\left\lfloor\frac n2\right\rfloor\ (*)$. I won't bother to describe an example which shows that $(*)$ does indeed work. It's a bit hard to explain in writing, but it should be obvious after playing around with a board. You take your rectangles to be $\left\lfloor \frac m2\right\rfloor$ horizontal rectangles of height $1$ and width $n$, and $\left\lfloor \frac n2\right\rfloor$ vertical rectangles of height $m$ and width $1$. Conversely, we have to prove that $(*)$ is minimal. Notice that any collection of rectangles with the desired property must also have the property that every segment on the board, except for those on the outer edges, must belong to the boundary of at least one rectangle in the collection. It thus suffices to show by induction on $m+n$ that a collection $\mathcal C$ with this latter property must contain at least $(*)$ rectangles. The small cases are easy to check, so assume now that we've proven the assertion for values of $m+n$ smaller than the current one. Assume that $m\le n$, and let the rectangle be named $ABCD$, with $BC$ and $AD$ being the lower and upper horizontal sides of length $n$ respectively. If $\mathcal C$ contains no rectangles with one side on $AD$ and one side on $BC$, it means that we need at least $\left\lfloor \frac n2\right\rfloor$ rectangles to cover the vertical segments of length one with one endpoint on $BC$, and $\left\lfloor \frac n2\right\rfloor$ more to cover those which have an endpoint on $AD$, i.e. we have $\ge 2\left\lfloor \frac n2\right\rfloor\ge (*)$ rectangles in total. On the other hand, if we do have a rectangle $R$ with the upper horizontal side on $AD$ and the lower one on $BC$, we can assume that its vertical sides are different from $AB,CD$. For each one of its vertical sides, merge the two columns to the right and to the left of the respective side, and eliminate $R$. We get a new problem, with an $m\times (n-2)$ table, which requires at least $(*)-1$ rectangles by the induction hypothesis. We add $R$ back into the picture, and we reach the desired conclusion: $\mathcal C$ must have $\ge (*)$ elements.

i feel really weird posting this We will prove that on an n*n board, there are n clicks required when n is even. Induct Base On a 2*2, there are clearly 2 click required. Inductive step WLOG, let the top left square be black. On an n*n board, do the n-2 clicks for the previous case. Then we are left with an (n-1)*(n-1) black square. and then 2 white strips with a black square in the bottom right corner. it kinda likes like b b b ... b w b b b ... b w b b b ... b w . . . . . . . . . . . . . . . b b b ... b w w w w ... w b then just click the bottom 1*98 rectangle and the 98*1 rectangle on the side and you're done. To prove this is the shortest way. use the fact that an (n-2)*(n-2) requires atleast n-2 clicks to show that n-1 clicks isnt possible.

abacadaea wrote: To prove this is the shortest way. use the fact that an (n-2)*(n-2) requires atleast n-2 clicks to show that n-1 clicks isnt possible. Unfortunately, I think this is the non-trivial part (and probably isn't true), but I think you might have misunderstood the problem anyway (or have I?).

It may be simpler to consider border tiles (tile is a pair of adjacent squares). For nxn board we have 4(n-1) border tiles. At most we can make four tiles into matching ones (choose a column of length n that doesn't contain a corner). So we need at least n-1. However corners screw this up so the minimum is n.

Hmm, I think this works.

My solution. I think it works..

Consider any even $n$ in place of 98. There are $4n-2$ grid vertices adjacent to oddly many black squares (all external ones except two white corners), call these bad, and good otherwise. Consider a move on rectangle $R$. If grid vertex $v$ is not a vertex of $R$, it is adjacent to evenly many squares in $R$, so after the move $v$ retains its state as good/bad. Thus only the 4 vertices of $R$ can change their state. Now every move decreases $S$, the number of bad vertices, by at most 4. But in the end $S=0$, thus we need at least $n$ moves. Take $\frac{n}{2}$ rows to get $\frac{n}{2}$ black columns, then take these columns. Thus $n$ is indeed the minimum.

We consider a $2n\times 2n$ grid instead of $98$. Now, you can do it in $2n$ click by first selecting all odd rows in first $n$ moves then odd column in next $n$ moves. Now, we show that this bound is optimal. WLOG, assume that the colour we end up with is the colour of the bottom left square(say white). Now, we ignore the complete grid except the bottom row and left most column. We only consider their action on these squares. Now, the number of rectangles acting on the corner must be even. So, we can randomly pair them. Now, for any pair of these rectangles, take the resultant of their action on the row and the column, as the resultant of these two is equivalent to two different rectangles acting on just the row and just the column(we can ignore the common part), we can replace these with the new rectangles. Now, every rectangle just acts on the row or the column. Again observe that any two intersecting rectangles can be replaced with two non-intersecting rectangles. Now, as any rectangle now does not intersect with any other rectangle, it cannot have any white squares. So, every rectangle is a single black square. Now, there are $n$ black squares in the rows and $n$ black squares in the columns. Thus, we get a total of $2n$ different rectangles.

Solution from Twitch Solves ISL: The answer is $98$. One of several possible constructions is to toggle all columns and rows with even indices. In the other direction, let $n = 98$ and suppose that $k$ rectangles are used, none of which are $n \times n$ (else we may delete it). Then, for any two orthogonally adjacent cells, the edge between them must be contained in the edge of one of the $k$ rectangles. We define a gridline to be a line segment that runs in the interior of the board from one side of the board to the other. Hence there are $2n-2$ gridlines exactly. Moreover, we can classify these rectangles into two types: Full length rectangles: these span from one edge of the board to the other. The two long sides completely cover two gridlines, but the other two sides of the rectangle do not. Partial length rectangles: each of four sides can partially cover ``half a'' gridlines. See illustration below for $n = 6$. [asy][asy] unitsize(0.5cm); picture base; for (int i=1; i<=5; ++i) { draw(base, (0,i)--(6,i), black ); draw(base, (i,0)--(i,6), black ); } picture full; picture partial; add(full, base); add(partial, base); label(full, "Full length", (3,0), dir(-90), red); label(partial, "Partial length", (3,0), dir(-90), blue); filldraw(full, box( (0,3), (6,1) ), lightred+opacity(0.3), red+1.4 ); filldraw(partial, box( (2,2), (4,5) ), lightcyan+opacity(0.3), blue+1.4 ); add(shift(0,0)*base); add(shift(7,0)*full); add(shift(14,0)*partial); [/asy][/asy] Since there are $2n-2$ gridlines; and each rectangle can cover at most two gridlines in total (where partial-length rectangles are ``worth $\frac{1}{2}$'' on each of the four sides), we immediately get the bound $2k \ge 2n-2$, or $k \ge n-1$. To finish, we prove that: Claim: If equality holds and $k = n-1$, then $n$ is odd. Proof. If equality holds, then look at the horizontal gridlines and say two gridlines are related if some rectangle has horizontal edges along both gridlines. (Hence, the graph has degree either $1$ or $2$ at each vertex, for equality to hold.) The reader may verify the resulting graph consists only of even length cycles and single edges, which would mean $n-1$ is even. $\blacksquare$ Hence for $n = 98$ the answer is indeed $98$ as claimed.

The desired minimum is 98. To show that it is achievable, first we make a move on all even columns and then on all odd rows. Now we have to show that this is indeed the desired minimum. We observe that each edge between squares has to be on the border of a rectangle we make a move on at least once, since otherwise the squares on the two sides of it will be different colors. Call a special edge an edge of the grid(between two squares) which is connected to the border of the board but not on the border. There are a total of $4(98-1)$ such special edges. Also each rectangle we make a move on has at most 4 special edges on it's border. But we have to change the color of two of the corner squares, and the rectangles we make a move on in order to do this contain at most 2 special edges, implying that we need at least $(4(98-1)-4)/4+2 = 98$ rectangles in order to have made a move on all of the special edges.

The answer is 98. In general, for an $n\times n$ board with even $n$, the answer is $n$. For the construction, hit all of the odd numbered rows and columns. To prove optimality, note that the edge between any pair of adjacent squares must be in the perimeter of one of the flipping rectangles. Consider the $2(n-1)$ edges attached to the top/bottom of the board and the $2(n-1)$ edges attached to the left/right side. Each rectangle can hit at most: (1) 4 vertical edges (2) 1 vertical edge and 1 horizontal edge (3) 4 horizontal edges. Clearly, at least $\frac{2(n-1)+2(n-1)}{4}=n-1$ are needed. However, $n-1$ is also not achievable because in order for each rectangle to hit 4 edges, all of them must be (1) or (3), and since there are $2\cdot 97\equiv 2\pmod{4}$ top edges, this is impossible. Thus, there are at least $n$ flipping rectangles and we're done. $\blacksquare$.

a bit jank The answer is $98$, which works by toggling every other row and every other column. To prove that this is minimal, consider the following problem: the $98 \times 98$ board starts off completely white, and by performing the same color-toggle operation we wish to color it into a checkerboard pattern such that the top left square is white. This is clearly equivalent to the original. Claim: Consider a $1 \times 98$ section of the board. If $k$ selected rectangles intersect it, then the black tiles form at most $k$ black connected components. Furthermore, if the end tiles of the section are opposite color, we actually have at most $k-a$ connected components, where $a$ of the intersecting rectangles intersect the entirety of the section. Proof: We first prove the first part of the claim by induction on $k$, with the base case of $k=0$ being obvious. Our inductive step consists of proving that flipping some rectangle part of the section increases the number of connected components by $1$. We consider these three cases: If both endpoints of the rectangle are black, and the rectangle contains $m$ black components, then upon being flipped there are $m-1$ black components. Since the endpoints could have been connected to larger black components that don't get deleted, there is a guaranteed loss of $m-2$ black components, so the number of components increases by at most $1$. If both endpoints of the rectangle are white, and the rectangle contains $m$ black components, then upon being flipped there are $m+1$ black components, so the increase is at most $1$. If one endpoint is black and one is white, then the flipped rectangle contains the same number of black components as before (both $m$). Since the black endpoint could've been part of a larger component, there is a guaranteed loss of $m-1$ black components, so the number of components increases by at most $1$. Now to prove the "extended claim", we work backwards. The actual order of the rectangles doesn't matter, so apply the "completely covering" rectangles last. Note that the inverse application of a rectangle on a checkerboard pattern in a $1 \times 98$ triangle doesn't change the number of connected components (since $98$ is even), so after applying all of those last we are left with $k-a$ rectangle intersections which can produce at most $k-a$ black connected components. To finish the problem, we consider the left, right, top, and bottom $1 \times 98$ sections of the chessboard. After all the rectangles are drawn, these rectangles should each have $49$ connected black components (considered independently, not together). We thus need a total of $49 \cdot 4=196$ rectangle intersections which aren't "complete covers". On the other hand, any given rectangle can only intersect two of the sections without covering them, since if a rectangle covers two opposite sections and also intersects a third, then the third section must be completely covered. Thus we require at least $196/2=98$ rectangles, which is the desired bound. $\blacksquare$