Art of Problem Solving
Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

1989 AIME Problems/Problem 13: Difference between revisions

← Older editNewer edit →
tex
Line 1: Line 1:
== Problem ==
== Problem ==
Let <math>S^{}_{}</math> be a subset of <math>\{1,2,3^{}_{},\ldots,1989\}</math> such that no two members of <math>S^{}_{}</math> differ by <math>4^{}_{}</math> or <math>7^{}_{}</math>. What is the largest number of elements <math>S^{}_{}</math> can have?
Let <math>S^{}_{}</math> be a [[subset]] of <math>\{1,2,3^{}_{},\ldots,1989\}</math> such that no two members of <math>S^{}_{}</math> differ by <math>4^{}_{}</math> or <math>7^{}_{}</math>. What is the largest number of [[element]]s <math>S^{}_{}</math> can have?


== Solution ==
== Solution ==
S can have the numbers 1 through 4, but it can't have numbers 5 through 11, because no two numbers can have a difference of 4 or 7. So, 12 through 15 work, but 16 through 22 don't work. So on. Now notice that this list contains only numbers 1 through 4 mod 11. 1989 is 9 mod 11, so 1984 is 4 mod 11. We now have the sequence
<math>S</math> can have the numbers <math>1</math> through <math>4</math>, but it can't have numbers <math>5</math> through <math>11</math>, because no two numbers can have a difference of <math>4</math> or <math>7</math>. So, <math>12</math> through <math>15</math> work, but <math>16</math> through <math>22</math> don't work, and so on. Now notice that this list contains only numbers <math>1</math> through <math>4 \mod{11}</math>. <math>1989</math> is <math>9 \mod{11}</math>, so <math>1984</math> is <math>4 \mod{11}</math>. We now have the [[sequence]]


{4,15,26,...,1984}
<cmath>\{4,15,26,...,1984\}</cmath>


We add 7 to each term to get
We add 7 to each term to get


{11,22,33,...,1991}
<cmath>\{11,22,33,...,1991\}</cmath>


We divide by 11 to get
We divide by 11 to get


{1,2,3,...,181}
<cmath>\{1,2,3,...,181\}</cmath>


So there are 181 numbers 4 mod 11 in S. We multiply by 4 to account for 1, 2, and 3 mod 11:
So there are 181 numbers <math>4 \pmod{11}</math> in S. We multiply by 4 to account for <math>1, 2</math>, and <math>3</math> <math>\mod{11}</math>: <math>181*4=\boxed{724}</math>.
 
<math>181*4=\boxed{724}</math>


== See also ==
== See also ==
{{AIME box|year=1989|num-b=12|num-a=14}}
{{AIME box|year=1989|num-b=12|num-a=14}}
[[Category:Intermediate Combinatorics Problems]]
[[Category:Intermediate Number Theory Problems]]

Revision as of 13:10, 25 November 2007

Problem

Let $S^{}_{}$ be a subset of $\{1,2,3^{}_{},\ldots,1989\}$ such that no two members of $S^{}_{}$ differ by $4^{}_{}$ or $7^{}_{}$. What is the largest number of elements $S^{}_{}$ can have?

Solution

$S$ can have the numbers $1$ through $4$, but it can't have numbers $5$ through $11$, because no two numbers can have a difference of $4$ or $7$. So, $12$ through $15$ work, but $16$ through $22$ don't work, and so on. Now notice that this list contains only numbers $1$ through $4 \mod{11}$. $1989$ is $9 \mod{11}$, so $1984$ is $4 \mod{11}$. We now have the sequence

\[\{4,15,26,...,1984\}\]

We add 7 to each term to get

\[\{11,22,33,...,1991\}\]

We divide by 11 to get

\[\{1,2,3,...,181\}\]

So there are 181 numbers $4 \pmod{11}$ in S. We multiply by 4 to account for $1, 2$, and $3$ $\mod{11}$: $181*4=\boxed{724}$.

See also

1989 AIME (Problems • Answer Key • Resources)
Preceded by
Problem 12 		Followed by
Problem 14
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions
Retrieved from "https://wiki.aopstest.com/wiki/index.php?title=1989_AIME_Problems/Problem_13&oldid=20231"