Prerequirement:

## The problem

Charles, Mary and Tom are three friends who like jogging. Today they went jogging together, but this situation seldom happens. In fact each of them follow an own pace, different from the others: Charles goes jogging every three days, Mary every four days and Tom every five. So the next times they will go jogging alone: Charles in three days, Mary in four days and Tom in five, then Charles and Mary will go gogging again, respectively in six and eight days, and so on. The first among them who will go jogging again together are just Charles and Mary, in twelve days.

The described situation can be shown by a dashed line: in particular, the linear dashed line (3, 4, 5):

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | \ldots | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

Charles | – | – | – | – | – | – | – | \ldots | ||||||||||||||

Mary | – | – | – | – | – | – | \ldots | |||||||||||||||

Tom | – | – | – | – | – | \ldots |

The interpretation of the table is very simple: columns represent days and the dashes in each column indicate who will go jogging that day. So we read that today, day 0, everyone goes jogging; tomorrow and the day after tomorrow, days 1 and 2, no one will go jogging; on day 3 only Charles will go jogging,; …; on day 20 Mary and Tom will go jogging.

We can ask some questions:

- We saw that Charles will be the first who will go jogging again, Mary will be the second and Tom the third… but, given any positive integer number x, starting from tomorrow who will be the x-th to go jogging in time order and, being the day equal, in alphabetical order?
- The person who answers the previous question, in how many days will go jogging?
- There are some days in which no one goes jogging: the first will be tomorrow, the second the day after tomorrow, the third in seven days… but in general what day will be the x-th of such days?

The theory of dashed lines was conceived for answering this kind of questions. Let’s see how.

First question: who will be the x-th to go jogging starting from tomorrow? For answering by an only graphical method, let’s put the dashes of Table 1 in order as follows:

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | \ldots | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

Charles | – | 1 | 4 | 6 | 8 | 10 | 13 | \ldots | ||||||||||||||

Mary | – | 2 | 5 | 9 | 12 | 14 | \ldots | |||||||||||||||

Tom | – | 3 | 7 | 11 | 15 | \ldots |

Here we see clearly that Charles will be the first who will go jogging again, followed by Mary and Tom, then Charles and Mary, then Charles again, and so on: so, looking at the name of the row on the left, we have the answers for the first question, as x varies. But, looking at the column numbers instead, we can answer the second question (the x-th person who will go jogging, in how many days he or she will do) at the same time. For example, searching for number 7 in the table, after finding it in the row of Tom and in column 10, we can say that the seventh person who will go jogging is Tom, and he will do it in 10 days. So Table 2 lets us answer the first two questions: the answer to the first question is the name of the row and the answer to the second question is the number of the column.

There is also the particular case in which at least two persons go jogging in the same day: for example in the twelfth day both Charles and Mary will go jogging. In the previous days, the event that any of the three friends went jogging happened 7 times, as you can see in the table; therefore Charles and Mary are, taking them altogether, the eighth and the ninth person. But, as they go jogging in the same day, who is the eighth and who the ninth? We get the answer by reading carefully the first question: “starting from tomorrow who will be the x-th to go jogging *in time order and, being the day equal, in alphabetical order*?”. If two or more persons go jogging in the same day, we have to count them in alphabetical order: in this case Charles is the eighth and Mary the ninth, simply because the letter C comes before the M. In fact, it’s no accident that the rows of Tables 1 and 2 are sorted from top to bottom according to the alphabetical order of the three friends: this way the order of the persons who go jogging in the same day coincides with the order of the rows, from top to bottom; in other terms, if there are at least two numbers in a single column, they are increasing from top to bottom, like in columns 12, 15 and 20.

Taking into account the day order, and the alphabetical order in a single day at the same time, you can easily obtain Table 2 from Table 1 by reading the latter by columns, from left to right and from top to bottom, numbering the dashed lines as you read them. This is the meaning of Definition T.4 (*Ordering of dashes*).

Let’s come back to the last question: the x-th day in which no one goes jogging. With reference to the representation of a dashed line, like Table 1, we know that this particular days are called *spaces* (Definition T.3), that are the columns that don’t contain any dash. For answering the question, it’s enough to sort spaces according to their numerical value: this means numbering them as we see them when reading the table from left to right:

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | \ldots | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

Charles | – | 1 | 2 | – | – | 3 | – | 4 | – | 5 | 6 | – | 7 | – | 8 | \ldots | ||||||

Mary | – | – | – | – | – | – | \ldots | |||||||||||||||

Tom | – | – | – | – | – | \ldots |

So we see that the first day in which no one goes jogging is the day 1 (tomorrow), the second day is the day 2, the third is the day 7, the fourth the day 11, and so on: in this way, looking at Table 3, we are able to answer the third question.

## The mathematical formulation

The three questions we have posed are among the subject matters of dashed line theory. In order to deal with this study in a mathematical way, we introduce the following functions:

