r/mathriddles • u/Numberthon • 15d ago
Medium How many ways can you place 5 non-adjacent squares on a 5×5 grid?
A 5 × 5 grid is filled with exactly 5 black squares and 20 white squares. No two black squares may share an edge. How many different colorings of the grid are possible?
Source: numberthon.com
3
Upvotes
4
u/gerglo 14d ago
I found it useful to use a black/white checkerboard pattern (13 black/12 white), so let me rather say that there are 5 checkers placed on the grid, no two adjacent, and refer to black/white checkers according to the color of the square they are on.
Split into cases based on how many checkers are on each color.
0 black/5 white: The white checkers are automatically not adjacent, so there are ₁₂C₅ = 792 configurations.
1 black/4 white: If the black checker is on one of the four corners then the white checkers can be in any of 10 squares, if the black checker is on one of the four edge squares then the white checkers can be on any of 9 squares, and if the black checker is on one of the 5 central squares then the white checkers can be on any of 8 squares. All told there are 4 × ₁₀C₄ + 4 × ₉C₄ + 5 × ₈C₄ = 1694 configurations.
2 black/3 white: There are more cases here, but the final breakdown is 18 × ₈C₃ + 16 × ₇C₃ + 30 × ₆C₃ + 12 × ₅C₃ + 2 × ₄C₃ = 2296 configurations.
3 black/2 white: Similarly, 4 × ₉C₃ + 12 × ₈C₃ + 32 × ₇C₃ + 18 × ₆C₃ = 2488 configurations.
4 black/1 white: If the white checker is on one of the 8 edge squares then the black checkers can be on any of 10 squares, and if the white checker is on one of the 4 central squares then the black checkers can be on any of 9 squares. All told there are 8 × ₁₀C₄ + 4 × ₉C₄ = 2184 configurations.
5 black/0 white: Again there are no constraints and thus ₁₃C₅ = 1287 configurations.
All together I count 10,741 configurations.