Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

Very nice problem. The answer is $ \frac {n(n+2)}{4}$. For the optimal marking: Consider chessboard colouring. We must mark $ \frac {n(n+2)}{8}$ black squares, and the same number of white squares. To do this: consider the $ n$ white diagonals of the square. Leave the $ 1$-st, $ 3$-rd, $ 5$-th ... $ n-1$-th diagonals all unmarked. For the $ 2$-nd, $ 4$-th ... $ n$-th diagonal, starting from the topmost square in each of the diagonal, mark the alternating squares. Do the exact same for the black diagonals. It's easy to see this marking satisfies the conditions, and that there are $ \frac {n(n+2)}{4}$ squares marked. To prove we can do no better: For each marked square, give it a value of $ 1$, and for each unmarked square, give it a value of $ 0$. Let the value of square, with coordinates $ (i,j)$ be $ a_{i,j}$. Colour the squares as shown in the following figure: consider the $ n$ by $ n$ square as collection of nested squares. Colour the outmost square, don't colour the square after that, colour the next square, and so on. See the attached pdf, for an example, when $ n=8$. For any square, if the adjacent squares are assigned values, say $ A, B, C, D$, then we know $ A+B+C+D \geq 1$ (since at least one of those squares has been marked). Now consider all the colored square. For each coloured square, write out the corresponding inequality (eg, for the square with coordinates $ (1,1)$, the inequality is $ a_{2,1} + a_{1,2} \geq 1$). Since there are $ \frac {n(n+2)}{2}$ colored squares, we have $ \frac {n(n+2)}{2}$ such inequalities. When we add up these inequalities, on the $ RHS$ we have $ \frac {n(n+2)}{2}$. But since each square (colored or not) is adjacent to exactly $ 2$ colored squares (we can easily verify this), on the $ LHS$, for each $ (i,j)$, $ a_{i,j}$ occurs exactly twice. That means, the inequality is simply: $ 2 \sum a_{i,j} \geq \frac{n(n+2)}{2}$, so $ \sum a_{i,j} \geq \frac{n(n+2)}{4}$. But clearly, $ \sum a_{i,j}$ is just the number of marked squares, so that means we have at least $ \frac {n(n+2)}{4}$ marked squares.

epitomy01 wrote: To prove we can do no better: For each marked square, give it a value of $ 1$, and for each unmarked square, give it a value of $ 0$. Let the value of square, with coordinates $ (i,j)$ be $ a_{i,j}$. Colour the squares as shown in the following figure: consider the $ n$ by $ n$ square as collection of nested squares. Colour the outmost square, don't colour the square after that, colour the next square, and so on. See the attached pdf, for an example, when $ n=8$. For any square, if the adjacent squares are assigned values, say $ A, B, C, D$, then we know $ A+B+C+D \geq 1$ (since at least one of those squares has been marked). Now consider all the colored square. For each coloured square, write out the corresponding inequality (eg, for the square with coordinates $ (1,1)$, the inequality is $ a_{2,1} + a_{1,2} \geq 1$). Nice solution! I would just like to note that this is not the only way of summing the inequalities $a_{i-1,j}+a_{i+1,j}+a_{i,j-1}+a_{i,j+1}\ge1$ over a set $S$ of squares $(i,j)$ (assuming we use each at most once): since the corners only have two neighbors each, we need $S$ to border each square on the board exactly $k$ times, where $k\in\{1,2\}$ is fixed. For $k=2$, we find the previous post's set of "colored" squares. For $k=1$, on the other hand, this is clearly equivalent to marking $n(n+2)/4$ squares satisfying the original problem conditions, with the additional caveat that every cell has exactly one marked neighbor. But this strengthening is valid, as the previous post's marking of every other square in every other diagonal (for a fixed color) illustrates. Of course, these restricted markings can also be viewed as partitions of the board into contiguous regions $R$ consisting of two adjacent marked squares $p,q$ such that the only neighbors of $p,q$ lie in $R$.

This is very beautiful problem. It is related to the fact that we can tile the plane with pieces like these: oXXo XXXX oXXo (the X represents the piece), but the solution doesn't use it. The answer is $\frac{n}{2}(\frac{n}{2}+1)$. First, note that this is in fact possible. Color the board like a chessboard. For each two consecutive squares on the main black diagonal, place a marker like this: X MX (M=marker) Repeat the process for the third-main black diagonal. And for the fifth, and so on. Do this again on the other side of the main black diagonal. It is easy to see we can cover all black squares with just $k(k+1)/2$ markers, where $k=n/2$. We do this again for the white squares, and end up using $k(k+1)$ markers. Now to prove that this is the maximum, we construct a set of $2k(k+1)$ squares, so that every marker can cover at most two of these squares. This is easy: take the squares on the edge take the squares at distance 2 from the edge take the squares at distance 4 from the edge and so on. In fact, my set of squares will look like a minisquare inside a square inside a bigger square inside etc. This set satisfies my condition. So done.