- The function \mathrm{t}(x), mapping x to the x-th dash, that will be of kind (1, n) if it lays in the first row (that one of Charles), of kind (2, n) if it lays in the second row (that one of Mary), of kind (3, n) if it lays in the third row (that one of Tom).
- The function \mathrm{t\_value}(x), mapping x to the value (i.e. the column) of the x-th dash.
- The function \mathrm{t\_space}(x), mapping x to the x-th space.

These three functions are related to the three questions as follows:

- The answer to the first question is in the row number of the dash returned by the function \mathrm{t}(x). In particular, given that \mathrm{t}(x) = (i, n), if i = 1 it means that Charles will be the x-th person who will run, Mary will be if i = 2 and Tom will be if i = 3.
- The answer to the second question is the result of \mathrm{t\_value}(x).
- The answer to the third question is the result of \mathrm{t\_space}(x).

The functions \mathrm{t} and \mathrm{t\_value} are tightly connected: in fact \mathrm{t\_value}(x) is the value of the x-th dash, that in turn is \mathrm{t}(x). We recall, in this regard, that the value of a dash is given by the dashed line function, which in this case, for the dashed line T = (3, 4, 5), is

So, summarizing, we can say that the following equality holds:

As we can consider \mathrm{t\_value}(x) to be a simplified notation, in place of T(\mathrm{t}(x)).

As an example, let’s see what are the first values of the three functions, for x = 1, 2, 3, 4, 5, \ldots, in the dashed line we have taken under consideration:

- \mathrm{t}(x): (1, 1), (2, 1), (3, 1), (1, 2), (2, 2), \ldots
- \mathrm{t\_value}(x): 3, 4, 5, 6, 8, \ldots
- \mathrm{t\_space}(x): 1, 2, 7, 11, 13, \ldots

In this case it’s clear that the functions we have introduced refer to the dashed line (3, 4, 5), because it’s the only dashed line we have considered since the beginning. But in general, every time it’s worth to specify the dashed line T which the functions \mathrm{t}, \mathrm{t\_value} and \mathrm{t\_space} refer to, we denote them as \mathrm{t}_T(x), \mathrm{t\_value}_T(x) e \mathrm{t\_space}_T(x). Here are their formal definitions.

Function \mathrm{t}

Let T be a dashed line of order k. The function \mathrm{t}_T(x): \mathbb{N}^{\star} \rightarrow \{1, \dots, k\} \times \mathbb{N} is defined as:

We agree that, when we want to say that the function \mathrm{t}_T has a given property P that is true for all T, or for no T, we say briefly “the function \mathrm{t} has the property P“, or “the function \mathrm{t} has not the property P“, meaning that “the function \mathrm{t}_T has the property P, for all T“, or “the function \mathrm{t}_T has not the property P, for all T“.

Function \mathrm{t\_value}

Let T be a dashed line. The function \mathrm{t\_value}_T(x): \mathbb{N}^{\star} \rightarrow \mathbb{N} is defined as:

We use the expressions “\mathrm{t\_value} has the property P” or “\mathrm{t\_value} has not the property P” with the same meaning as that one explained in Definition T.7.

Function \mathrm{t\_space}

Let T be a dashed line. The function \mathrm{t\_space}_T(x): \mathbb{N}^{\star} \rightarrow \mathbb{N} is defined as:

We use the expressions “\mathrm{t\_space} has the property P” or “\mathrm{t\_space} has not the property P” with the same meaning as that one explained in Definition T.7.

## The solution

We have seen that in order to solve the initial problem we have to calculate the functions \mathrm{t}, \mathrm{t\_value} and \mathrm{t\_space}. The calculation of these functions for any dashed line is one of the main problems of dashed line theory. Till now, we know the formulas for calculating the functions \mathrm{t} and \mathrm{t\_value} for any linear dashed line up to order three, and \mathrm{t\_space} up to order two. We’ll examine in depth this matter but, just to have an idea, let’s see what formulas hold for the dashed line T = (3, 4, 5), hence obtaining the answers to the questions we initially posed.

Let’s start with the function \mathrm{t}(x). We saw that it computes the x-th dash, which we can indicate by the couple (i, n), that is we let \mathrm{t}(x) = (i, n). The dashed line theory formulas let compute only i first and then, on this basis, also n.

The number i is computed essentially by trial: there is a specific formula to establish if a certain value of i is the correct one. Being i the row number, the number of possible values is equal to the number of rows of the dashed line, that is its order. In this case i \in \{1, 2, 3\} because the dashed line T = (3, 4, 5) is of order three, and the formulas are the following:

In formulas (2), (3) and (4), the numbers are obtained as functions of the dashed line components, as follows:

