2002 AMC 10P Problems/Problem 15

Problem

What is the smallest integer $n$ for which any subset of $\{ 1, 2, 3, \; \dots \; , 20 \}$ of size $n$ must contain two numbers that differ by 8?

$\textbf{(A)} \; 2 \quad \textbf{(B)} \; 8 \quad \textbf{(C)} \; 12 \quad \textbf{(D)} \; 13 \quad \textbf{(E)} \; 15$

Solution

There are twelve pairs $\{ 1, 9 \}$ , $\{ 2, 10 \}$ , $\{ 3, 11 \}$ , $\{ 4, 11 \}$ , $\; \dots \; \{ 12, 20 \}$ in $\{ 1, 2, 3, \; \dots \; , 20 \}$ that differ by 8. If we take $n = 12$ , it could be that we selected one element from each pair for the subset: the condition may not be fulfilled. By the Pigeonhole principle, in order to select at least one pair, it is necessary to select $\boxed{\textbf{(D) } 13}$ elements.

~green_lotus

Solution 2

Use casework to find that the answer is $\boxed{\textbf{(D) } 13}$ .

2002 AMC 10P (Problems • Answer Key • Resources)
Preceded by Problem 14	Followed by Problem 16
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.

Page

Toolbox

Search

2002 AMC 10P Problems/Problem 15

Contents

Problem

Solution

Solution 2

See Also