Maths Olympiad Prep

Library / /734 of 740

Combinatorics Difficulty 6.0 AIME, harder Prove it United States

Problem:
A weird checkerboard is a coloring of an 8×88 \times 8 grid constructed by making some (possibly none or all) of the following 14 cuts:
- the 7 vertical cuts along a gridline through the entire height of the board,
- and the 7 horizontal cuts along a gridline through the entire width of the board.

The divided rectangles are then colored black and white such that the bottom left corner of the grid is black, and no two rectangles adjacent by an edge share a color. Compute the number of weird checkerboards that have an equal amount of area colored black and white.
Figure 1

Solution

Solution:
We can focus on only the black cells of the grid, which we need 3232 of. Moreover, the number of black squares in the bottom row and leftmost column uniquely determine the total number of black squares. Suppose that there are xx black cells in the bottom row and yy black cells in the leftmost column. Then, each of the xx rows with black leftmost cell is identical to the bottom row and has yy black cells, while the remaining 8x8-x rows are inverted and have 8y8-y black cells, so the total number of black cells is

(8x)(8y)+xy=32(8-x)(8-y)+x y=32

This rearranges as

2(x4)(y4)=02(x-4)(y-4)=0

which tells us we have 3232 black cells exactly when either the bottom row or leftmost column (or both) contains 44 black cells.
The bottom-left corner is already black. There are (73)\binom{7}{3} ways to choose three more cells in the bottom row or leftmost column to be black, and 272^{7} ways to color the remaining cells in the bottom row or leftmost column with no restrictions. Hence, there are 27(73)2^{7}\binom{7}{3} ways for the bottom row to have 44 black cells, 27(73)2^{7}\binom{7}{3} ways for the leftmost column to have 44 black cells, and (73)2\binom{7}{3}^{2} ways for both to occur. The answer is

2(27)(73)(73)2=77352\left(2^{7}\right)\binom{7}{3}-\binom{7}{3}^{2}=7735

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.