Count The Squares

General solution

Suppose we have an $n\times n$ grid, with the red star at position $(a,b)$ .

Consider a square of size $k\times k$ , and let the left corner of this square have coordinates $(x, y)$ . The square fits entirely on the grid if $1 \leq x \leq n-k+1;\ \ \ 1 \leq y \leq n-k+1;$ the number of squares for which this is the case is $(n-k+1)^2$ . Writing $k' = n+1-k$ , the total number of squares is then $\sum_{k=1}^n (n-k+1)^2 = \sum_{k'=1}^n (k')^2 = \tfrac16n(n+1)(2n+1).$

The square contains the red star if moreover $a-k+1 \leq x \leq a;\ \ \ b-k+1 \leq y \leq b.$ Combining the two conditions, $\text{max}(1, a-k+1) \leq x \leq \text{min}(n-k+1, a);\ \ \ \text{max}(1, b-k+1) \leq y \leq \text{min}(n-k+1, b).$ The number of squares for which this is the case is $R_k = (\text{min}(n-k+1, a) - \text{max}(1, a-k+1) + 1)\cdot (\text{min}(n-k+1, b) - \text{max}(1, b-k+1) + 1) \\ = (\text{min}(n-k-a+1, 0) + \text{min}(a,k))\cdot (\text{min}(n-k-b+1, 0) + \text{min}(b,k)).$

Without loss of generality...

The expression for the sum $\sum R_k$ will not be easy to simplify. It becomes a bit simpler if we can assume, without loss of generality, that $1 \leq b \leq a \leq \lceil\frac 12 n\rceil$ . Then $R_k = \begin{cases} k\cdot k & k \leq b \\ k\cdot b & b \leq k \leq a \\ a\cdot b & a \leq k \leq n+1-a \\ (n-k+1)\cdot b & n+1-a \leq k \leq n+1-b \\ (n-k+1)\cdot (n-k+1) & k \geq n+1-b \end{cases}$ Note that, if we write $k' = n+1-k$ etc., a symmetric picture appears: $R_k = \begin{cases} k\cdot k & k \leq b \\ k\cdot b & b \leq k \leq a \\ a\cdot b & a \leq k, k' \\ k'\cdot b & b \leq k' \leq a \\ k'\cdot k' & k' \leq b \end{cases}$ Thus the sum becomes $\sum_{k = 1}^n R_k = 2\cdot \sum_{k=1}^b k^2 + 2\cdot \sum_{k=b+1}^a k\cdot b + \sum_{k = a+1}^{n-a} a\cdot b \\ = \frac{b(b+1)(2b+1)}3 + b(a(a+1) - b(b+1)) + (n-2a)ab \\ = (n+1-a)ab - \tfrac13(b-1)b(b+1).$ This is the number of squares that contains a red star.

Applying it to the given values

$n = 8$ , $a = 4$ , and $b = 3$ . Thus there are $\tfrac16n(n+1)(2n+1) = \tfrac16\cdot 8\cdot 9\cdot 17 = 204$ squares in total, of which $(n+1-a)ab - \tfrac13(b-1)b(b+1) = 5\cdot 3\cdot 4 - \tfrac13\cdot 2\cdot 3\cdot 4 = 60 - 8 = 52$ contain a star. The answer, then, is $204 - 52 = \boxed{152}.$

Number of 1×1 squares that contains the red star = 1×1 = 1
Number of 2×2 squares that contains the red star = 2×2 = 4
Number of 3×3 squares that contains the red star = 3×3 = 9
Number of 4×4 squares that contains the red star = 3×4 = 12
Number of 5×5 squares that contains the red star = 3×4 = 12

Number of total 1×1 squares = 8×8 = 64
Number of total 2×2 squares = 7×7= 49
Number of total 3×3 squares = 6×6 = 36
Number of total 4×4 squares = 5×5 = 25
Number of total 5×5 squares = 4×4 = 16

Note:- Here we dont count any 6×6, 7×7 and 8×8 grids, because all of them would contain the red star which we dont want.

Number of 8×8 squares that does not contain the red star = 64 - 1= 63
Number of 7×7 squares that does not contain the red star = 49 - 4= 45
Number of 6×6 squares that does not contain the red star = 36 - 9= 27
Number of 5×5 squares that does not contain the red star = 25 - 12= 13
Number of 4×4 squares that does not contain the red star = 16 - 12= 4

So, total number of squares that does not contain the red star = $63 + 45 + 27 + 13 + 4\\ = \boxed{152}$