Suppose all unit squares have at most two blue edges(in other words,at least two red edges) Color all unit squares with black and white such that two unit squares which share an edge have different colors since color an edge red will increase the red edge of two unit square with different colors by 1 respectively (except for the boundary,but if we color an edge in the boundary it would only increase 1) so the sum of red edges of all squares is at most $2n^2$ (since color 1 increase at most 2) but it is at least $2n^2\Rightarrow $ all the squares have two red edges,and we don't color edges in the boundary so the sum of red edges of white squares equals to that of black squares...(1) by (1) and n is odd we know it is impossible

PSJL wrote: since color an edge red will increase at most the red edge of two unit square with different colors by 1 respectively You are overlooking the squares at the boundary.

I edited

For the sake of contradiction let us assume it is not possible. So any square have at least 2 red edges. If there is a red edge then tick the square connecting it. So each square is ticked at least 2 times making a total of atleast $2n^2$ ticks. So if outside edge is chosen which is connected to only one side it would not be possible as there are $n^2$ red edges and because of outside edge only one square is ticked. So all interior edges must be chosen. Now we number square starting from 1 to $n^2$. As each square is ticked 2 times so the total of nombers is $n^2(n^2+1)$ which is even. But when we chose an interior vertice sum of square connecting it is always odd. And odd number of edges are chosen. So the sum must be odd. Contradiction Hence proved

Nice and easy. Assume to the contrary. Note that we can assume that no red edge is at the boundary. Indeed, consider a red edge at the boundary and the square to which it is a side. If this square has both adjacent sides to this edge as red, remove it; else replace it with the blue neighbour. Using these operations, we can get rid of the boundary red edges without affecting our conclusion. Next we claim that no square has three red edges. Clearly, since each square has at least two red edges and and each red edge has two squares containing it, and the number of red edges is at most $n^2$, we get the result. (Essentially, counting in two ways to get $2n^2 \le |\{(E,S)| E \text {is a red edge and} E \in S\}| \le 2n^2$ so equality holds, which means that each square has exactly two red edges.) Now, consider the graph with vertices as the squares and two vertices joined by an edge if and only if they share a red edge. Each vertex has degree two, hence the graph is a disjoint union of cycles. By the structure of the board, it takes an even number of vertices to form a cycle. Adding the lengths of all these cycles gives that $n^2$ is even, a contradiction. Therefore, the stated assertion holds.

anantmudgal09,Can you explain some detail about last step why the structure of the board , it takes an even number of vertices to form a cycle?

Suppose on the contrary we can choose some $n^2$ red edges such that every square has at least $2$ edges red. Claim: No exterior edges are red and each square has exactly two red edges on its boundary. Proof: In each square we put a number indicating the number of red edges on its boundary. Initially every square has $0$ inside it. Colour the red edge one by one. At every step at most two squares have their number increased by $1$. So in the end after putting $n^2$ red edges the sum of all numbers is at most $2n^2$. If it were less than this, then some square will have at most one red edge, so equality holds and every square has number $2$ in it. Since exterior edges increase number in only one square, they are not chosen to be red. Now consider a graph whose vertices are the squares and vertices joined by edge if the corresponding squares are adjacent by red edge. In this graph, every vertex has degree 2. Hence it is disjoint union of cycles. Since number of vertices,$n^2$ is odd there is some cycle whose length is odd. But the graph is bipartite (chessboard colouring), so we have the desired contradiction.

here's an easy solution by me suppose the contrary : each square has at most two blue edges let $r$ be the number of red edges and $b$ the number of blue edges claim(1): all the boundary edges are blue and each square has two red edges and two blue edges proof: since $r \le n^2 \implies b \ge n^2+2n$ now we'll conut the number of pairs $(B,s)$ where $s$ is a unit square and $B$ is a blue edge of it since each edge is neighbor to two squares unless its on the boundary so $(B,s) \ge 4n+2(n^2-2n)=2n^2$ and since each square has at most two blue edges $2n^2 \ge (B,s)$ so the equality happens $\blacksquare$ now color the grid as in the chess so the number of black squares is $\lfloor \frac{n^2}{2} \rfloor +1$ but each of black squares the has two red edges so $r > n^2$ a contradiction and we win

Simple one, I was surprised that this was a P3. Here's my solution. I will prove the equivalent result that if at least $n^2 + 2n$ edges are coloured blue in an $n$x$n$ grid, then some cell must have three blue edges. Let $n=2k+1$ since its odd. First, define the weight of a cell to be the number of blue edges it has. Suppose FTSOC that $n^2 + 2n$ edges can be coloured blue without any cell having three edges. Then, the sum of weights of all cells is at most $2n^2$ since there are $n^2$ cells and each has at most $2$ blue edges. Also, every blue edge contributes to the weights of at most $2$ cells and contributes to one cell only if it is a boundary edge. So, the sum of contributions to weights by border edges is at most $4n$ since there are $4n$ edges on the boundary. So, the remaining edges contribute at least $(n^2 + 2n-4n)(2) = 2n^2 - 4n$ to the weights and so the sum of contributions becomes exactly $2n^2$ and so equality holds everywhere in all the inequalities. This means that all the $4n$ edges on the boundary have to be coloured blue. Now, consider the inner $(n-2)$x$(n-2)$ grid. Since equality had held, it also means that every cell must have exactly $2$ blue edges. So, this means that all the edges on the boundary of this $(n-2)$x$(n-2)$ grid must be colored blue. Similarly, we can repeat this again for a $(n-4)$x$(n-4)$ grid and so on. But at the end, we will reach a $1$x$1$ grid which needs to have all of its border edges coloured blue. But, this is impossible since that would mean that this cell has $4$ blue edges. Therefore, it is not possible to have at most $n^2$ red edges and not have a cell with at least $3$ blue edges

