2002 AIME I Problems/Problem 9
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.
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 .
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 .
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 .
|2002 AIME I (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|