Track / Stage 3 / 138 of 260 #138 of 1964

Problem 138

AMC 10/12, early questions

Combinatorics Difficulty 3.4 Prove it The 4th Japanese Junior Mathematical Olympiad · Japan

There are ten red cards, numbered $1$ , $2$ , $\ldots$ , $10$ , and ten blue cards, also numbered $1$ , $2$ , $\ldots$ , $10$ . How many ways are there to choose three from these twenty cards so that the sum of the numbers on the cards chosen is $16$ or less?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Write $1$ , $2$ , $\ldots$ , $9$ or $10$ on the back of the cards so that each card has two numbers which add up to $11$ .

Call a set of three cards good if the sum of the numbers on their faces is $16$ or less, and call it bad if the sum of the numbers on their backs is $16$ or less.

Since the sum of their faces and their backs add up to $11 \times 3 = 33$ , every set of three cards is good or bad, and none is both. Furthermore, by symmetry, there must be the same number of good and bad sets. Therefore, there are exactly $\frac{1}{2} \cdot \binom{20}{3} = 570$ ways of required choice.

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