If every square has at least $2$ red edges, then there must be at least $2n^2$ ordered pairs of the form $(S,e)$ where $S$ is a unit square and $e$ is a red edge of $S$. However, every red edge can touch at most $2$ unit squares, so equality must hold e.g. each unit square touches $2$ red edges while each red edge touches $2$ unit squares. By checkerboard coloring this is impossible when $n$ is odd.

is this wrong??? i cannot find anything similar above consider only the $\frac{n^2+1}{2}$ squares as shown above... none of them have common edge and assume every square has $< 3$ blue edge means every square has $\geq 2$ red edge means there are total $$\ge 2(\frac{n^2+1}{2}) = n^2 + 1 > n^2$$red edges ... a contradiction

L567 wrote: Now, consider the inner $(n-2)$x$(n-2)$ grid. Since equality had held, it also means that every cell must have exactly $2$ blue edges. So, this means that all the edges on the boundary of this $(n-2)$x$(n-2)$ grid must be colored blue. Similarly, we can repeat this again for a $(n-4)$x$(n-4)$ grid and so on. But at the end, we will reach a $1$x$1$ grid which needs to have all of its border edges coloured blue. But, this is impossible since that would mean that this cell has $4$ blue edges. Why does the equality imply that $n-2$ by $n-2$ sub-grid must have its boundary be all blue?

Assume for the sake of contradiction that every unit square has at most 2 blue edges. This implies that there are at most $$4n+\frac 12(2n^2-4n) = n^2 + 2n$$blue edges (the $4n$ comes from the edges along the periphery.) Thus, it suffices to show that the equality case cannot work. In the equality case, notice that we must have a border of blue edges and also a border of blue edges around the interior $(n-2) \times (n-2)$ grid. Thus, inductively, we can reduce the problem down to a $3 \times 3$ grid, for which such a coloring is obviously impossible.

Call a configuration orz if it has at least $n^2+2n$ blue edges but each unit square has at most 2 blue edges. We will show that orz configurations do not exist. Define the value of an edge as the number of unit squares that contain it. That is, border edges have value 1 while other edges have value 2. Furthermore, define the value of a configuration as the sum of the values of its blue edges. Claim: Any orz configuration must have the entire border blue. Clearly, any orz configuration can have a value of at most $2n^2$ by summing over the unit squares. However, if we color the $n^2+2n$ smallest value edges blue (that is, $4n$ edges of value 1 and $n^2-2n$ edges of value 2), then we get a value of exactly $2n^2$. Since the value is both at least $2n^2$ and at most $2n^2$, it must be $2n^2$, and hence the entire border (consisting of value 1 edges) must be blue. Now, color the border of the grid blue. Then, label each unit square with the number of blue edges it has (so as of now, 2 for each corner cell and 1 for each non-corner edge cell, 0 for others). Now, note that coloring an additional interior edge is just adding 1 to the labels of two adjacent cells. Furthemore, we have shown that any orz configuration has a value of $2n^2$, so our "target" configuration is each cell having a label of 2. However, we will use a coloring argument to show that this is not possible. Color the cells in a checkerboard pattern, with the corners all being white. The white cells contain 4 2's, $2n-6$ 1's, and $\frac{(n-2)^2+1}{2}$ 0's. Thus, we need an additional $$n^2-2n-1$$worth of value on the white cells. On the other hand, the black cells contain $2n-2$ 1's and $\frac{(n-2)^2-1}{2}$ 0's, so we need an additional $$n^2-2n+1$$worth of value on the black cells. However, each additional edge we color blue will add one to each of two adjacent cells, one of which is white and the other is black, but the amount of extra value that we need on white and black cells are different, so achieving a orz configuration is clearly a fantasy.

Suppose not, then each cell has at least two red edges. Summing over all cells in the grid, there are at least $2n^2$ red edges but each interior red edge is counted twice. Since there are at most $n^2$ red edges, this means that there are exactly $n^2$ red edges, every red edge is in the interior, and every cell has exactly two red edges. Now use a checkerboard coloring on the grid where the corners are black. Summing over the black cells gives that there are an even number of red edges, contradiction. $\blacksquare$

First, let us color the grid like a checkerboard so that the corner squares are all shaded black. and example for $n=5$ is shown below. FTSOC, assume there is a coloring of the edges with at most $n^2$ red edges such that no square has more than two blue edges. However, notice that for each edge we have colored red, each red edge touches at most one black square, and at most once. In order to have all of the black squares have at most $2$ blue edges (or at least $2$ red edges), we would need each black square to be touched by a red edge twice. Therefore, we have that \[\text{\# of red edges}\geq 2*\text{\# of black squares}=2*\frac{n^2+1}{2}=n^2+1>n^2,\]a contradiction. Therefore at least one square (in particular, at least one black square) must have at least $3$ blue edges, finishing the problem.