These are some really great solutions! I was just wondering, what is the motivation for making such colorings? Thank you so much for all your help!

Anyone? Thank you very much!

MathPanda1 wrote: These are some really great solutions! I was just wondering, what is the motivation for making such colorings? Thank you so much for all your help! Greeting, Coloring came to me naturally in 5-10 minutes. Proving was harder for me. Your friend, Luo Zhang

Hmm, very nice job polya36! But in particular, like the nested square coloring in epitomy01's solution, is there any motivation behind wanting to color in that manner, e.g. thought process/insights toward that coloring? Thank you so much for all your help!

See attachment for solution. The marked cells go out in a spiral from the center. So $\dfrac {n^2} 4 + \dfrac n 2$ markings are enough for an $n \times n$ board. $\dfrac {n^2} 4 + \dfrac n 2$ is also minimal, as you can see by building up the board with concentric square shells of thickness 2. Suppose $n \equiv 2\pmod 4$. In the thickness-2 shell around the $n-4 \times n-4$ board, there are $4(n-4)+12= 4n-4$ edge cells, which aren't neighbors to any cell in the $n-4 \times n-4$ board. Since at most two edge cells can be neighbors to a cell inside the square, at least $2n-2$ more markings are needed for the $n \times n$ board. 2 markings are needed for a $2 \times 2$ board. So for $n = 2 \mod 4$, at least $2 + (2\times 6 - 2) + ... + (2n-2) = \dfrac {n^2} 4 + \dfrac n 2$ markings are needed. Similarly, if $n \equiv 0\pmod 4, (2\times 4 - 2) + ... + (2n-2)= \dfrac {n^2} 4 + \dfrac n 2$ markings are needed.

