2020 AMC 10B Problem 19

P16-20~6 minPrint

Divisibility & Factors Basic Counting Primes Use the answer choices (mod checks, size, form) to eliminate or select Use an invariant, parity, or coloring argument

In a certain card game, a player is dealt a hand of $10$ cards from a deck of $52$ distinct cards. The number of distinct (unordered) hands that can be dealt to the player can be written as $158A00A4AA0$ . What is the digit $A$ ?

Show solution without answering

Key insight

The number of hands is divisible by 4 but not 8, and not by 3. The digit tests for 3, 4 and 8 then leave only A = 2.

Solution

The number of hands is
$N = \binom{52}{10} = \frac{52 \times 51 \times 50 \times \cdots \times 43}{10 \times 9 \times 8 \times \cdots \times 1}.$
Computing it is too slow, but we can count how many factors of $2$ and $3$ it has. Then the divisibility tests on the digits $158A00A4AA0$ will pin down $A$ .

Factors of $3$ . On top, the multiples of $3$ from $43$ to $52$ are $45 = 3 \times 3 \times 5$ , $48 = 3 \times 16$ and $51 = 3 \times 17$ : that is $2 + 1 + 1 = 4$ threes. On the bottom, $3$ , $6$ and $9 = 3 \times 3$ give $1 + 1 + 2 = 4$ threes. They cancel, so $N$ is not divisible by $3$ .
Factors of $2$ . On top: $44 = 4 \times 11$ gives $2$ , $46$ gives $1$ , $48 = 16 \times 3$ gives $4$ , $50$ gives $1$ , $52 = 4 \times 13$ gives $2$ . Total $10$ . On the bottom: $2$ gives $1$ , $4$ gives $2$ , $6$ gives $1$ , $8$ gives $3$ , $10$ gives $1$ . Total $8$ . So $10 - 8 = 2$ twos are left: $N$ is divisible by $4$ but not by $8$ .
Use the test for $3$ . The digit sum is $1 + 5 + 8 + 4 + 4A = 18 + 4A$ . It must not be a multiple of $3$ . Since $18$ is a multiple of $3$ , $4A$ must not be, which rules out $A = 3$ and $A = 6$ .
Use the test for $4$ . The last two digits, $A0$ , must form a multiple of $4$ . That needs $A$ even ( $20$ and $40$ work, $70$ does not), which rules out $A = 7$ .
Use the test for $8$ . The last three digits, $AA0$ , must not form a multiple of $8$ . For $A = 4$ : $440 = 8 \times 55$ , a multiple of $8$ , so $A = 4$ is out. For $A = 2$ : $220 \div 8 = 27.5$ , not a whole number, so $A = 2$ is fine.

Only $A = 2$ is left. (In fact $\binom{52}{10} = 15{,}820{,}024{,}220$ .)

The answer is $\boxed{\textbf{(A)}\ 2}$ .

Why this works

When a number is shown with missing digits, you usually cannot compute it, but you can find which small numbers divide it. Counting the factors of $2$ and $3$ on the top and bottom of the fraction tells you exactly that. Facts like "not divisible by $3$ " and "not divisible by $8$ " are just as useful as "divisible by $4$ ", because the digit tests turn each one into a condition on $A$ .

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

The number is $N = \binom{52}{10} = \dfrac{52!}{10!\,42!}$ . Instead of computing it, test divisibility by small primes using the exponent of each prime in the factorials.

Prime 3. Exponent in $52!$ : $17 + 5 + 1 = 23$ . In $10!$ : $3 + 1 = 4$ . In $42!$ : $14 + 4 + 1 = 19$ . Net: $23 - 23 = 0$ , so $3 \nmid N$ . The digit sum of $158A00A4AA0$ is $18 + 4A$ , which must not be a multiple of $3$ : this rules out $A = 3$ and $A = 6$ .

Prime 2. Exponent in $52!$ : $26 + 13 + 6 + 3 + 1 = 49$ . In $10!$ : $5 + 2 + 1 = 8$ . In $42!$ : $21 + 10 + 5 + 2 + 1 = 39$ . Net: $49 - 47 = 2$ , so $N$ is divisible by $4$ but not by $8$ .

Divisible by $4$ : the last two digits $A0$ must form a multiple of $4$ , so $A$ is even; this rules out $7$ . Not divisible by $8$ : the last three digits $AA0$ must not be a multiple of $8$ . For $A = 4$ , $440 = 8 \cdot 55$ fails; for $A = 2$ , $220 = 8 \cdot 27.5$ is fine.

Only $A = 2$ survives (indeed $\binom{52}{10} = 15\,820\,024\,220$ ).

The answer is $\boxed{\textbf{(A)}\ 2}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 1: Integers: The Basics (§1.4, §1.5)
Introduction to Number Theory, Chapter 2: Primes and Composites
Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
Introduction to Number Theory, Chapter 5: Divisor Problems (§5.2, §5.3)