Easy for 6.The answer is (2*n+1)*(n+1).Just mark the rows 1,2,...2*n+1.Now,example for (n+1)*(2*n+1):Let rows 1,3,5...2*n+1 be black.Now,it is easy to see that the number of black cells in 2 adjacent rows is at most 2*n+2(but iff in both rows we have n+1 cell),or the maximum is 2*n+1(This can be proven very easy,but I don't have enough time).Now,if the number in the first row is n+1,we easy get that the maximum is (n+1)*(2*n+1),if it is n,we get the maximum is (n+1)*(2*n+1)-1,if it is an arbitary integer x different from this two,it is easy to see that maximum is (n+1)*(2*n+1),so we are finished.

The answer is $(2n+1)$x$(n+1)$. So we separeted the board in sub board $2\times 2$, in L-triminos and $1\times 1$ sub board in this form, for example $n=2$ and $n=3$. In the diagonal L-triminos and $1\times 1$. It's easy see, we have $n^2$ $2\times 2$, $n$ L-triminos and $(n+1)$ sub board of $1\times 1$. We note that in each $2\times 2$ there are at most $2$ black cells, in each L-triminos there are at most $2$ black cells, and in each $1\times 1$ there is at most $1$ black cell. In total, there are $n^2\times 2+n\times 2+(n+1)\times 1= 2n^2+3n+1=(2n+1)(n+1)$ and this is the answer. The example for all n is colored columns $1,3,5...,2n+1$

Leicich wrote: Let $Q$ be a $(2n+1) \times (2n+1)$ board. Some of its cells are colored black in such a way that every $2 \times 2$ board of $Q$ has at most $2$ black cells. Find the maximum amount of black cells that the board may have. I promise I will write/try to write solution in proper manner that is actually proper proof writing. I promise I will write/try to write solution in proper manner that is actually proper proof writing. I promise I will write/try to write solution in proper manner that is actually proper proof writing. I promise I will write/try to write solution in proper manner that is actually proper proof writing. I promise I will write/try to write solution in proper manner that is actually proper proof writing. Dolution : We first make an observation : The condition for coloring are hereditary , i.e, if a coloring of board of size $2k+1$ by $2k+1$ is called as $\mathcal{D}_1$ which satisfies all conditions of the problem, then we can remove last $2$ rows and last $2$ columns and still the condition would be satisfied. We will use this but in the opposite direction, being careful because the converse of the statement I made above doesn't hold true. We induct on $k$. Let us say that alternative row coloring has been optimal choice of coloring for some $k$, base case $3$ fails to work due to pigeon hole principle as two square cannot cover $2$ spots in every $2$ by $2$ square in the $3$ by $3$ square grid so $\boxed{6}$ is maximum for $k=3$, only way of acheiving it is the column or row coloring. Now, we can see that PHP argument also tells us that best coloring for $2$ by $k$ is $k$ by alternative row or a full column or vice versa. Now we see that if we combine $2k+1$ by $2k+1$, $2$ by $2k+1$ and $2$ by $2k+3$ rectangle together in a particular manner, we get a $2k+3$ by $2k+3$ square. Now, we know that we have combined three objects will optimal coloring. It seems that overall this huger coloring is also optimal, we'll call this coloring $\mathcal{D}_1$. Also let us call these three rectangle as $a, b, c$ respectively. Suppose there exists better coloring. Then at least one of the rectangles $a, b, c$ of this new coloring has more marked squares than the rectangle in the coloring we claimed to be optimal. This contradicts the fact that $a, b, c$ were given optimal coloring. Now I'll leave it to the reader in what way should we color these rectangles and then arrange them.

thats too easy by partitioning the check board you can easily understand the answer is $(n+1)(2n+1)$

No I intentionally left the trivial part so the reader just doesn't read and leave

We claim that the answer is $(2n+1)(n+1).$ To prove this, we induct on $n{}.$ The base case is trivial; assume that this bound holds for $n{}.$ We will prove that it also holds for $n+1.{}$ Let the cell on the $i$-th row and $j$-th column be $C_{i,j}$ and split the board into an L-shaped piece $\mathcal{L}$ and a $(2n+1)\times (2n+1)$ board $\mathcal{B}$ with the upper-left vertex $C_{1,3}.$ By the induction hypothesis we can have at most $(2n+1)(n+1)$ black squares in $\mathcal{B}.$ Hence, there are at least $4n+6$ black squares in $\mathcal{L}.$ Now, divide $\mathcal{L}$ into several ($2n+1$, more specifically) $2\times 2$ squares and the four unit squares $C_{2n+3,1},C_{2n+3,2}$ and $C_{2n+2,3},C_{2n+3,3}.$ Observe that any $2\times 2$ square has at most 2 black squares and $\mathcal{L}$ has at least $4n+6$ black squares, hence $C_{2n+3,1},C_{2n+3,2}$ and $C_{2n+2,3},C_{2n+3,3}$ must all be black. However, by a symmetrical decomposition of $\mathcal{L}$ we can deduce that $C_{2n+3,1},C_{2n+2,1}$ and $C_{2n+1,1},C_{2n+1,2}$ must all be black as well. Hence, the lower-left $2\times 2$ square must have at least $3$ black squares in it, which is a contradiction. Therefore, our bound holds for an $2n+3\times 2n+3$ board as well. Equality can be obtained by a chessboard coloring, where $C_{1,1}$ is black.

First we will show that amongst $2$ consecutive rows of the board, there are atmost $2n+1$ black cells. Let's forget the rest of the board for now, and we will show that if we only consider the problem's constraints in the subgrid here, it will still give the required result. Consider each location such that the black square is in the bottom and there is a white cell just to the top of it. Note that we can shift such black cells up without affecting the problem's property.This gives if some cell of the bottom row is black, then the one above it is black as well. So, if there are $2n+2$ cells colored black, (after this movement, the numner of black cells hasn't changed so don't panic) then the first row must be completely black and at least one of the bottom row cells should be black as well. But then if we consider a $2 \times 2$ board containing that bottom cell, it has $3$ black cells, a contradiction. Thus there are at most $2n +1$ cells as such. Now, divide the original board into $n$ such $2 \times 2n+1$ boards and one $1 \times 2n+1$ array. This immediately gives that there are at most $(n+1)(2n+1)$ black cells in the entire board. And this is achievable, for if we number the rows of the board from $1$ to $2n+1$ and color the odd rows black completely then the board satisfies our conditions and has $(n+1)(2n+1)$ colored cells. Thus the answer to the problem is $(n+1)(2n+1)$.

I present two solutions out of which one might be completely wrong, so kindly let me know if it is Solution 1: Induction I claim that the maximum number of black cells is $(n+1)(2n+1)$. The base case clearly holds true. Now let the assertion hold true for all $n \in \{1,2, \dots, k-1\}$. Partition the $(2k+1) \times (2k+1)$ board into four rectangles, of dimensions $(2k-1) \times (2k-1), 2 \times (2k-1), 2 \times (2k-1), 2 \times 2$ respectively. First note that any $2 \times (2x+1)$ box has a maximum of $2x+2$ black cells in it (divide it into a box of dimension $2 \times 2k$ which cannot have more than $2k$ black cells) with equality when each of the two columns have $x+1$ black cells and each black cell in one column has an adjacent black cell in the other column. Now if the $2 \times 2$ box has $0$ black cells, we get the maximum as $k(2k-1)+2(2k)=2k^2+3k$ which is less than $(k+1)(2k+1)$. If the $2 \times 2$ box has $1$ black cell, the maximum is $2k^2+3k+1$. If it has $2$ black cells, however, one $2 \times (2k-1)$ box is forced to have $2k-1$ black cells (equality can’t ever hold) so the maximum remains the same and we are done. Solution 2 : FTSOC assume that some $(2n+1) \times (2n+1)$ box can have at least $(2n+1)(n+1)+1$ black cells while following the given condition. This means that some column has at least $n+2$ black cells. Call such a column good, else call it bad. We make two cases. In the first case, the leftmost column isn’t good. Since we know a good column exists, choose the leftmost one, and pair it with the column on its left, and delete it. So we are left with $(n+1)(2n+1)-(2n+1)+1$ cells and $2n-1$ columns. In general, it is easy to prove that $(n+1)(2n+1)+1-(2n+1)k > (n+1)(2n+1-2k)$ which means that every time we can pair a good column with its adjacent bad column, we can delete them and by php we can always find another good column. Back to the main problem, we just keep choosing the leftmost good column at each step and we can always pair it with an adjacent bad column (in this case just pair every good column with its leftmost column) because no two good columns can be adjacent. Therefore at least $n$ of the box’s columns should be good, and at maximum it can have $(2n+1)n+(2n+1)=(2n+1)(n+1)$ black cells, contradiction. In the second case, the leftmost column is good. As usual, keep choosing the leftmost good column and pair it with its adjacent left column if possible (it might not be if it’s already deleted ; in that case choose the right one). If at some point we are able to pair it with its left column, do that and keep pairing the good columns after that with their left ones. This means we can always pair a good column with an adjacent bad column, so we are done by the same reasoning as in the above case. However if it’s not possible, it would mean that column $1,3, \dots,(2n-1)$ are good which means that the maximum is $n(2n+1)+(2n+1)=(2n+1)(n+1)$, contradiction. P.S. sorry for the bad writeup :p

Forgot to post this lol The answer is $(n+1)(2n+1)$, which can be achieved by coloring every other row black, starting with the uppermost (so we get $n+1$ colored rows). To show that this is an upper bound I will use induction, with the base case of $n=0$ being clear. Call the shape formed by removing the top-right $2n-1\times 2n-1$ board from a $2n+1\times 2n+1$ board a "$2n+1$ L". By inductive hypothesis it suffices to show that at most $4n+1$ cells in a $2n+1$ L are black. We again use induction for this. For the base case of $n=1$, divide the $3$ L as such: [asy][asy] draw((0,3)--(2,3)); draw((0,2)--(3,2)); draw((0,1)--(3,1)); draw((0,0)--(3,0)); draw((0,3)--(0,0)); draw((1,3)--(1,0)); draw((2,3)--(2,0)); draw((3,2)--(3,0)); draw((0.1,2.9)--(1.9,2.9)--(1.9,1.1)--(0.1,1.1)--cycle, red); draw((2.9,0.1)--(2.9,1.9)--(1.1,1.9)--(1.1,0.1)--cycle, blue); draw((0.1,0.1)--(0.9,0.1)--(0.9,0.9)--(0.1,0.9)--cycle, green); [/asy][/asy] Then, $$\text{\# of black cells} \leq \text{\# of black cells in green} + \text{\# of black cells in red} + \text{\# of black cells in blue} \leq 1+2+2=5,$$as desired. Now, a $2n+1$ L is simply a $2n-1$ L with two $2 \times 2$ squares added to both "ends" of the L, which increases the number of black cells by at most $4$. Therefore, by inductive hypothesis there are at most $4n+1$ black cells in a $2n+1$ L, so we're done. $\blacksquare$ Remark: If at first you can't induct, try, try again

Here's an odd solution. The answer is $(2n+1)(n+1)$, where equality holds when we color all the odd-indexed rows black. Label each black square with $1$ and white square with $-1$. For double counting reasons, it suffices to show that we can have at most $4$ corner black squares and $6n-4$ edge black squares. Actually, we will show the stronger conclusion that we can have at most $6n$ black squares along the outer periphery. Assume for the sake of contradiction that $6n$ is not optimal. Divide the $(2n+1) \times (2n+1)$ square into $n-1$ layers in succession wrapped around one center square, and define the value of each layer to be the sum of the values of it squares, counted by multiplicity according to how many $2 \times 2$ squares with one edge along the edge of this layer the square belongs to. This means that the value of the outer periphery of squares is greater than $6n \cdot 2 - 4 - 2\cdot 4n = 8n-4$. Claim. The absolute value of the value of each successive layer comprised of the outer periphery of the square contained within the previous layer decreases by at most $8$ each layer. Proof. The layer of $2 \times 2$ squares that are formed by squares within the two layers must have values summing to zero. On the other hand, this value equals $$0 = \text{Value} = \text{Value of outer layer} \ +\ \text{Value of inner layer} \ -\ 2\ \cdot \ \text{Value of four corner squares}.$$As the value of the four corner squares is at most $\pm 4$, this implies the result. $\blacksquare$ This means that the value of the final layer has absolute value at least $5$. However, using the previous equality again, this implies that the value of the center square has absolute value greater than $1$ (as it is counted in four of the $2 \times 2$ squares), contradiction.

Notice each connected component is a stick, you can extend sticks on the edge of the board, and if there is no stick on the edge you can push one to it. Now you get a stick along one edge of the board. Delete the last 2 rows and repeat.

Solution from Twitch Solves ISL: The answer is $(n+1)(2n+1)$ achieved by coloring all the odd numbered rows. We proceed by induction on $n$ with the base case $n=0$ being clear. For the other direction, we are going to decompose our $(2n+1)\times(2n+1)$ board into a $2 \times 2$ square, two $2 \times (2n-1)$ strips, and a $(2n-1) \times (2n-1)$ square, as shown below. [asy][asy] size(6cm); filldraw(box( (0,0), (2,7) ), palegreen, blue+1); filldraw(box( (2,7), (9,9) ), palegreen, blue+1); filldraw(box( (0,7), (2,9) ), palered, blue+1); for (int i=0; i<=9; ++i) { draw( (0,i)--(9,i), grey ); draw( (i,0)--(i,9), grey ); } filldraw(box((2,0), (9,7)), paleyellow, blue+1); label("$(2n-1) \times (2n-1)$", (5.5, 3.5), blue); [/asy][/asy] To get the bound, we observe that: The red $2 \times 2$ square has at most two black cells. The western green rectangle has at most $2n$ black cells, with equality if and only if the rows of length $2$ are shaded alternating black. The same is true for the northern green rectangle. However, equality cannot simultaneously occur: if the two green rectangles both have $2n$ black cells, then the red $2 \times 2$ square has at most one black cell (at the northwestern corner). Hence, outside the yellow square, there are at most $(2n + 2n + 2) - 1 = 4n+1$ black squares. Now, induction gives a bound of \[ \underbrace{n \cdot (2n-1)}_{\text{by IH}} + \underbrace{(4n+1)}_{\text{green/red}} = (n+1)(2n+1). \]

The answer is $\boxed{(n+1)(2n+1)}$, achieved by coloring in every other column. Now, we will show that this is true by induction. The base case $n=0$ is vacuous so we move on to the inductive step. Suppose the inductive hypothesis is true for $n=k-1$. This is equivalent to a $(2k-1) \times (2k-1)$ square having at most $k(2k-1)$ black cells. Notice that a $(2k+1) \times (2k+1)$ square can be dissected into a $(2k-1) \times (2k-1)$ square, two $2 \times (2k-1)$ rectangles, and a $2 \times 2$ square. WLOG let the $(2k-1) \times (2k-1)$ square be in the bottom-left corner. By the induction hypothesis, the $(2k-1) \times (2k-1)$ contains at most $k(2k-1)$ squares, and we can easily find that the rectangles contain at most $2k$ squares each with a similar tiling configuration. Then, the $2 \times 2$ square contains at most $2$ squares. However, if both equality cases hold for the rectangles, only the top-left square of the $2 \times 2$ square can be colored in, and it is clear that this is optimal. Hence, the number of squares for a $(2k+1) \times (2k+1)$ square is \[k(2k-1)+2k+2k+1 = (k+1)(2k+1),\] completing the induction.

We claim the answer is $\boxed{(2n+1)(n+1)}$, which can be constructed by alternating shading each row. Induct on $n$, with trivial base case $n=0$. Note that a square with side $2n+3$ can be split into a square with side $2n+1$ (which our inductive hypothesis tells us has at most $(2n+1)(n+1)$ black squares), along with a square of side length 2 (which by definition has at most 2) and two rectangles with dimensions $(2n+1) \times 2$. These rectangles can be further divided into $n$ squares of side length 2 and a $2 \times 1$ rectangle, so they have a maximum of $2n+2$ black squares with equality only when we have alternating $2 \times 1$ black columns. However, equality cannot hold using the maximum for each of the $2 \times 2$ square and $(2n+1) \times 2$ rectangle, so the next best we can do is $(2n+2) + (2n+2) + 2 - 1 = 4n+5$, from which adding to $(2n+1)(n+1)$ indeed gives us an upper bound of $(2n+3)(n+2)$, which we've shown to be achieveable. $\blacksquare$

Nuked with sharpness principle The answer is $(n + 1)(2n + 1)$. For construction, color the leftmost column black and alternate black/white columns throughout. To prove the bound we induct for $n \ge 0$. For the base case, it is clearly $1$ which our bound equals. For the inductive step, assume it is true for $n = k - 1$ for some $k \ge 1$. Note that the bottom-left $(2k - 1) \times (2k - 1)$ subgrid contains at most $k(2k - 1)$ black cells by our inductive hypothesis. The rest of the grid can be partitioned into $2k - 2$ copies of a $2 \times 2$ grid which have at most $4k - 4$ black cells, and a $3 \times 3$ grid missing a corner, which can be easily shown to have at most $5$ black cells. Adding our bounds the total number of black cells is at most $$k(2k - 1) + 4k - 4 + 5 = 2k^2 + 3k + 1 = (k + 1)(2k + 1)$$as desired.

We claim that the maximum is $(2n+1)(n+1),$ which is attainable when the rows are filled/not filled in an alternating pattern, with the top row being filled. Now, for the bound, we proceed with induction on $n.$ The base case, $n=0,$ is trivial so assume that our proposition holds for some integer $n=k \geq 0.$ Then consider a $(2k+3) \times (2k+3)$ board. From the inductive hypothesis, the top left $(2k+1) \times (2k+1)$ board has at most $2k^2+3k+1$ black squares. Then, the rest of the board can be partitioned into a heart-shaped tile with $8$ squares, and two $2 \times 2k$ rectangles. The rectangles each can be separated into $k$ $(2 \times 2)$ squares, each having at most $2$ black cells, therefore the two rectangles combined contribute at most $4k$ black squares. Finally, for the heart-shape, it is easy to see that we can put at most $5$ black squares. Otherwise, if we have at least $6,$ we can bash all cases to see that they don't work. (It's not too many anyways) Therefore, we have at most $$2k^2+3k+1+4k+5=2k^2+7k+6=(2k+3)(k+2),$$so the bound holds for $n=k+1.$

The answer is $\boxed{2n^2+3n+1}$, achieved by alternating rows black with the top row black. We proceed using induction with the base case obvious to show. Now, consider a $2n+1$ grid. Take out a $2n-1$ grid from the bottom right corner to get a "L" shape remaining. We need to show that this shape has at most $2n^2+3n+1 - (2(n-1)^2 + 3(n-1)+1) = 4n+1$ black squares. Partition it into squares as shown in the image below which is easily generalizable. We have this small tetris piece left highlighted in red. It remains to show that this tetris piece cannot be all black which is obvious by considering the square in blue which finishes.