AMC 10 Step by Step

2022 AMC 10A Problem 14

P11-15~4 minPrint

How many ways are there to split the integers 11 through 1414 into 77 pairs such that in each pair, the greater number is at least 22 times the lesser number?

Log in to save your progress.
Show solution without answering

Key insight

Numbers 8 to 14 can never be the smaller one in a pair, so they are the seven larger numbers. Pair 7 first, then 6, 5, 4.

Solution

Step 1: which numbers can be the smaller one in a pair? If xx is the smaller number, its partner is at least 2x2x, and the partner is at most 1414. So 2x≤142x \le 14, which means x≤7x \le 7.

So 8,9,…,148, 9, \ldots, 14 are always the larger number of their pair. That is 77 numbers, and there are exactly 77 pairs, each with one larger number. So the larger numbers are exactly 88 through 1414, and the smaller numbers are exactly 11 through 77. Every pair has one number from each group.

Step 2: list the allowed partners.

Smaller numberAllowed partners
771414
6612,13,1412, 13, 14
551010 to 1414
4488 to 1414
3,2,13, 2, 188 to 1414

Step 3: match the pickiest number first. Each list contains the one above it, so every partner already taken is always in the current list, and we can simply subtract.

  • 77: 11 choice (1414).
  • 66: 33 allowed, 11 already taken: 22 choices.
  • 55: 55 allowed, 22 taken: 33 choices.
  • 44: 77 allowed, 33 taken: 44 choices.
  • 33, 22, 11: the 33 partners left can go to them in 3×2×13 \times 2 \times 1 ways.

Step 4: multiply. 1×2×3×4×3×2×1=1441 \times 2 \times 3 \times 4 \times 3 \times 2 \times 1 = 144.

The answer is (E) 144\boxed{\textbf{(E)}\ 144}.

Why this works

When items have different numbers of options, place the most restricted one first. Here the lists of allowed partners sit inside each other, so going from 77 down to 11 each step loses exactly one option per earlier pick. Every count is then a fixed number, and the multiplication principle works with no cases.

Concise solution

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

A number xx can be the smaller member of a pair only if 2x≤142x \le 14, so 8,9,…,148, 9, \dots, 14 must all be the larger members. That is seven numbers, and there are exactly seven pairs, so the larger members are precisely 88 through 1414 and the smaller members are precisely 11 through 77.

Each of 1,…,71, \dots, 7 must be matched with a number from 8,…,148, \dots, 14 at least twice as large. Match the most restricted numbers first:

  • 77: only 1414 works. 11 choice.
  • 66: 12,13,1412, 13, 14 minus the one already used. 22 choices.
  • 55: 1010 through 1414 minus two used. 33 choices.
  • 44: 88 through 1414 minus three used. 44 choices.
  • 3,2,13, 2, 1: any of the remaining three, in turn. 3⋅2⋅13 \cdot 2 \cdot 1 choices.

Total: 1⋅2⋅3⋅4⋅3⋅2⋅1=1441 \cdot 2 \cdot 3 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 144.

The answer is (E) 144\boxed{\textbf{(E)}\ 144}.

Review in the AoPS books

Similar problems

Problem © Mathematical Association of America (MAA), American Mathematics Competitions. Reproduced for non-commercial educational use. Solution and commentary are original to this site.