Question

There is a collection of $25$ indistinguishable white chips and $25$ indistinguishable black chips. Find the number of ways to place some of these chips in a $5 \times 5$ grid such that:

• each cell contains at most one chip

• all chips in the same row and all chips in the same column have the same color, and

• any additional chip placed on the grid would violate one or more of the previous two conditions.

Answer

Solution:

In a valid placement, each nonempty row has a single color, and likewise each column. If some row were empty, choose any cell of it: a chip of the color of that cell's column (either color if the column is also empty) could legally be added, contradicting the third condition. So every row and every column is nonempty, and we may speak of its color.

A chip at a cell forces its row and column colors to agree; conversely, if a row and a column share a color but their common cell is empty, a chip of that color could be added. Hence chips occupy exactly the cells whose row color equals the column color. For every row to be nonempty, each row's color must appear among the column colors, and vice versa — the rows and the columns use the same set of colors. Any such coloring conversely yields a valid maximal placement (at most $25$ cells hold chips of each color, so the supply suffices), and distinct colorings give distinct placements.

Counting the colorings: all rows and columns white, all black, or both colors used by the rows and by the columns: $1 + 1 + (2^5 - 2)^2 = 2 + 900 = 902.$

2024 AIME II Problem 9

Solution:

Problem 9 in Other Years