Olympiad Maths Prep

Track / Stage 6 / 228 of 400 #1228 of 2000

Problem 1228

National olympiad, first round
Combinatorics Difficulty 6.4 Find the answer

Harold, Tanya, and Ulysses paint a very long picket fence.
Harold starts with the first picket and paints every hhth picket;
Tanya starts with the second picket and paints everth ttth picket; and
Ulysses starts with the third picket and paints every uuth picket.
Call the positive integer 100h+10t+u100h+10t+u paintable\textit{paintable} when the triple (h,t,u)(h,t,u) of positive integers results in every picket being painted exaclty once. Find the sum of all the paintable integers.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

To solve this problem, we need to ensure that every picket is painted exactly once by Harold, Tanya, and Ulysses. We will analyze the conditions under which this happens and find the sum of all paintable integers 100h+10t+u100h + 10t + u.

1. Analyzing the conditions:
- Harold starts with the first picket and paints every hh-th picket.
- Tanya starts with the second picket and paints every tt-th picket.
- Ulysses starts with the third picket and paints every uu-th picket.

We need to ensure that every picket is painted exactly once. This means that the sequences generated by hh, tt, and uu must cover all positive integers without overlapping.

2. Case Analysis:
- **Case 1: hh paints the 4th picket.**
- If Harold paints the 4th picket, then h=3h = 3.
- **Sub-case 1: tt paints the 5th picket.**
- If Tanya paints the 5th picket, then t=3t = 3 and u=3u = 3. This gives the paintable integer 333333.
- **Sub-case 2: uu paints the 5th picket.**
- If Ulysses paints the 5th picket, then u=2u = 2. However, this would mean (h,u)=1(h, u) = 1, which does not work because hh and uu must be relatively prime.

- **Case 2: tt paints the 4th picket.**
- If Tanya paints the 4th picket, then t=2t = 2.
- **Sub-case 1: hh paints the 5th picket.**
- If Harold paints the 5th picket, then h=4h = 4 and u=2u = 2. This gives the paintable integer 424424.
- **Sub-case 2: uu paints the 5th picket.**
- If Ulysses paints the 5th picket, then u=2u = 2. However, this would mean h=0h = 0, which does not work because hh must be a positive integer.

- **Case 3: uu paints the 4th picket.**
- If Ulysses paints the 4th picket, then u=1u = 1. However, this would mean uu paints everything, which does not work because uu must be greater than 1.

3. Summing the paintable integers:
- From the valid sub-cases, we have the paintable integers 333333 and 424424.
- Summing these integers: 333+424=757333 + 424 = 757.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.