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"

m (→‎Solution)
(→‎Solution 7 (casework))
 
(26 intermediate revisions by 14 users not shown)
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 ==
  
−
Let the desired integer be <math>2n</math> for some positive integer <math>n</math>. Notice that we must have <math>2n-9</math>, <math>2n-15</math>, <math>2n-21</math>, <math>2n-25</math>, ..., <math>2n-k</math> all prime for every odd composite number <math>k</math> less than <math>2n</math>. Therefore <math>n</math> must be small. Also, we find that <math>n</math> is not divisible by 3, 5, 7, and so on. Clearly, <math>n</math> must be a prime. We can just check small primes and guess that <math>n=19</math> gives us our maximum value of <math>38</math>.
+
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:
 +
 
 +
If <math>x \ge 18</math> and is <math>0 \bmod{6}</math>, <math>x</math> can be expressed as <math>9 + (9+6n)</math> for some nonnegative <math>n</math>. Note that <math>9</math> and <math>9+6n</math> are both odd composites.
 +
 
 +
If <math>x\ge 44</math> and is <math>2 \bmod{6}</math>, <math>x</math> can be expressed as <math>35 + (9+6n)</math> for some nonnegative <math>n</math>. Note that <math>35</math> and <math>9+6n</math> are both odd composites.
 +
 
 +
If <math>x\ge 34</math> and is <math>4 \bmod{6}</math>, <math>x</math> can be expressed as <math>25 + (9+6n)</math> for some nonnegative <math>n</math>. Note that <math>25</math> and <math>9+6n</math> are both odd composites.
 +
 
 +
 
 +
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 prime quintuplet. However, only one prime quintuplet exists as exactly one of those 5 numbers must be divisible by 5.This 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>.
 +
 
 +
== Solution 3 (bash) ==
 +
Let <math>2n</math> be an even integer. Using the [[Chicken McNugget Theorem]] on the two smallest odd composite integers that are relatively prime from each other, 9 and 25, show that the maximum is 191, and the maximum even integer is 190 or lower. We use the fact that sufficiently high multiples of 6, 10, 14, 22, etc. can be represented as <math>n+n</math>. We bash each case until we find one that works.
 +
 
 +
== Solution 4 (easiest) ==
 +
The easiest method is to notice that any odd number that ends in a 5 is a composite (except for 5 itself). This means that we will have 15, 25, 35, etc... no matter what. What it also means is that if we look at the end digit, if 15 plus another number will equal that number, then any number that has that same end digit can be added by that same number plus a version of 15, 25, 35...
 +
 
 +
For example, let's say we assume our end digit of the number is 4. If we have 5 as one of our end digits, then 9 must be the end digit of the other number. If we go down our list of numbers that end with a 9 and is composite, we will stumble upon the number 9 itself. That means that the number 15+9 is able to be written in a composite form, but also anything that ends with a 4 and is above 15+9(ex. 34, 44 . . .). Hence the largest number that ends with a 4 that satisfies the conditions is 14.
 +
 
 +
If you list out all the numbers(15, 27, 9, 21, 33), you will notice that 33 is the largest number where the last digit is not repeated (13 and 23 are not composite). That means that 33+15 and any number greater that ends with a 3 is bad(ex. 58, 68. . .), so the largest number that satisfies the conditions is the largest number that ends with a 8 and is below 48. That number would be <math>\boxed{38}</math>
 +
 
 +
== Solution 5 ==
 +
Claim: The answer is <math>\boxed{038}</math>.
 +
 
 +
Proof:
 +
It is fairly easy to show 38 can't be split into 2 odd composites.
 +
 
 +
Assume there exists an even integer <math>m > 38</math> that m can't be split into 2 odd composites.
 +
 
 +
Then, we can consider m modulo 5.
 +
 
 +
If m = 0 mod 5, we can express m = 15 + 5k for some integer k. Since <math>m > 20</math>, <math>k > 1</math> so <math>k \geq 2</math>. Thus, 5k is composite. Since 15 is odd and composite, m is even, 5k should be odd as well.
 +
 
 +
If m = 1 mod 5, we can express m = 21 + 5k for some integer k. Since <math>m > 26</math>, <math>k > 1</math> so <math>k \geq 2</math>. Thus, 5k is composite. Since 21 is odd and composite, m is even, 5k should be odd as well.
 +
 
 +
If m = 2 mod 5, we can express m = 27 + 5k for some integer k. Since <math>m > 32</math>, <math>k > 1</math> so <math>k \geq 2</math>. Thus, 5k is composite. Since 27 is odd and composite, m is even, 5k should be odd as well.
 +
 
 +
If m = 3 mod 5, we can express m = 33 + 5k for some integer k. Since <math>m > 38</math>, <math>k > 1</math> so <math>k \geq 2</math>. Thus, 5k is composite. Since 33 is odd and composite, m is even, 5k should be odd as well.
 +
 
 +
If m = 4 mod 5, we can express m = 9 + 5k for some integer k. Since <math>m > 14</math>, <math>k > 1</math> so <math>k \geq 2</math>. Thus, 5k is composite. Since 9 is odd and composite, m is even, 5k should be odd as well.  
 +
 
 +
