2021 JMPSC Invitationals Problems/Problem 7

Problem

In a $3 \times 3$ grid with nine square cells, how many ways can Jacob shade in some nonzero number of cells such that each row, column, and diagonal contains at most one shaded cell? (A diagonal is a set of squares such that their centers lie on a line that makes a $45^\circ$ angle with the sides of the grid. Note that there are more than two diagonals.)

Solution

Suppose all the squares are NOT fully covered by shaded squares. We have $9$ total cases that include this. Now, the center square already covers the whole grid, so we only need to consider edge squares. Each edge square has $2$ corner square options, so $4$ lines of symmetry dictates $8$ more cases. The answer is $\boxed{17}$

~Geometry285

Solution 2

If only one square is shaded, it is guaranteed to be a valid configuration. 9 boxes so $9$ choices for this case.

If two squares are shaded, the only way this can happen is a corner and an opposing edge. 4 corners and 2 valid edges for each corner, so $8$ choices in this case.

We see that we can have no more than two squares shaded, otherwise, no valid configurations occur. Thus, the answer is $9+8=\boxed{17}$.

~BakedPotato66

See also

  1. Other 2021 JMPSC Invitationals Problems
  2. 2021 JMPSC Invitationals Answer Key
  3. All JMPSC Problems and Solutions

The problems on this page are copyrighted by the Junior Mathematicians' Problem Solving Competition. JMPSC.png

Invalid username
Login to AoPS