Competition problem — Number theory

Library / /126 of 1394

Number theory Difficulty 4.8 AIME Find the answer United States

Problem:
A checkerboard is a rectangular grid of cells colored black and white such that the top-left corner is black and no two cells of the same color share an edge. Two checkerboards are distinct if and only if they have a different number of rows or columns. For example, a $20 \times 25$ checkerboard and a $25 \times 20$ checkerboard are considered distinct.

Compute the number of distinct checkerboards that have exactly 41 black cells.

Proposed by: Albert Wang

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:
Since there is a black corner on the checkerboard, the number of white squares is at most the number of black squares. So, the board either has 40 or 41 white squares. Therefore, we want to compute the number of ordered pairs $(r,c)$ with a product of 81 or 82. Since $81 = 3^{4}$ has 5 divisors and $82 = 41 \cdot 2$ has 4 divisors, there are $\boxed{9}$ checkerboards with exactly 41 black cells.

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.