2
$\begingroup$

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

  • Joe visits every $3$rd day
  • Greg visits every $5$th day
  • Dean visits every $7$th 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?

  • 0
    Are you familiar with the Inclusion-Exclusion Principle?2010-10-30
  • 0
    Nopes :( Any clues/references?2010-10-30
  • 1
    Use the chinese remainder theorem to solve the set of congruences. The days are prime for a reason :D2010-10-30
  • 0
    For inclusion/exclusion, look at Wikipedia2010-10-31

1 Answers 1

4

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.

Basically to attack these problems just think about dividing the 365 days and using the quotient, as it is equal to the number of days a given person goes to the park.

  • 0
    Superb, thanks so much for such a clear explanation.2010-10-30
  • 0
    Since all go to the park on the first day of the year, won't Dean and Joe meet on 18 occasions, not 17? (The last one on 24th of December, unless they skip it to prepare Christmas). Basically, since the very first day of a cycle is a got-to-park day, you may want to round up instead of down. Same thing for Greg being alone only on 41 days. (Frankly, in such a case I'd take brute force anytime, but that's another discussion)2011-08-17