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 "2002 AIME I Problems/Problem 9"
(→‎Problem)
 
(17 intermediate revisions by 9 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
 +
Harold, Tanya, and Ulysses paint a very long picket fence.
 +
 +
* Harold starts with the first picket and paints every <math>h</math>th picket;
 +
* Tanya starts with the second picket and paints every <math>t</math>th picket; and
 +
* Ulysses starts with the third picket and paints every <math>u</math>th picket.
 +
 +
Call the positive integer <math>100h+10t+u</math> paintable when the triple <math>(h,t,u)</math> of positive integers results in every picket being painted exactly once. Find the sum of all the paintable integers.
  
 
== Solution ==
 
== Solution ==
−
{{solution}}
+
=== Solution 1 ===
 +
Note that it is impossible for any of <math>h,t,u</math> to be <math>1</math>, since then each picket will have been painted one time, and then some will be painted more than once. 
 +
 
 +
<math>h</math> cannot be <math>2</math>, or that will result in painting the third picket twice. If <math>h=3</math>, then <math>t</math> may not equal anything not divisible by <math>3</math>, and the same for <math>u</math>. Now for fourth and fifth pickets to be painted, <math>t</math> and <math>u</math> must be <math>3</math> as well. This configuration works, so <math>333</math> is paintable.
 +
 
 +
If <math>h</math> is <math>4</math>, then <math>t</math> must be even. The same for <math>u</math>, except that it can't be <math>2 \mod 4</math>. Thus <math>u</math> is <math>0 \mod 4</math> and <math>t</math> is <math>2 \mod 4</math>. Since this is all <math>\mod 4</math>, <math>t</math> must be <math>2</math> and <math>u</math> must be <math>4</math>, in order for <math>5,6</math> to be paint-able. Thus <math>424</math> is paintable.
 +
 
 +
<math>h</math> cannot be greater than <math>4</math>, since if that were the case then the answer would be greater than <math>999</math>, which would be impossible for the AIME.
 +
 
 +
Thus the sum of all paintable numbers is <math>\boxed{757}</math>.
 +
 
 +
=== Solution 2 ===
 +
Again, note that <math>h,t,u \neq 1</math>. The three conditions state that no picket number <math>n</math> may satisfy any two of the conditions: <math>n \equiv 1 \pmod{h},\ n \equiv 2 \pmod{t},\ n \equiv 3 \pmod{u}</math>. By the [[Chinese Remainder Theorem]], the [[greatest common divisor]] of any pair of the three numbers <math>\{h,t,u\}</math> cannot be <math>1</math> (since otherwise [[without loss of generality]] consider <math>\text{gcd}\,(h,t) = 1</math>; then there will be a common solution <math>\pmod{h \times t}</math>).
 +
 
 +
Now for <math>4</math> to be paint-able, we require either <math>h = 3</math> or <math>t=2</math>, but not both.
 +
*In the former condition, since <math>\text{gcd}\,(h,t),\ \text{gcd}\,(h,u) \neq 1</math>, it follows that <math>3|t,u</math>. For <math>5</math> and <math>6</math> to be paint-able, we require <math>t = u = 3</math>, and it is easy to see that <math>333</math> works.
 +
*In the latter condition, similarly we require that <math>2|h,u</math>. All even numbers are painted. We now renumber the remaining odd pickets to become the set of all positive integers (<math>1,3,5, \ldots \rightarrow 1',2',3', \ldots</math>, where <math>n' = \frac{n+1}{2}</math>), which requires the transformation <math>h' = h/2,\ u' = u/2</math>, and with the painting starting respectively at <math>1',2'</math>. Our new number system retains the same conditions as above, except without <math>t</math>. We thus need <math>\text{gcd}\, (h',u') \neq 1, h',u' \neq 1</math>. Then for <math>3',4'</math> to be painted, we require <math>h' = u' = 2</math>. This translates to <math>424</math>, which we see works. 
 +
 
 +
Thus the answer is <math>333+424 = \boxed{757}</math>.
 +
=== Solution 3 ===
 +
The three conditions state that no picket number <math>n</math> may satisfy any two of the conditions: <math>n \equiv 1 \pmod{h},\ n \equiv 2 \pmod{t},\ n \equiv 3 \pmod{u}</math>. Note that the smallest number, <math>min \{ h,t,u \}, </math> divides the other <math>2</math>, and the next smallest divide the largest number, otherwise there is a common solution by the [[Chinese Remainder Theorem]]. It is also a necessary condition so that it paints exactly once. Note that the smallest number can't be at least <math>5</math>, otherwise not all picket will be painted. We are left with few cases (we could also exclude <math>1</math> as the possibility) which could be done quickly. Thus the answer is <math>333+424 = \boxed{757}</math>.
  
 
== See also ==
 
== See also ==
−
* [[2002 AIME I Problems/Problem 8| Previous problem]]
+
{{AIME box|year=2002|n=I|num-b=8|num-a=10}}
−
 
 
−
* [[2002 AIME I Problems/Problem 10| Next problem]]
 
  
−
* [[2002 AIME I Problems]]
+
[[Category:Intermediate Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 18:44, 25 April 2024

Problem

Harold, Tanya, and Ulysses paint a very long picket fence.

  • Harold starts with the first picket and paints every $h$th picket;
  • Tanya starts with the second picket and paints every $t$th picket; and
  • Ulysses starts with the third picket and paints every $u$th picket.

Call the positive integer $100h+10t+u$ paintable when the triple $(h,t,u)$ of positive integers results in every picket being painted exactly once. Find the sum of all the paintable integers.

Solution

Solution 1

Note that it is impossible for any of $h,t,u$ to be $1$, since then each picket will have been painted one time, and then some will be painted more than once.

$h$ cannot be $2$, or that will result in painting the third picket twice. If $h=3$, then $t$ may not equal anything not divisible by $3$, and the same for $u$. Now for fourth and fifth pickets to be painted, $t$ and $u$ must be $3$ as well. This configuration works, so $333$ is paintable.

If $h$ is $4$, then $t$ must be even. The same for $u$, except that it can't be $2 \mod 4$. Thus $u$ is $0 \mod 4$ and $t$ is $2 \mod 4$. Since this is all $\mod 4$, $t$ must be $2$ and $u$ must be $4$, in order for $5,6$ to be paint-able. Thus $424$ is paintable.

$h$ cannot be greater than $4$, since if that were the case then the answer would be greater than $999$, which would be impossible for the AIME.

Thus the sum of all paintable numbers is $\boxed{757}$.

Solution 2

Again, note that $h,t,u \neq 1$. The three conditions state that no picket number $n$ may satisfy any two of the conditions: $n \equiv 1 \pmod{h},\ n \equiv 2 \pmod{t},\ n \equiv 3 \pmod{u}$. By the Chinese Remainder Theorem, the greatest common divisor of any pair of the three numbers $\{h,t,u\}$ cannot be $1$ (since otherwise without loss of generality consider $\text{gcd}\,(h,t) = 1$; then there will be a common solution $\pmod{h \times t}$).

Now for $4$ to be paint-able, we require either $h = 3$ or $t=2$, but not both.

  • In the former condition, since $\text{gcd}\,(h,t),\ \text{gcd}\,(h,u) \neq 1$, it follows that $3|t,u$. For $5$ and $6$ to be paint-able, we require $t = u = 3$, and it is easy to see that $333$ works.
  • In the latter condition, similarly we require that $2|h,u$. All even numbers are painted. We now renumber the remaining odd pickets to become the set of all positive integers ($1,3,5, \ldots \rightarrow 1',2',3', \ldots$, where $n' = \frac{n+1}{2}$), which requires the transformation $h' = h/2,\ u' = u/2$, and with the painting starting respectively at $1',2'$. Our new number system retains the same conditions as above, except without $t$. We thus need $\text{gcd}\, (h',u') \neq 1, h',u' \neq 1$. Then for $3',4'$ to be painted, we require $h' = u' = 2$. This translates to $424$, which we see works.

Thus the answer is $333+424 = \boxed{757}$.

Solution 3

The three conditions state that no picket number $n$ may satisfy any two of the conditions: $n \equiv 1 \pmod{h},\ n \equiv 2 \pmod{t},\ n \equiv 3 \pmod{u}$. Note that the smallest number, $min \{ h,t,u \},$ divides the other $2$, and the next smallest divide the largest number, otherwise there is a common solution by the Chinese Remainder Theorem. It is also a necessary condition so that it paints exactly once. Note that the smallest number can't be at least $5$, otherwise not all picket will be painted. We are left with few cases (we could also exclude $1$ as the possibility) which could be done quickly. Thus the answer is $333+424 = \boxed{757}$.

See also

2002 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 8 		Followed by
Problem 10
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2002_AIME_I_Problems/Problem_9&oldid=218676"