AMC 10 · 2022 · #14
Grade 6 arithmeticProblem
Suppose that S is a subset of {1,2,3,…,25} such that the sum of any two (not necessarily distinct) elements of S is never an element of S. What is the maximum number of elements S may contain?
Pick an answer.
AMC 10 2022 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
Try it yourself first — the explanation is most useful after you’ve attempted it.
Toolkit + CCSS Solution
Understand
Restated: Pick a subset $S$ of $\{1, 2, 3, \ldots, 25\}$ with one rule: whenever you take two members (the same one counted twice is OK), their sum must NOT be a member of $S$. How big can $S$ be?
Givens: Universe $U = \{1, 2, 3, \ldots, 25\}$; Rule: for any $x, y \in S$ (possibly $x = y$), $x + y \notin S$; Answer choices: (A) 12, (B) 13, (C) 14, (D) 15, (E) 16
Unknowns: The maximum number of elements $|S|$
Understand
Restated: Pick a subset $S$ of $\{1, 2, 3, \ldots, 25\}$ with one rule: whenever you take two members (the same one counted twice is OK), their sum must NOT be a member of $S$. How big can $S$ be?
Givens: Universe $U = \{1, 2, 3, \ldots, 25\}$; Rule: for any $x, y \in S$ (possibly $x = y$), $x + y \notin S$; Answer choices: (A) 12, (B) 13, (C) 14, (D) 15, (E) 16
Plan
Primary tool: #9 Easier Related Problem
Secondary: #5 Look for a Pattern, #1 Draw a Diagram, #16 Change Focus / Count the Complement, #3 Eliminate Possibilities
Tool #9 (Easier Problem): shrink to $\{1, \ldots, 5\}$ first. You can take $\{3, 4, 5\}$ (3 elements) because smallest sum is $3 + 3 = 6 > 5$. That suggests the "top half" idea — picking large numbers makes every sum overshoot the universe. Tool #5 (Pattern): for $\{1, \ldots, n\}$ the top-half family $\{\lceil n/2 \rceil + 1, \ldots, n\}$ gives $\lceil n/2 \rceil$ elements; for $n = 25$ that is $\{13, \ldots, 25\}$ with 13 elements. Tool #1 (Diagram): draw a number line 1-25 and mark candidate elements; the picture shows that pairing $i$ with $25 - i$ (or with the max $M$ in $S$) blocks one of each pair from joining $S$. Tool #16 (Complement) captures that bound: the pairs $(1,24), (2,23), \ldots, (12,13)$ contribute at most 12 elements, plus the max element itself $\le 13$ total. Tool #3 (Eliminate) confirms 13 beats 14, 15, 16 in the answer list.
Execute — Answer: B
3.OA.D.8 Step 1 - Warm up on $\{1, 2, 3, 4, 5\}$.
- Try the top half: $S = \{3, 4, 5\}$.
- The two smallest members add to $3 + 3 = 6$, which is already outside the universe, so no sum can land back inside $S$.
- Three elements work cleanly.
💡 Grade 3 two-step word problem: small case shows that big numbers can't add into the original set.
4.OA.A.3 Step 2 - Copy the trick to $\{1, \ldots, 25\}$.
- Choose $S = \{13, 14, 15, \ldots, 25\}$.
- There are $25 - 13 + 1 = 13$ elements.
- The smallest possible sum is $13 + 13 = 26$, which is already past 25, so $x + y \notin S$ for every pair.
- Thirteen elements is achievable.
💡 Grade 4 multi-step: copy the pattern "start above half" so every pair sum overshoots the universe.
5.G.B.3 Step 3 - Now prove 14 is impossible — argue an upper bound.
- Let $M$ be the biggest element of $S$.
- For each pair $(i, M - i)$ with $1 \le i < M/2$, at most one of the two can be in $S$ (otherwise their sum would equal $M$, which is in $S$).
- The middle case $M / 2$ also cannot be in $S$ when $M$ is even, because $\tfrac{M}{2} + \tfrac{M}{2} = M$.
💡 Grade 5 attributes-and-subgroups: every pair $(i, M-i)$ behaves like a single "choose one" slot.
4.OA.A.3 Step 4 - Count the pairs.
- Among the integers $1, 2, \ldots, M - 1$, the pairs $(i, M - i)$ split into about $\lfloor (M - 1) / 2 \rfloor$ pairs.
- Add 1 for $M$ itself, and the size of $S$ cannot exceed $\lfloor (M-1)/2 \rfloor + 1 = \lceil M / 2 \rceil$.
- The biggest allowed value for $M$ is 25, giving $\lceil 25/2 \rceil = 13$.
💡 Grade 4: pairs are an exclusive "pick one" — exactly the complement-style counting move.
6.EE.B.5 Step 5 - Combine the two halves.
- The construction in Step 2 reaches $|S| = 13$.
- The bound in Step 4 says $|S| \le 13$.
- Therefore the maximum is exactly 13.
💡 Grade 6: an upper bound that you can hit is the actual maximum — no daylight between the two.
6.EE.B.5 Step 6 Match 13 to the answer choices: that is (B).
💡 Final compare against the five options — only (B) lands on 13.
3.OA.D.8 Warm up on $\{1, 2, 3, 4, 5\}$. Try the top half: $S = \{3, 4, 5\}$. The two sma 4.OA.A.3 Copy the trick to $\{1, \ldots, 25\}$. Choose $S = \{13, 14, 15, \ldots, 25\}$. 5.G.B.3 Now prove 14 is impossible — argue an upper bound. Let $M$ be the biggest elemen 4.OA.A.3 Count the pairs. Among the integers $1, 2, \ldots, M - 1$, the pairs $(i, M - i) 6.EE.B.5 Combine the two halves. The construction in Step 2 reaches $|S| = 13$. The bound 6.EE.B.5 Match 13 to the answer choices: that is (B). Review
Reasonableness: Try another 13-element family to double-check: the odd numbers $\{1, 3, 5, \ldots, 25\}$ count exactly 13 elements. Any two odd numbers sum to an even number, and our set contains no even numbers — so $x + y \notin S$ holds automatically. The fact that two completely different families both hit 13 elements (and the upper bound also says 13) is strong evidence the answer is right. Cross-check the count in $\{13, \ldots, 25\}$: $25 - 13 + 1 = 13$, matches.
Alternative: Tool #2 (Systematic List): try to push to 14 elements directly. The largest 14 elements would have to include some number $\le 12$. But then that number plus 13 lies inside $\{13, \ldots, 25\}$, blowing the rule. Any way you slide a 14th element in, two existing members will sum to it. This is a hands-on confirmation of the pair-bound argument.
CCSS standards used (min grade 6)
3.OA.D.8Solve two-step word problems using four operations within 100 (Warm-up on $\{1, \ldots, 5\}$: picking $\{3, 4, 5\}$ and checking the smallest sum $3+3 = 6$ exceeds 5.)4.OA.A.3Solve multi-step word problems using four operations with whole numbers (Scaling the warm-up pattern to $\{1, \ldots, 25\}$ with $\{13, \ldots, 25\}$ and counting the pair structure $1 + \lfloor (M-1)/2 \rfloor$ for the upper bound.)5.G.B.3Understand that attributes belonging to a category apply to all subcategories (Treating each pair $(i, M-i)$ as a single membership slot from which at most one element can join $S$.)6.EE.B.5Understand solving an equation or inequality as a process of finding values (Combining "$|S| \le 13$" with the achievable construction "$|S| = 13$" to lock in the maximum, then matching 13 to answer choice (B).)
⭐ This AMC 10 problem only needs Grade 6 reasoning about pair-counting and category membership you already know — start with the top-half family $\{13, \ldots, 25\}$ where every sum overshoots 25, then pair up $(i, 25-i)$ to show 13 is also the most you could ever fit.
⭐ This AMC 10 problem only needs Grade 6 reasoning about pair-counting and category membership you already know — start with the top-half family $\{13, \ldots, 25\}$ where every sum overshoots 25, then pair up $(i, 25-i)$ to show 13 is also the most you could ever fit.
More like this
Same archetype — closest grade level first.