Thus, in all cases we can split m into 2 odd composites, and we get at a contradiction. <math>\blacksquare</math>
 +
 
 +
-Alexlikemath
 +
 
 +
==Solution 6==
 +
All numbers that could possibly work must be <math>2 \cdot p</math> where <math>p</math> is prime. As previous solutions stated, the maximum number that could possibly work by Chicken McNugget is <math>9 \cdot 25 - 9 - 25 = 225-34 = 191</math>. We then bash from top to bottom:
 +
 
 +
1. <math>178 = 89 \cdot 2 => 87 + 91</math> - refuted
 +
 
 +
2. <math>166 = 83 \cdot 2 => 81 + 85</math> - refuted
 +
 
 +
3. <math>158 = 79 \cdot 2 => 77 + 81</math> - refuted
 +
 
 +
4. <math>146 = 73 \cdot 2 => 69 + 77</math> - refuted
 +
 
 +
5. <math>142 = 71 \cdot 2 => 65 + 77</math> - refuted
 +
 
 +
6. <math>134 = 67 \cdot 2 => 65 + 69</math> - refuted
 +
 
 +
7. <math>122 = 61 \cdot 2 => 57 + 65</math> - refuted
 +
 
 +
8. <math>118 = 59 \cdot 2 => 55 + 63</math> - refuted
 +
 +
9. <math>106 = 53 \cdot 2 => 51 + 55</math> - refuted
 +
 
 +
10. <math>94 = 47 \cdot 2 => 45 + 49</math> - refuted
 +
 
 +
11. <math>86 = 43 \cdot 2 => 35 + 51</math> - refuted
 +
 
 +
12. <math>82 = 41 \cdot 2 => 33 + 49</math> - refuted
 +
 
 +
13. <math>74 = 37 \cdot 2 => 35 + 39</math> - refuted
 +
 
 +
14. <math>62 = 31 \cdot 2 => 27 + 35</math> - refuted
 +
 
 +
15. <math>58 = 29 \cdot 2 => 25 + 33</math> - refuted
 +
 
 +
16. <math>46 = 23 \cdot 2 => 21 + 25</math> - refuted
 +
 
 +
17. <math>38 = 19 \cdot 2 => = 19 + 19</math> - it works!
 +
 
 +
Because we did a very systematic bash as shown, we are confident the answer is <math>\boxed {038}</math>
 +
 
 +
~Arcticturn
 +
 
 +
== Solution 7 (casework) ==
 +
As stated above, all numbers that could possibly work must be <math>2 \cdot p</math> where <math>p</math> is prime. If <math>p</math> > 30, we consider <math>p</math> by modulo 30. <math>p</math> could be 1,7,11,13,17,19,23,29 modulo 30. <math>2 \cdot p</math> can be expressed as (<math>p</math>+<math>q</math>)+(<math>p</math>-<math>q</math>) for some positive, even <math>q</math> less then <math>p</math>.
 +
 
 +
If <math>p</math> = <math>1 \bmod{30}</math>, p±4 would both be composite
 +
 
 +
If <math>p</math> = <math>7 \bmod{30}</math>, p±2 would both be composite
 +
 
 +
If <math>p</math> = <math>11 \bmod{30}</math>, p±14 would both be composite
 +
 
 +
If <math>p</math> = <math>13 \bmod{30}</math>, p±8 would both be composite
 +
 
 +
If <math>p</math> = <math>17 \bmod{30}</math>, p±8 would both be composite
 +
 
 +
If <math>p</math> = <math>19 \bmod{30}</math>, p±14 would both be composite
 +
 
 +
If <math>p</math> = <math>23 \bmod{30}</math>, p±2 would both be composite
 +
 
 +
If <math>p</math> = <math>29 \bmod{30}</math>, p±4 would both be composite
 +
 
 +
So <math>p</math> < 30
 +
 
 +
From here, just try all possible p and find the answer is <math>\boxed {038}</math>
 +
 
 +
~Mathophobia
 +
 
 +
== Video Solution using Bashing==
 +
https://www.youtube.com/watch?v=n98zEG1-Hrs
 +
~North America Math Contest Go Go Go
  
 
== See also ==
 
== See also ==

Latest revision as of 00:16, 9 January 2024

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 prime quintuplet. However, only one prime quintuplet exists as exactly one of those 5 numbers must be divisible by 5.This 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}$.

Solution 3 (bash)

Let $2n$ be an even integer. Using the Chicken McNugget Theorem on the two smallest odd composite integers that are relatively prime from each other, 9 and 25, show that the maximum is 191, and the maximum even integer is 190 or lower. We use the fact that sufficiently high multiples of 6, 10, 14, 22, etc. can be represented as $n+n$. We bash each case until we find one that works.

Solution 4 (easiest)

The easiest method is to notice that any odd number that ends in a 5 is a composite (except for 5 itself). This means that we will have 15, 25, 35, etc... no matter what. What it also means is that if we look at the end digit, if 15 plus another number will equal that number, then any number that has that same end digit can be added by that same number plus a version of 15, 25, 35...

