29
$\begingroup$

I go to the gym every Mon/Wed/Fri while a friend of mine goes every 3 days regardless of the day. A typical two weeks could look like:

     Su | M | T | W | R | F | Sa | Su | M | T | W | R | F | Sa
 ME:      X       X       X             X       X       X
HIM:          X           X             X           X

To my surprise, I've observed that I see him exactly once a week. I decided to look at it from a math perspective.

It's clear the number of times a week I see him has an upper bound of 1. If I see him Mon, he'll come in Thurs and I won't see him Wed/Fri. The same logic can be used for if I see him Wed/Fri.

However, I'm not sure why the lower bound here is 1. My intuition tells me it has something to do with modulus 7, since the days he comes to the gym are cyclical (this would also make some kind of sense since I'm coming to the gym every two days 3 times while he comes every 3 days and his cycle repeats every 3 weeks) but I can't make the mathematical leap.

I also tried to generalize. What if I come in for 3 days that are each 1 apart? Then it's obvious I'll see him exactly once. But what if I come in 3 days that are each 4 days apart?

I can bruteforce this to find that I'm right, but intuitively, why are our days lining up exactly once a week?

$\endgroup$
  • 4
    $\begingroup$ What's R? Thursday? If there is Sa and Su, why not Tu and Th? $\endgroup$ – Asaf Karagila May 25 '18 at 10:42
  • 7
    $\begingroup$ Your gym schedule is the same every week. His schedule, on the other hand, repeats only after $\mathrm{lcm}(3,7)=21$ days. Your example shows 14 days; the first week is of the type where his first gym day of the week is Tuesday, and the second week in your table is the type where his first gym day is a Monday. So if you had extended the table with just one more week, you would have completed the "brute force" proof already. $\endgroup$ – Jeppe Stig Nielsen May 25 '18 at 11:51
  • 10
    $\begingroup$ @AsafKaragila R is a common abbreviation for Thursday; it grew out of necessity for a single-letter abbreviations for weekdays. Saturday and Sunday aren't indicated as often in the work world, so I guess single-letter abbreviations for those never saw much use. (At least, I've never seen any.) I've noticed that universities around here tend to use R + Sa/Su for class schedules, since most classes aren't on weekends. $\endgroup$ – Zenexer May 25 '18 at 18:34
  • 4
    $\begingroup$ @AsafKaragila In undergrad, the schedules were laid out as MTWRFSU. I've used that schema ever since. $\endgroup$ – hBy2Py May 25 '18 at 18:56
  • 4
    $\begingroup$ @Zenexer Common in what country? I'm in the U.S. and I've never seen it before. Semi-jokingly, why not use Þ? $\endgroup$ – David Conrad May 26 '18 at 11:33
42
$\begingroup$

Let's think of numbers $0, 1, \ldots, 6, \ldots$ as the days starting from some Sunday.

Then every Monday, Wednesday, and Friday, means $\{7n + 1, 7n + 3, 7n + 5\}$.

"Every three days" is all days of the form $3n + k$, where $k \in \{0, 1, 2\}$. Equivalently, these are all days that are $\equiv k \pmod 3$.

Taking $\{\rm M, W, F\}$ modulo $3$, we get $\{n+1, n, n+2\}$, which is the same as $\{0,1,2\}$, thus one of Monday, Wednesday, Friday is $k \pmod{3}$. Thus for any $k$, there is a day that matches both sets.

$\endgroup$
17
$\begingroup$

Take any three numbers of the form $n,n+2,n+4$ for some $n\in\Bbb N$. Then one of them, and exactly one, is a multiple of $3$.

This is because $2$ is a generator of the cyclic group of order $3$, $\Bbb Z/3\Bbb Z$.

$\endgroup$
  • 10
    $\begingroup$ (Or, more intuitively for me, $n, n + 2, n + 4$ is $n, (n + 1) + 3, n + 2$ and exactly one out of $n, n + 1, n + 2$ has to be divisible by 3.) $\endgroup$ – muru May 25 '18 at 5:08
  • $\begingroup$ @muru that's indeed a valid proof, maybe more understandable as it is elementary, but the reason I gave is fundamentally one one should learn if they are interested in maths. $\endgroup$ – Arnaud Mortier May 25 '18 at 11:20
  • 2
    $\begingroup$ @muru if you're interested, what you wrote is that $2 $ is a generator because $1 $ is. $\endgroup$ – Arnaud Mortier May 25 '18 at 12:08
  • $\begingroup$ ah, it's been a few years since I last (and first) studied groups and generators, but it is nice to see what one stumbled on to. $\endgroup$ – muru May 25 '18 at 12:32
12
$\begingroup$

It's clear the number of times a week I see him has an upper bound of 1. If I see him Mon, he'll come in Thurs and I won't see him Wed/Fri. The same logic can be used for if I see him Wed/Fri.

Similar logic works the other way around. Since he comes every three days, he'll have to be there on Monday, Tuesday or Wednesday:

  • If he comes in on Monday, you'll see him on Monday.
  • If he comes in on Tuesday, he'll also come on Friday, and you'll see him on Friday.
  • If he comes in on Wednesday, you'll see him on Wednesday.

So there's also a lower bound of 1.

If you go on three days that are four days apart, they can be numbered as $n$, $n+4$, and $n+8$. Modulo 3, these are $n$, $n+1$ and $n+2$. All remainders modulo 3 are covered, so exactly one of these days coincides with the every-three-days cycle of the other person.

On the other hand, if you went on days that are three apart (or any multiple of three), then your partial cycle would be locked with the other person's cycle, and you'd see him either every time, or never.

$\endgroup$
3
$\begingroup$

Your pattern would repeat every 2 days if you didn't include Sunday. Looking at the six days from Monday to Saturday, your pattern is:

X-X-X- (1, 3, 5)

which is all the odd numbers, if Monday is day 1.

Your friend goes every 3 days and his pattern shifts compared to yours:

X--X-- (1, 4)
-X--X- (2, 5)
--X--X (3, 6)

Only one of his days will be odd, the other will be even for the six overlapping days. That's why it will always be one day per week you will be at the gym on the same day.

$\endgroup$
2
$\begingroup$

He comes in every three days, so on any given week he comes in on all day whith numbers congruent to x modulo 3, just the x changes from week to week, but it can be assumed to be 0, 1, or 2.

You on the other hand come in on days 0, 2, 4. Modulo 3, that is 0, 2, 1. So he will be there on exactly one of your days.

What makes this particular setup work: He comes in every $n$ days, you come in on exactly $n$ days, and the days on which you come in are $m$ apart, where $m$ is relatively prime to $n$ (so that $0$, $m$, $2m$, ..., $(n-1)m$ are all different modulo $n$).

$\endgroup$
1
$\begingroup$

One way of analyzing this is to take your period (7 days), his period (3 days), and take the lcm (21 days). Every 21 days, your combined pattern will be the same. Once you see what happens each week three weeks in a row, you know what the general pattern is. This can be generalized to other cases.

Then it's obvious I'll see him exactly once. But what if I come in 3 days that are each 4 days apart?

Then your period will be 12 days, and his will be 3, so your combined period will be lcm(12,3) = 12. If you line up the first time, the next time you will be one day late. The third time, you will be two days late. The fourth time, you will be three days late, but since he comes every three days, you will line up again. So you will see him every three visits, he will see you every four of his visits, and you will see each other every 12 days.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.