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

Difference between revisions of "1984 AIME Problems/Problem 14"

(→‎Solution)
(→‎Solution)
Line 2: Line 2:
 
What is the largest even integer that cannot be written as the sum of two odd composite numbers?
 
What is the largest even integer that cannot be written as the sum of two odd composite numbers?
  
−
== Solution ==
+
== Solution 1 ==
  
 
Take an even positive integer <math>x</math>. <math>x</math> is either <math>0 \bmod{6}</math>, <math>2 \bmod{6}</math>, or <math>4 \bmod{6}</math>. Notice that the numbers <math>9</math>, <math>15</math>, <math>21</math>, ... , and in general <math>9 + 6n</math> for nonnegative <math>n</math> are odd composites. We now have 3 cases:
 
Take an even positive integer <math>x</math>. <math>x</math> is either <math>0 \bmod{6}</math>, <math>2 \bmod{6}</math>, or <math>4 \bmod{6}</math>. Notice that the numbers <math>9</math>, <math>15</math>, <math>21</math>, ... , and in general <math>9 + 6n</math> for nonnegative <math>n</math> are odd composites. We now have 3 cases:
Line 14: Line 14:
  
 
Clearly, if <math>x \ge 44</math>, it can be expressed as a sum of 2 odd composites. However, if <math>x = 42</math>, it can also be expressed using case 1, and if <math>x = 40</math>, using case 3. <math>38</math> is the largest even integer that our cases do not cover. If we examine the possible ways of splitting <math>38</math> into two addends, we see that no pair of odd composites add to <math>38</math>. Therefore, <math>\boxed{038}</math> is the largest possible number that is not expressible as the sum of two odd composite numbers.
 
Clearly, if <math>x \ge 44</math>, it can be expressed as a sum of 2 odd composites. However, if <math>x = 42</math>, it can also be expressed using case 1, and if <math>x = 40</math>, using case 3. <math>38</math> is the largest even integer that our cases do not cover. If we examine the possible ways of splitting <math>38</math> into two addends, we see that no pair of odd composites add to <math>38</math>. Therefore, <math>\boxed{038}</math> is the largest possible number that is not expressible as the sum of two odd composite numbers.
 +
 +
== Solution 2 ==
 +
Let <math>n</math> be an integer that cannot be written as the sum of two odd composite numbers. If <math>n>33</math>, then <math>n-9,n-15,n-21,n-25,n-27,</math> and <math>n-33</math> must all be prime (or <math>n-33=1</math>, which yields <math>n=34=9+25</math> which does not work). Thus <math>n-9,n-15,n-21,n-27,</math> and <math>n-33</math> form a sexy prime quintuplet. However, only one sexy prime quintuplet exists as exactly one of those 5 numbers must be divisible by 5.This sexy prime quintuplet is <math>5,11,17,23,</math> and <math>29</math>, yielding a maximal answer of 38. Since <math>38-25=13</math>, which is prime, the answer is <math>\boxed{038}</math>.
  
 
== See also ==
 
== See also ==

Revision as of 16:38, 16 January 2016

Problem

What is the largest even integer that cannot be written as the sum of two odd composite numbers?

Solution 1

Take an even positive integer $x$. $x$ is either $0 \bmod{6}$, $2 \bmod{6}$, or $4 \bmod{6}$. Notice that the numbers $9$, $15$, $21$, ... , and in general $9 + 6n$ for nonnegative $n$ are odd composites. We now have 3 cases:

If $x \ge 18$ and is $0 \bmod{6}$, $x$ can be expressed as $9 + (9+6n)$ for some nonnegative $n$. Note that $9$ and $9+6n$ are both odd composites.

If $x\ge 44$ and is $2 \bmod{6}$, $x$ can be expressed as $35 + (9+6n)$ for some nonnegative $n$. Note that $35$ and $9+6n$ are both odd composites.

If $x\ge 34$ and is $4 \bmod{6}$, $x$ can be expressed as $25 + (9+6n)$ for some nonnegative $n$. Note that $25$ and $9+6n$ are both odd composites.


Clearly, if $x \ge 44$, it can be expressed as a sum of 2 odd composites. However, if $x = 42$, it can also be expressed using case 1, and if $x = 40$, using case 3. $38$ is the largest even integer that our cases do not cover. If we examine the possible ways of splitting $38$ into two addends, we see that no pair of odd composites add to $38$. Therefore, $\boxed{038}$ is the largest possible number that is not expressible as the sum of two odd composite numbers.

Solution 2

Let $n$ be an integer that cannot be written as the sum of two odd composite numbers. If $n>33$, then $n-9,n-15,n-21,n-25,n-27,$ and $n-33$ must all be prime (or $n-33=1$, which yields $n=34=9+25$ which does not work). Thus $n-9,n-15,n-21,n-27,$ and $n-33$ form a sexy prime quintuplet. However, only one sexy prime quintuplet exists as exactly one of those 5 numbers must be divisible by 5.This sexy prime quintuplet is $5,11,17,23,$ and $29$, yielding a maximal answer of 38. Since $38-25=13$, which is prime, the answer is $\boxed{038}$.

See also

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