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