Painting a grid of squares. Consider a $9\times9$ block of squares where each square is painted either black or white.  If each square is adjacent to at most three black squares, what is the maximal number of black squares? Here we include diagonal adjacency, so every square is adjacent to (up to) eight squares. It's at least $36$:


 A: Here is an argument that might require some polishing:
The are a maximum of $3\times 81=243$ blacks including duplicates. Counting the other way,


*

*a black at corner is counted $3$ times.

*a black on one of egdes (not the corner) is counted $5$ times.

*a black somewhere in the centre is counted $8$ times.


We would like to find the $A,B,C$ such that 
$$A+B+C=243$$
where $A$ is the number of counts of black corner square with duplicates, $B$ is the number of counts of black edge square with duplicates and $C$ is the number of counts of black centre squares with duplicates.
and maximize $$\frac{A}{3}+\frac{B}{5}+\frac{C}{8}$$
A greedy approach would suggest us to fill all corners and edges with blacks. That gives $A=12$ and $B=28\times 5=140$. This leaves us with $C=91$ and $\lfloor \frac{91}{8}\rfloor=11$.
This might give us an possible upper bound of $4+24+12=40$ black squares.
PS: $91$ not being divisible by $8$ indicates that we may have to color one or more of the corners or edges with a white to get the maximum number of black squares.
