Problem:
There is a collection of indistinguishable black chips and indistinguishable white chips. Find the number of ways to place some of these chips in unit cells of a grid so that
Solution:
First, observe that no valid grid may have an empty row because otherwise any one cell of that row could have another chip added without violating the constraints of the problem. Similarly, every column of the grid must contain at least one chip. Thus in every valid grid each row and column can be labeled white or black, depending on the color of the chips in it. Then
It can also be verified that any chip placement that satisfies the above requirements also meets the requirements of the problem. Therefore a valid grid is determined by labeling each row and column as either white or black, and then placing chips of the appropriate colors in each cell whose row and column labels agree. However, all the rows can have the same color if and only if all the columns also have that color. There are non-monochromatic choices and monochromatic choices, for a total of ways to place the chips.
The problems on this page are the property of the MAA's American Mathematics Competitions