Consider an $n\times n$ grid which is made up of $n^2$ unit squares and $2n(n+1)$ edges.

Question

Let $n$ be an odd natural number. We consider an $n\times n$ grid which is made up of $n^2$ unit squares and $2n(n+1)$ edges. We colour each of these edges either $\color{red}{\text{red}}$ or $\color{blue}{\text{blue}}$. If there are at most $n^2$ $\color{red}{\text{red}}$ edges, then show that there exists a unit square at least three of whose edges are $\color{blue}{\text{blue}}$.

---

If we suppose that each square has at most $2$ blue edges. Say we have on the border $a$ blue edges (so $a\leq 4n$) and in the interior we have $b$ blue edges. Then we have $$a+b=:k\geq 2n(n+1) - n^2 = n^2+2n$$ so $b\geq n^2-2n$. Now we also have $$2n^2 \geq 2b+a = b+ k\geq (n^2-2n)+(n^2+2n) = 2n^2$$ so we have equality every where so we have $4n$ blue edges on border and every square has exactly $2$ blue edges and a total number of blue edges is $n^2+2n$. That is it, I can't see a contradiction from here.

Answer 1

Actually it is easier to prove it by considering $\color{red}{red}$ edges. Since we know that there are at most $n^2$ $\color{red}{red}$ edges and there are exactly $n^2$ unit squares, we need to prove that we can't put $\color{red}{red}$ edges so that every unit square has at least two $\color{red}{red}$ edges for an odd $n$.

First, let $R$ be the number of total $\color{red}{red}$ edges when we consider each unit square seperately (by that I mean there are $4n^2$ edges in total when we consider them seperately). So we need to prove we can't put $\color{red}{red}$ edges so that $R = 2n^2$.

Now, with only one $\color{red}{red}$ edge, we can increase $R$ by at most $2$ (When that edge is a mutual edge for adjacent unit squares). So we can suppose with $n^2$ $\color{red}{red}$ edges, we can have $R = 2n^2$ and try to be left with a contradiction for an odd $n$.

Suppose, for a contradiction, that we can put the $\color{red}{red}$ edges so that no unit square has $3$ $\color{blue}{blue}$ edges. In this case, starting from corner unit squares is more clever since they have two side edges and we must not put red lines on side edges since doing that way would increase $R$ by $1$. So we have the following pattern:

Notice that this is the only pattern we can use for the corner unit square because if we put $\color{red}{red}$ edges on sides of $n \times n$ square (big one), we only increase $R$ by $1$ so $R$ will be strictly less than $2n^2$ in that case. So we put $\color{red}{red}$ edges on corner square as in the figure and we don't have any other choice for putting the other two red lines (you may try to put them differently and see what happens). Now, if $n$ was an even number, we could have put the $\color{red}{red}$ edges with $R = 2n^2$ by continuing this pattern. But we are given $n$ is odd, therefore when we continue this pattern, we will stuck at rightmost corner as shown in the figure. I have also written the reasoning in figure why it is a contradiction.

Answer 2

Suppose that there are $k$ blue edges on the border.

Consider the graph in which the vertices are the squares and there is an edge between them if and only if the squares are adjacent and the edge between them is blue.

We must prove that there cannot be $n^2+2n-k$ edges in this graph. Equivalently that the sum of degrees cannot be $2n^2+4n-2k$

We can easily show that the sum of the degreees is at most $2n^2-k$.

So we must only treat the case in which $2n^2-k\geq 2n^2+4n-2k\iff k\geq 4n$ ( so only the case in which the whole border is blue must be treated)

---

So we must only prove that in this case it is not possible to build a graph in which there are $4n-4$ vertices of degree $1$ and $n^2-4n$ vertices of degree $4$ (and the four corners which have degree $0$).

In such a graph the components are going to be $2n-2$ paths ( the endpoints of the paths are the vertices of degree $1$, which are the ones in the border) and a bunch of even-lengthed cycles.

If we color the board like a chess board then it is clear that out of the there are $2n-2$ black boxes of degree $1$ and $2n-2$ white boxes of degree $1$.

We conclude that the number of black-black paths is equal to the number of white-white paths.

We conclude that the number of black boxes contained in the paths is equal to the numbre of white boxes. The same can be said of the boxes contained in the even lengthed cycles. This is a contradiction because the number of white vertices in total is $\frac{n^2-1}{2}$ and the number of black vertices is $\frac{n^2+1}{2}-4$. (assuming the corners are black).

Answer 3

A really easy solution using Arsen's interpretation.

Suppose it is possible to to use only $n^2$ edges and make every vertex have degree $2$ (or more). Clearly no red edge is on the border and each box has exactly two red edges. Now consider the graph in which vertices are boxes and we add an edge between vertices if the boxes share a red edge.

This graph must have all of its vertices of degree $2$ and thus is a disjoint union of cycles, these cycles are even because the graph is bipartite and thus the number of total boxes cannot be odd.