Daphne is visited periodically by her three best friends: Alice, Beatrix, and Claire. Alice visits every third day, Beatrix visits every fourth day, and Claire visits every fifth day. All three friends visited Daphne yesterday. How many days of the next 365-day period will exactly two friends visit her?
- A)
- B)
- C)
- D)
- E)
Answer
B
Key insight
Two friends meet on multiples of 12, 15 or 20. All three meet on multiples of 60, and those days must be taken out of each pair's count.
Solution
Call yesterday day . The question is about days to . Alice comes on days (multiples of ), Beatrix on multiples of , Claire on multiples of .
1. When do Alice and Beatrix both come? On days that are multiples of both and , which means multiples of . From to there are of them, since .
2. Alice and Claire: multiples of . There are , since .
3. Beatrix and Claire: multiples of . There are , since .
4. When do all three come? On multiples of . There are , since .
5. Take those out. A day when all three come is not an "exactly two" day. Each such day was counted in all three lists above (for example, day is a multiple of , of and of ). So remove from each list:
The answer is .
Why this works
Two repeating schedules line up on multiples of the least common multiple of their gaps. "Exactly two" means you must throw out the days when the third friend also shows up. Each all-three day sits in every one of the three pair lists, so it is removed three times, once from each.
Alternative approach
The whole pattern repeats every days, so look at days to first. Multiples of : days. Of : days. Of : days. Only day has all three, so exactly-two days number per block of . Six blocks cover days to , giving . Days to contain no multiple of , or , so the answer stays .
The trap
Counting the multiples of 12, 15 and 20 and stopping at 30 + 24 + 18 = 72, without removing the days when all three come.
Concise solution
Call yesterday day ; the period in question is days through . Alice comes on multiples of , Beatrix on multiples of , Claire on multiples of .
Two particular friends both come on multiples of the lcm of their periods:
- Alice and Beatrix: multiples of , days.
- Alice and Claire: multiples of , days.
- Beatrix and Claire: multiples of , days.
Each of these counts includes the days when all three come, the multiples of : days. Those must be removed from each pair count, because "exactly two" excludes them:
The answer is .
Review in the AoPS books
- Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic (§1.3)
- Introduction to Number Theory, Chapter 3: Multiples and Divisors (§3.3, §3.4, §3.7)
- Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.3)
- Intermediate Counting & Probability, Chapter 3: A Piece of PIE (§3.2, §3.3)
Techniques
Count the complement and subtract from the total · Set up the equation/formula and compute; no special trick needed