# Simple Sequence Problem: Walk in the park

In a 365 day year, Joe, Greg & Dean visit the park multiple times for a walk.

• Joe visits every 3rd day
• Greg visits every 5th day
• Dean visits every 7th day
• All three visit the park on the first day of the year

In the year:

• On how many days is Greg alone in the park?
• On how many days will Dean meet Joe?
• On how many days will all three meet?

I can work this out brute force by laying down the multiples of 3,5,7 from 1 to 365. I'm looking for an efficient way of formalizing the calculation step by step. What'd be the best way?

-
Are you familiar with the Inclusion-Exclusion Principle? – jericson Oct 30 '10 at 21:51
Nopes :( Any clues/references? – MassiveAttack Oct 30 '10 at 22:00
Use the chinese remainder theorem to solve the set of congruences. The days are prime for a reason :D – crasic Oct 30 '10 at 22:40
For inclusion/exclusion, look at Wikipedia – Ross Millikan Oct 31 '10 at 14:59

Lets say its the $x$th day. Then, Greg is alone if and only if $x$ is a multiple of $5$ but not of $3$ or $7$. Dividing 365 by $5$ we get that Greg will go to the park 73 times.
Joe will go to the park every 3 times that Greg goes to the park. 73 = 24*3 + 1, so will be 24 occasions in which Joe is also in the park. Also, as 73 = 10*7 + 3, there will be 10 occasions when Dean is also in the park. Finally they are all in the park if $x$ is a multiple of $3*5*7=105$, which is only on 3 days. Thus, tallying it all up Greg is alone 73 - 24 - 10 + 3 = 42 days out of the year (the reason I add 3 is because in subtracting 24 and 10 I have also included days when they are both there twice, but we are only counting how many days he is alone).
Similarly, Dean will meet Joe if and only if $x$ is both a multiple of 3 and 7, or if and only if $x$ is a multiple of 21. As $365 = 17*21 + 8$, they will meet on $17$ occasions.