AMC 10 · 2022 · #14

Grade 6 arithmetic

Archetype Small-Domain Constrained Search

sum-free-setset-partitionextremal-constructionpattern-recognition easier-related-problempattern-recognitioncomplementary-counting ↑ Prerequisites: set-partitionsystematic-enumeration

📏 Medium solution 💡 3 insights

Problem

Suppose that $S$ is a subset of $\left\{ 1, 2, 3, \ldots , 25 \right\}$ 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.

(A)

(B)

(C)

(D)

(E)

View mode:

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

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

#9 Easier Related Problem 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.

$$S = \{3, 4, 5\} \subset \{1, \ldots, 5\}; \; \min(x+y) = 6 > 5$$

💡 Grade 3 two-step word problem: small case shows that big numbers can't add into the original set.

#5 Look for a Pattern 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.

$$S = \{13, 14, \ldots, 25\}; \;|S| = 13; \; \min(x+y) = 26 > 25$$

💡 Grade 4 multi-step: copy the pattern "start above half" so every pair sum overshoots the universe.

#1 Draw a Diagram 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$.

$$\text{if } i + (M - i) = M \in S, \text{ then at most one of } i, M - i \in S$$

💡 Grade 5 attributes-and-subgroups: every pair $(i, M-i)$ behaves like a single "choose one" slot.

#16 Change Focus / Count the Complement 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$.

$$|S| \le \lceil M / 2 \rceil \le \lceil 25 / 2 \rceil = 13$$

💡 Grade 4: pairs are an exclusive "pick one" — exactly the complement-style counting move.

#9 Easier Related Problem 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.

$$\max |S| = 13$$

💡 Grade 6: an upper bound that you can hit is the actual maximum — no daylight between the two.

#3 Eliminate Possibilities 6.EE.B.5 Step 6

Match 13 to the answer choices: that is (B).

$$13 \;\Rightarrow\; \textbf{(B)}$$

💡 Final compare against the five options — only (B) lands on 13.

[1] #9 3.OA.D.8 Warm up on $\{1, 2, 3, 4, 5\}$. Try the top half: $S = \{3, 4, 5\}$. The two sma

[2] #5 4.OA.A.3 Copy the trick to $\{1, \ldots, 25\}$. Choose $S = \{13, 14, 15, \ldots, 25\}$.

[3] #1 5.G.B.3 Now prove 14 is impossible — argue an upper bound. Let $M$ be the biggest elemen

[4] #16 4.OA.A.3 Count the pairs. Among the integers $1, 2, \ldots, M - 1$, the pairs $(i, M - i)

[5] #9 6.EE.B.5 Combine the two halves. The construction in Step 2 reaches $|S| = 13$. The bound

[6] #3 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.8 Solve 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.3 Solve 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.3 Understand 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.5 Understand 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.

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: B

Review

CCSS standards used (min grade 6)

More like this