coloring a $n\times n$ square grid in a specific way I recently saw a maths problem that looked fun to solve. I have a $n\times n$ square grid and I need to color the cells within the grid in such a manner that no $2\times 2$ square that is within the larger grid has 3 of its 4 cells colored(it can be 1 or 2 or sometimes 0) and when all the necessary cells are colored if you color any of the empty cells there must be a 2*2 square (within the larger grid) which has $3$ cells colored.
It is a hard problem to wrap your mind around.
Everything up untill the $5\times 5$ grid is not hard to solve. For example, there is only one solution for a $2\times2$ grid.
No $2\times2$ square within the $3\times3$ square grid has 3 cells colored and if you were to color any of the empty cells there would be at least one $2\times2$ square which has 3 cells colored.
I also have solutions for the $5\times 5$ and $6\times6$ grid. The problem is that for 6*6 there were a lot of plausible solutions so  it would take absurd amount of time to get the results by hand.
The real problem is that I need to create a proof to why for example a 4*4 grids lowest number of colored cells is 7 and that is the thing I have been struggling with. I also need to understand in what manner should I color the cells to get the results I need so that I can get the results on my own as n gets larger.
Maybe some of you could recommend some scientific papers that adress this kind of problem or help me figure out in what way should I color the cells.
Any help would be much appreciated. Tnx :)
 A: This problem is similar to Martin Gardner's no-three-in-a-line problem, which is discussed in OEIS entry A219760.
A similar integer linear programming formulation yields the following min and max values for the number of colored cells in your problem if you require 1 or 2 colored cells in each 2x2 square:
 n min max
 2   2   2 
 3   3   6 
 4   7   8 
 5   9  15 
 6  13  18 
 7  17  28 
 8  22  32 
 9  28  45 
10  35  50 
11  41  66 

Edit: here are the min and max values for the number of colored cells in your problem if you require 0, 1, or 2 colored cells in each 2x2 square:
 n min max
 2   2   2
 3   3   6
 4   7   8
 5   9  15
 6  12  18
 7  17  28
 8  22  32
 9  27  45
10  34  50
11  41  66

I used an integer linear programming formulation that is identical to the one in the linked OEIS entry if you change SQUARES[k] to $\text{CELLS}_k$, the set of cells that appear in 2x2 square $k$ and LINES[i,j] to $\text{SQUARES}_{i,j}$, the set of 2x2 squares that contain cell $(i,j)$.  Explicitly, the problem is to minimize or maximize $\sum_{i,j} x_{i,j}$ subject to:
\begin{align}
2 y_k \le \sum_{(i,j) \in \text{CELLS}_k} x_{i,j} &\le 2 &&\text{for all 2x2 squares $k$} \\
x_{i,j} + \sum_{k \in \text{SQUARES}_{i,j}} y_k &\ge 1 &&\text{for all $(i,j)$} \\
x_{i,j} &\in \{0,1\} &&\text{for all $(i,j)$} \\
y_k &\in \{0,1\} &&\text{for all $k$}
\end{align}
Edit: By request, here is the SAS code I used for the LP relaxation of the minimization problem:
proc optmodel printlevel=0;
   num n;
   set ROWS = 1..n;
   set COLS = ROWS;
   set CELLS = ROWS cross COLS;
   set SQUARES = {i in ROWS diff {n}, j in COLS diff {n}};
   set CELLS_square {<i,j> in SQUARES} = i..i+1 cross j..j+1;

   var X {CELLS} binary;
   min MinNumColored = sum {<i,j> in CELLS} X[i,j];

   /* if X[i,j] = 0, then some square containing <i,j> has exactly 2 colored */
   var Y {SQUARES} binary;
   con TwoByTwoGE {<i,j> in SQUARES}:
      sum {<ii,jj> in CELLS_square[i,j]} X[ii,jj] >= 2 * Y[i,j];
   con TwoByTwoLE {<i,j> in SQUARES}:
      sum {<ii,jj> in CELLS_square[i,j]} X[ii,jj] <= 2;
   con YCon {<i,j> in CELLS}:
      X[i,j] + sum {<ii,jj> in SQUARES: <i,j> in CELLS_square[ii,jj]} Y[ii,jj] >= 1;

   set NSET = 2..11;
   num opt {NSET};
   do n = NSET;
      solve with lp relaxint;
      print X;
      opt[n] = _OBJ_;
   end;
   print opt;
