Difference between revisions of "2002 AIME I Problems/Problem 9"

Revision as of 11:13, 13 July 2008

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 odd. 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.

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}$ .

@@ Line 2: / Line 2: @@
 Harold, Tanya, and Ulysses paint a very long picket fence.
-Harold starts with the first picket and paints every <math>h</math> th picket;
+*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
-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.
-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.
@@ Line 26: / Line 24: @@
 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 again we see 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>.
@@ Line 32: / Line 30: @@
 == See also ==
 {{AIME box|year=2002|n=I|num-b=8|num-a=10}}
+[[Category:Intermediate Number Theory Problems]]

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

Page

Toolbox

Search