- 27 = 3(4 + 5)
- 32 = 4(3 + 5)
- 35 = 5(3 + 4)
- \begin{array}{c} \{9, 14, 19, 24, 13, 18, 23, 28, 17, 22, 27, 32, 21, 26, 31, 36, 25, 30, 35, 40\} = \\ \{4a + 5b \mid a \in \{1, 2, 3, 4, 5\}, b \in \{1, 2, 3, 4\}\} \end{array}
- \begin{array}{c} \{5, 10, 15, 8, 13, 18, 11, 16, 21, 14, 19, 24, 17, 22, 27\} = \\ \{3a + 5b \mid a \in \{0, 1, 2, 3, 4\}, b \in \{1, 2, 3\}\} \end{array}
- \{0, 4, 8, 3, 7, 11, 6, 10, 14, 9, 13, 17\} = \{3a + 4b \mid a \in \{0, 1, 2, 3\}, b \in \{0, 1, 2\}\}

Now let’s try to do the calculations, for example for x = 12.

Let’s see if i = 1, by applying formula (2). We have that 27 \cdot 12 \mathrm{\ mod\ } 47 = 324 \mathrm{\ mod\ } 47 = 42. No element of the set of formula (2), when divided by 47, gives 42 as reminder, so i \neq 1.

So let’s see if i = 2, by applying formula (3). We have that 32 \cdot 12 \mathrm{\ mod\ } 47 = 384 \mathrm{\ mod\ } 47 = 8. The set in (3) contains the number 8, the reminder modulo 47 of which is again 8, so i = 2. At this point we can stop, because only one value for i is possible. If you want, however, you can compute also formula (4) and verify that i \neq 3.

Having established that i = 2, we know that the twelfth dash is in row 2, as you can see in Table 2. This result, related with the problem, means that the twelfth person who will go jogging will be the one of the second row, i.e. Mary. We have just obtained the answer to the first question.

Now, as we know the value of i, we can compute the value of n, completing the computation of the \mathrm{t} function. For this purpose different formulas exist, more or less complex and more or less accurate. We’ll apply here the following exact formula:

In this formula, the numbers 35 and 47 have been obtained as before, 3 is the least dashed line component, 7 is the sum of the first two components. Moreover, the 5 appearing at the numerator of the internal fraction is equal to one of the components, but it’s a coincidence: in fact it was computed as a function of the first two components with the formula 3 \cdot 4 - (3 + 4).

Doing the calculations with x = 12, we have that n = \left \lceil \frac{3 \left \lceil \frac{35x - 5}{47} \right \rceil}{7} \right \rceil = \left \lceil \frac{3 \left \lceil \frac{415}{47} \right \rceil}{7} \right \rceil = \left \lceil \frac{3 \cdot 9}{7} \right \rceil = \left \lceil \frac{27}{7} \right \rceil = 4. So, being i = 2 and n = 4, we can say that the twelfth dash is \mathrm{t}(12) = (2, 4).

Now, as we have computed the twelfth dash, we can compute its value by means of the dashed line function given by (1):

That is the answer to the second question: the twelfth person who will go jogging, will do it in 16 days.

A note for the most curious people: if you want you can try formulas (2), (3) and (4) with different values of x, even very big ones, for verifying their correctness. However formula (5) holds only for i = 2, while in general n is given by:

Moreover, this is not the only possible exact formula, but we’ll see the others in specific posts.

Concerning the last question, that is the computation of the x-th space, a general formula is not known yet for dashed lines of order three, but only up to order two. So we answer to a simplified version of the question, restricted to the first two friends: what is the x-th day in which neither Charles nor Mary will go jogging? The answers are shown in the following table:

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | \ldots | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

Charles | – | 1 | 2 | – | 3 | – | 4 | – | 5 | 6 | – | 7 | 8 | – | 9 | – | 10 | \ldots | ||||

Mary | – | – | – | – | – | – | \ldots |

So we are considering the dashed line of order two (3, 4). In this case the solution of the problem is given by the following formula:

In this formula, 3 and 4 are the dashed line components, and the numbers 5, 8 and 6 were obtained from them as follows:

- The 8 of the first case is given by \frac{(3 - 1)\mathrm{LCM}(3, 4)}{3}
- 6 = (3 - 1)(4 - 1)
- 5 = (3 - 1)(4 - 1) - 1
- The 8 of the second case is given by (3 - 1)4

Let’s do the calculations with x = 10. The number 10 is not multiple of 6, so we have to apply the second case formula. Placing numbers we have: \mathrm{t\_space}(10) = \left \lfloor \frac{3 \left \lfloor \frac{8\left(10 - \left \lfloor \frac{10}{6} \right \rfloor \right) - 3}{5} \right \rfloor - 1}{2} \right \rfloor = \left \lfloor \frac{3 \left \lfloor \frac{8(10 - 1) - 3}{5} \right \rfloor - 1}{2} \right \rfloor = \left \lfloor \frac{3 \left \lfloor \frac{69}{5} \right \rfloor - 1}{2} \right \rfloor = \left \lfloor \frac{3 \cdot 13 - 1}{2} \right \rfloor = \left \lfloor \frac{38}{2} \right \rfloor = 19. This is indeed the correct answer, as you can see in Table 4.