We want to mark some of the nine unit squares of a $3 × 3$ grid so that none of the four $2 × 2$ squares in the grid is left completely unmarked. In how many ways can this be done?
I know we want to use the inclusion-exclusion principle. If we let $$S=\{\text{all ways to mark a } 3 × 3 \text{ grid}\}$$ $$A_1=\{\text{all the ways to mark a } 3 × 3 \text{ such that one } 2 × 2 \text{ square is unmarked}\}$$ $$A_2=\{\text{all the ways to mark a } 3 × 3 \text{ such that two } 2 × 2 \text{ squares are unmarked}\}$$ $$A_3=\{\text{all the ways to mark a } 3 × 3 \text{ such that three } 2 × 2 \text{ squares are unmarked}\}$$ $$A_4=\{\text{all the ways to mark a } 3 × 3 \text{ such that four } 2 × 2 \text{ squares are unmarked}\}$$ Then our desired number is $$|S-(A_1 \cup A_2 \cup A_3 \cup A_4)|$$ I'm pretty sure that $$|S|=\sum_{n=0}^9 \binom{9}{n}=2^9$$ because we can mark the grip with $\{0,...,9\}$ marks, and in each case we're essentially ordering $n$ marks and $9-n$ empty squares. I'm struggling a bit to figure out how to count the remaining portions of the inclusion-exclusion principle and would love some help! For instance, I think that $$|A_i|=\sum_{n=0}^5 \binom{5}{n}=2^5$$ for $1 \leq i \leq 4$ because we fix $4$ squares to be unmarked and then simply have to arrange $n$ marks and $5-n$ empty squares for $\{0,...,5\}$ marks. Using similar logic we get $$|A_i \cap A_j|=\sum_{n=0}^3 \binom{3}{n}=2^3 \qquad\text{ if the two unmarked squares share an edge}$$ $$|A_i \cap A_j|=\sum_{n=0}^2 \binom{2}{n}=2^2 \qquad\text{ if the two unmarked squares share a corner}$$ $$|A_i \cap A_j \cap A_k|=\sum_{n=0}^1 \binom{1}{n}=2$$ $$|A_i \cap A_j \cap A_k \cap A_l|=\sum_{n=0}^0 \binom{0}{0}=1$$ for $1 \leq i \ne j \ne k \ne l \leq 4$.This would mean our final answer is $$2^9-\binom{4}{1}*2^5+(4*2^3+2*2^2)-\binom{4}{3}*2 + 1=417$$
Yes, $417$ is the correct count, and inclusion-exclusion is a natural approach. You can simplify a bit by avoiding the sums of binomial coefficients and just think in terms of subsets of cells. For a given subset of $m$ cells, you can either mark or not mark each one, yielding $2^m$ choices.