Color the board in a checkerboard fashion. Clearly, it suffices to answer how many white squares need to be marked so that all black squares are next to marker, and then multiply the answer by $2$. This is because white squares are only adjacent to black squares and vice versa. We claim the final answer is $\boxed{\frac{n(n+2)}{4}}$, which means that if $k=n/2$, then the answer for the white squares is $k(k+1)/2$. We'll show this restated problem. Actually, we'll show that we need at least $k(k+1)/2$ white squares marked to cover all the black squares, and that we actually can cover all the white squares by marking $k(k+1)/2$ black squares (this is equivalent because of color symmetry). I know this is a bit confusing, but you'll see why I chose it this way soon. First, we'll show that we need at least $k(k+1)/2$ white squares to be marked to cover all the black squares. To do this, color all black diagonals (marked in orange) alternately, and color the odd numbered black diagonals blue, and the even numbered black diagonals red. See the diagram below for more details. [asy][asy] int m=13,n=13; for(int i = 0; i < m; ++i) { for(int j = 0; j < n; ++j) { if(i<n-1 && j>0 &&(i+j)%4==1 && max(n-1-i,j)%2==0)dot((i+1/2,j-1/2),red); if(i<n-1 && j>0 &&(i+j)%4==3 && max(n-1-i,j)%2==0)dot((i+1/2,j-1/2),blue); if(i < m-1) draw((i, j)--(i + 1, j)); if(j < n-1)draw((i, j)--(i, j + 1)); //if(i<m-1 && j>0) draw((i,j)--(i+1,j-1)); } } for(int k=0 ; k<n ; ++k) { if(k%2==0) continue; draw((k,0)--(0,k),orange+0.5); draw((n-1,k)--(k,n-1),orange+0.5); } [/asy][/asy] Note that there are $1+2+\cdots+k$ red dots and $1+2+\cdots+k$ blue dots, so a total of $k(k+1)$ dots. Furthermore, any white square is adjacent two at most two dots, so we need at least $k(k+1)/2$ white squares to be marked. Now, mark all the red squares (note that these are black), and then we see that all the white squares are covered. So we've shown that we need to mark at least $k(k+1)/2$ white squares to cover all the black squares, so we need at least $k(k+1)$ squares marked to cover all squares. We've also shown that we can mark $k(k+1)/2$ black squares to cover all the white squares, so we can mark $k(k+1)$ squares to cover all squares. $\blacksquare$

Proof without words:

Eyed wrote: Proof without words: nice

Color the board in rings using the following method: color every cell neighboring the edge of the board white, then every uncolored cell neighboring any existing white cell black, then every uncolored cell neighboring any existing black cell white, and so on, making a grid that looks like this: \begin{align*} 1~~1~~1~~1~~1~~1~~1~~1\\ 1~~0~~0~~0~~0~~0~~0~~1\\ 1~~0~~1~~1~~1~~1~~0~~1\\ 1~~0~~1~~0~~0~~1~~0~~1\\ 1~~0~~1~~0~~0~~1~~0~~1\\ 1~~0~~1~~1~~1~~1~~0~~1\\ 1~~0~~0~~0~~0~~0~~0~~1\\ 1~~1~~1~~1~~1~~1~~1~~1 \end{align*}Then every single cell borders four other cells, and it is easy to see that it borders exactly two white cells. There are $4(x-1)$ cells in a ring of size $x$, so the number of white cells in an $n\times n$ grid with $n=4k$ is \[4(4k-1+4k-5+\dots + 3)=8k^2+4k\]Thus, the number of marked cells is at least $4k^2+2k$ Similarly, if $n=4k+2$ then \[4(4k+1+4k-3+\dots + 1)=8k^2+12k+4\]so the number of marked cells is at least $4k^2+6k+2.$ As a construction, in each white ring, alternately color two and skip two, starting at the top left corner each time and going clockwise. \begin{align*} \textbf{1}~~\textbf{1}~~1~~1~~\textbf{1}~~\textbf{1}~~1~~1 & \\ 1~~0~~0~~0~~0~~0~~0~~\textbf{1} & ~~| ~~\textbf{1}~~\textbf{1}~~1~~1~~\textbf{1}~~\textbf{1}\\ 1~~0~~\textbf{1}~~\textbf{1}~~1~~1~~0~~\textbf{1} & ~~| ~~1~~0~~0~~0~~0~~1\\ \textbf{1}~~0~~1~~0~~0~~\textbf{1}~~0~~1 & ~~| ~~1~~0~~\textbf{1}~~\textbf{1}~~0~~1\\ \textbf{1}~~0~~1~~0~~0~~\textbf{1}~~0~~1 & ~~| ~~\textbf{1}~~0~~1~~1~~0~~\textbf{1}\\ 1~~0~~\textbf{1}~~\textbf{1}~~1~~1~~0~~\textbf{1} &~~ | ~~\textbf{1}~~0~~0~~0~~0~~\textbf{1}\\ 1~~0~~0~~0~~0~~0~~0~~\textbf{1} & ~~| ~~1~~1~~\textbf{1}~~\textbf{1}~~1~~1\\ \textbf{1}~~\textbf{1}~~1~~1~~\textbf{1}~~\textbf{1}~~1~~1 & \end{align*} MathPanda1 wrote: These are some really great solutions! I was just wondering, what is the motivation for making such colorings? Thank you so much for all your help! Experimentation. A lot of it. In fact, the first coloring I experimented with is actually not the best I could do: it was rings centered at a vertex of the grid. However, it did show that both straight lines and $90^\circ$ turns were good.

We claim the answer $\frac n2\left( \frac n2 +1\right) .$ Highlight the spiral-like path of cells, as on the picture (case $n=10$). We alternately color pairs of consecutive cells of path in red and blue (the last blue cell may be single). [asy][asy] unitsize(16); fill((0,0)--(1,0)--(1,9)--(9,9)--(9,1)--(3,1)--(3,7)--(7,7)--(7,3)--(5,3)--(5,5)--(6,5)--(6,6)--(4,6)--(4,2)--(8,2)--(8,8)--(2,8)--(2,0)--(10,0)--(10,10)--(0,10)--cycle, blue); fill((4,5)--(6,5)--(6,6)--(4,6)--cycle, red); fill((4,2)--(6,2)--(6,3)--(4,3)--cycle, red); fill((7,3)--(8,3)--(8,5)--(7,5)--cycle, red); fill((6,7)--(8,7)--(8,8)--(6,8)--cycle, red); fill((2,7)--(4,7)--(4,8)--(2,8)--cycle, red); fill((2,3)--(3,3)--(3,5)--(2,5)--cycle, red); fill((2,0)--(4,0)--(4,1)--(2,1)--cycle, red); fill((6,0)--(8,0)--(8,1)--(6,1)--cycle, red); fill((9,1)--(10,1)--(10,3)--(9,3)--cycle, red); fill((9,5)--(10,5)--(10,7)--(9,7)--cycle, red); fill((8,9)--(10,9)--(10,10)--(8,10)--cycle, red); fill((4,9)--(6,9)--(6,10)--(4,10)--cycle, red); fill((0,9)--(2,9)--(2,10)--(0,10)--cycle, red); fill((0,5)--(1,5)--(1,7)--(0,7)--cycle, red); fill((0,1)--(1,1)--(1,3)--(0,3)--cycle, red); for(int i = 0; i < 11; ++i){ draw((i,0)--(i,10)); draw((0,i)--(10,i)); } draw((0,0)--(1,0)--(1,9)--(9,9)--(9,1)--(3,1)--(3,7)--(7,7)--(7,3)--(5,3)--(5,5)--(6,5)--(6,6)--(4,6)--(4,2)--(8,2)--(8,8)--(2,8)--(2,0)--(10,0)--(10,10)--(0,10)--(0,0), linewidth(2.5)); [/asy][/asy] By induction we easily see, that the number of red cells is $2\left( 1+2+\dots +\frac n2\right) =\frac n2 \left( \frac n2 +1\right) .$ Observe that no cell is neighbouring with two different red cells, so at least $\frac n2\left( \frac n2 +1\right)$ marked cells are required; any cell is neighbouring with red cell, so marking all red cells we obtain the exact construction.

Let $S$ be a set of squares such that any square has a neighbour in $S$. We have to mark all squares of $S$.Consider the chessboard coloring in $n \cdot n$ board as shown below. Consider the following diagonals(starting with bottomleft then skipping next and so on) as shown below. Squares in following different diagonals don't share a common neighbour. Now we write $V$ in the black squares($r$ be the no. of $V$ black squares) as shown below and note that any $2$ black square in which $V$ is written doesn't have a common neighbour.So the set $S$ must have atleast $r$ neighbours of $V$ black squares. Note that $r=1+2+...+\frac{n}{2}=\frac{n \cdot (n+2)}{8}$. Now note that since a white square and a black square doesn't share a common neighbour. We can reflect the considered diagonals across vertical line of symmetry of board.Now note that any $2$ $V$ squares doen't have a common neighbour. They are $2r=\frac{n \cdot (n+2)}{4}$ in number so set $S$ has atleast $\frac{n \cdot (n+2)}{4}$ neighbours of $V$ squares. The construction is also clear from above diagram.All the squares in which $V$ is written ,we take it as part of set $S$ and this satisfies the problem condition. So we are done .

The answer is $\frac{n(n+2)}{4}$. For a construction, consider the outermost "ring" of squares (which has dimensions $n \times n$), then the third-outermost "ring" (which has dimensions $(n-2) \times (n-2)$), fifth-outermost "ring", and so on. Mark squares in groups of two, keeping two cells "between" each group (walking along each ring). To prove that this is maximal, note that any marked square is adjacent to exactly two squares in the above rings. Since there are $\frac{n(n+2)}{2}$ squares in these rings, it follows that we need at least $\frac{n(n+2)}{4}$ marked squares. $\blacksquare$ Remark: Constricting the equality case motivates the proof of the bound. By the time we get to $n=8$, it more or less becomes apparent that there is some "ring" structure to these equality cases, which gives the general equality case. Furthermore, if we consider these "rings" carefully enough, the proof of the bound is not too hard to come up with. There's another solution (in #11) which uses a checkerboard coloring: I think this is somewhat natural as well, but by the time I got the equality case the idea of rings was too appealing for me to give it more consideration. Also worth noting that you can take the blue cells only in post #11 and the argument works (with each white cell being adjacent to at most $1$ blue cell). EDIT: actually these are really the same solution. If you take the blue/red cells and repeat the coloring for the white cells you get the rings in this solution lol. I still think if you're focusing on the checkerboard coloring looking at only blue cells is perhaps more motivated if you start from small cases.

ring ring ring. Ended up getting roughly the same solution as above, so here's a diagram. [asy][asy] size(10cm); int N = 8; for (int i = 0; i <= N; ++i) { draw((0,i)--(N,i)); draw((i,0)--(i,N)); } path vd = (0,0)--(0,2)--(1,2)--(1,0)--cycle; path hd = (0,0)--(0,1)--(2,1)--(2,0)--cycle; fill(vd, red+white+white); fill(shift(7,0)*vd, red+white+white); fill(shift(0,4)*vd, red+white+white); fill(shift(7,4)*vd, red+white+white); fill(shift(3,0)*hd, red+white+white); fill(shift(1,7)*hd, red+white+white); fill(shift(5,7)*hd, red+white+white); fill(shift(2,2)*vd, blue+white+white); fill(shift(5,2)*vd, blue+white+white); fill(shift(3,5)*hd, blue+white+white); draw((2,2)--(2,6)--(6,6)--(6,2)--cycle, linewidth(2)); [/asy][/asy]