In the 2022 AMC 10A competition, Problem #14 presents a combinatorial partitioning puzzle with an inequality condition:
Contest Problem Statement: "How many ways are there to split the integers 1 through 14 into 7 pairs so that in each pair the greater number is at least 2 times the lesser number?"
Understanding the Constraint
Each pair $(a, b)$ with $a < b$ must satisfy the inequality:
$$b \ge 2a$$
For example, $(1, 3)$ is valid because $3 \ge 2(1) = 2$. However, $(3, 4)$ is invalid because $4 < 2(3) = 6$.
Notice what happens even on a small set like $\{1, 2, 3, 4\}$:
Can we pair $(1, 2)$? If we do, the remaining numbers are $3$ and $4$, which gives pair $(3, 4)$ — invalid because $4 < 2 \times 3$.
Can we pair $(1, 4)$? The remaining numbers are $2$ and $3$, giving pair $(2, 3)$ — invalid because $3 < 2 \times 2$.
What about $(1, 3)$? The remaining numbers are $2$ and $4$, giving pair $(2, 4)$. Here $4 \ge 2 \times 2$! Valid!
Thus, for $\{1, 2, 3, 4\}$, there is exactly 1 valid pairing: $(1, 3)$ and $(2, 4)$.
Solving with Prolog's Backtracking
In traditional programming languages, generating partitions of a 14-element set without double-counting pairs requires complicated loops or recursion with index management.
In Prolog, we can express this with an elegant recursive rule:
Start with the sorted list of numbers [1, 2, ..., 14].
Take the head of the list as the first element of the pair: A (which is guaranteed to be the smallest remaining number).
Use select_item/3 to non-deterministically pick a partner B from the rest of the list such that B >= 2 * A.
Recursively pair the remaining numbers!
When the list is empty ([]), a complete valid pairing has been formed.
Because A is always chosen as the smallest available element, each unordered set of pairs is generated exactly once, avoiding any duplicates!
pairings([], []). pairings([A|Rest], A, B]|Pairs]) :- select_item(B, Rest, Remaining),% Multiplicative pairing condition: Replace ???? with A
B >= 2 * ???? ,pairings(Remaining, Pairs).
Move the mouse over a dotted box for more information.
By enforcing A as the head of the sorted list, Prolog explores the search tree without duplicate permutations and counts all 144 valid pairings in milliseconds!
Now you try.
Replace ???? with A and click Run to find all 144 valid integer pairings. Then check Example 1 to see individual pair structures, or Example 2 to see the count for smaller lists like 1..4, 1..6, and 1..8!
Type your code here:
See your results here:
The code has ???? in the pair condition \ge 2A$. Replace ???? with A and click Run to count all 144 valid partitions!
Prolog outputs:
Count = 144
This matches option (E) 144 on the 2022 AMC 10A exam.
Share your code
Show a friend, family member, or teacher what you've done!