quit;

A: Here is a sketch of a proof that a $4\times 4$ square must have at least seven coloured squares. You should be able to fill in the gaps.
Let's call the $1\times 1$ squares cells, and divide the $4\times 4$ square into four disjoint $2\times 2$ blocks. Number columns $1$ to $4$ left to right, and rows $1$ to $4$ from top to bottom.
Each block can contain at most two coloured cells. If it contains no coloured cells then the corner cell of the block [the one at position $1,1$ or $1,4$ or $4,1$ or $4,4$] can be coloured contrary to the restriction. If the block contains just one coloured cell, and this is not a corner cell, then the corner cell can likewise be coloured.
Suppose the top left block contains just one coloured cell, it must be the corner cell $1,1$. Then for $2,1$ to leave a $2\times 2$ square with three coloured squares, $3,1$ and $3,2$ must be coloured, and similarly $1,3$ and $2,3$. That deals with three of the four blocks.
If the bottom right block contains two coloured cells we are up to $7$ and if just one it must be $4,4$ which forces $2,4$ and $4,2$ in violation of the rules (and taking the total to $8$ anyway).
So the minimum number for $4\times 4$ is seven.
A: Here's a good start on a proof that $n \lceil n/2 \rceil$ is optimal for the linear programming relaxation of the maximization problem, even without the $y$ variables and associated constraints.  The problem is to maximize $\sum_{i,j} x_{i,j}$ subject to:
\begin{align}
\sum_{(i,j) \in \text{CELLS}_k} x_{i,j} &\le 2 &&\text{for all $k$, with dual variable $\pi_k \ge 0$}\\
-x_{i,j} &\le 0 &&\text{for all $(i,j)$, with dual variable $\alpha_{i,j} \ge 0$} \\
x_{i,j} &\le 1 &&\text{for all $(i,j)$, with dual variable $\beta_{i,j} \ge 0$}
\end{align}
For even $n$, an optimal primal solution is $x_{i,j}=1/2$ for all $(i,j)$, with objective value $n^2/2$.  An optimal dual solution is $\pi_k = 1/2$ for each 2x2 square $k$ whose top-left corner has odd coordinates, $\pi_k=0$ otherwise, and  $\alpha_{i,j}=\beta_{i,j}=0$ for all $(i,j)$.  Multiplying both sides of the constraints by these dual multipliers and adding up both sides yields $\sum_{i,j} x_{i,j} \le n^2/2$, so this primal-dual pair provides a certificate of optimality.
For odd $n$, an optimal primal solution is
$$x_{i,j} = 
\begin{cases}
1 & \text{if $i$ and $j$ are both odd}, \\
0 & \text{if $i$ and $j$ are both even}, \\
1/2 & \text{otherwise},
\end{cases}$$
with objective value $n \lceil n/2 \rceil$.  An optimal dual solution is $\alpha_{i,j}=1/\lfloor n/2 \rfloor$ if $i$ and $j$ are both even, $\beta_{i,j}=1/\lceil n/2 \rceil$ if $i$ and $j$ are both odd, and a more complicated formula for $\pi_k$.  For $n=3$, take $\pi_k = 1/2$ for all $k$. For $n=5$, take
$$\pi_k=
\begin{cases}
2/3 &\text{if the top-left corner of square $k$ has coordinates in $\{1,4\}$},\\
1/6 &\text{if the top-left corner of square $k$ has coordinates in $\{2,3\}$},\\
1/3 &\text{otherwise}.
\end{cases}$$
Again, these dual multipliers yield $\sum_{i,j} x_{i,j} \le n \lceil n/2 \rceil$, so this primal-dual pair provides a certificate of optimality.
It remains to describe $\pi_k$ for larger odd $n$, but please check your understanding so far.  In particular, it is a good exercise to verify that the dual solutions provided for $n=3$ and $n=5$ do in fact show that $\sum_{i,j} x_{i,j} \le n \lceil n/2 \rceil$.