For example, let's say we assume our end digit of the number is 4. If we have 5 as one of our end digits, then 9 must be the end digit of the other number. If we go down our list of numbers that end with a 9 and is composite, we will stumble upon the number 9 itself. That means that the number 15+9 is able to be written in a composite form, but also anything that ends with a 4 and is above 15+9(ex. 34, 44 . . .). Hence the largest number that ends with a 4 that satisfies the conditions is 14.

If you list out all the numbers(15, 27, 9, 21, 33), you will notice that 33 is the largest number where the last digit is not repeated (13 and 23 are not composite). That means that 33+15 and any number greater that ends with a 3 is bad(ex. 58, 68. . .), so the largest number that satisfies the conditions is the largest number that ends with a 8 and is below 48. That number would be $\boxed{38}$

Solution 5

Claim: The answer is $\boxed{038}$.

Proof: It is fairly easy to show 38 can't be split into 2 odd composites.

Assume there exists an even integer $m > 38$ that m can't be split into 2 odd composites.

Then, we can consider m modulo 5.

If m = 0 mod 5, we can express m = 15 + 5k for some integer k. Since $m > 20$, $k > 1$ so $k \geq 2$. Thus, 5k is composite. Since 15 is odd and composite, m is even, 5k should be odd as well.

If m = 1 mod 5, we can express m = 21 + 5k for some integer k. Since $m > 26$, $k > 1$ so $k \geq 2$. Thus, 5k is composite. Since 21 is odd and composite, m is even, 5k should be odd as well.

If m = 2 mod 5, we can express m = 27 + 5k for some integer k. Since $m > 32$, $k > 1$ so $k \geq 2$. Thus, 5k is composite. Since 27 is odd and composite, m is even, 5k should be odd as well.

If m = 3 mod 5, we can express m = 33 + 5k for some integer k. Since $m > 38$, $k > 1$ so $k \geq 2$. Thus, 5k is composite. Since 33 is odd and composite, m is even, 5k should be odd as well.

If m = 4 mod 5, we can express m = 9 + 5k for some integer k. Since $m > 14$, $k > 1$ so $k \geq 2$. Thus, 5k is composite. Since 9 is odd and composite, m is even, 5k should be odd as well.

Thus, in all cases we can split m into 2 odd composites, and we get at a contradiction. $\blacksquare$

-Alexlikemath

Solution 6

All numbers that could possibly work must be $2 \cdot p$ where $p$ is prime. As previous solutions stated, the maximum number that could possibly work by Chicken McNugget is $9 \cdot 25 - 9 - 25 = 225-34 = 191$. We then bash from top to bottom:

1. $178 = 89 \cdot 2 => 87 + 91$ - refuted

2. $166 = 83 \cdot 2 => 81 + 85$ - refuted

3. $158 = 79 \cdot 2 => 77 + 81$ - refuted

4. $146 = 73 \cdot 2 => 69 + 77$ - refuted

5. $142 = 71 \cdot 2 => 65 + 77$ - refuted

6. $134 = 67 \cdot 2 => 65 + 69$ - refuted

7. $122 = 61 \cdot 2 => 57 + 65$ - refuted

8. $118 = 59 \cdot 2 => 55 + 63$ - refuted

9. $106 = 53 \cdot 2 => 51 + 55$ - refuted

10. $94 = 47 \cdot 2 => 45 + 49$ - refuted

11. $86 = 43 \cdot 2 => 35 + 51$ - refuted

12. $82 = 41 \cdot 2 => 33 + 49$ - refuted

13. $74 = 37 \cdot 2 => 35 + 39$ - refuted

14. $62 = 31 \cdot 2 => 27 + 35$ - refuted

15. $58 = 29 \cdot 2 => 25 + 33$ - refuted

16. $46 = 23 \cdot 2 => 21 + 25$ - refuted

17. $38 = 19 \cdot 2 => = 19 + 19$ - it works!

Because we did a very systematic bash as shown, we are confident the answer is $\boxed {038}$

~Arcticturn

Solution 7 (casework)

As stated above, all numbers that could possibly work must be $2 \cdot p$ where $p$ is prime. If $p$ > 30, we consider $p$ by modulo 30. $p$ could be 1,7,11,13,17,19,23,29 modulo 30. $2 \cdot p$ can be expressed as ($p$+$q$)+($p$-$q$) for some positive, even $q$ less then $p$.

If $p$ = $1 \bmod{30}$, p±4 would both be composite

If $p$ = $7 \bmod{30}$, p±2 would both be composite

If $p$ = $11 \bmod{30}$, p±14 would both be composite

If $p$ = $13 \bmod{30}$, p±8 would both be composite

If $p$ = $17 \bmod{30}$, p±8 would both be composite

If $p$ = $19 \bmod{30}$, p±14 would both be composite

If $p$ = $23 \bmod{30}$, p±2 would both be composite

If $p$ = $29 \bmod{30}$, p±4 would both be composite

So $p$ < 30

From here, just try all possible p and find the answer is $\boxed {038}$

~Mathophobia

Video Solution using Bashing

https://www.youtube.com/watch?v=n98zEG1-Hrs ~North America Math Contest Go Go Go

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=210312"