2002 AIME I Problems/Problem 9
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 odd. 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 .
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 |