4. Da un problema sulla corsa ai tratteggi

Prerequisito:

Il problema

Carlo, Maria e Tommaso sono tre amici che amano la corsa. Oggi sono andati a correre tutti e tre insieme, ma questo capita raramente. Infatti ognuno dei tre segue un proprio ritmo, diverso da quello degli altri: Carlo corre ogni tre giorni, Maria ogni quattro giorni e Tommaso ogni cinque. Perciò le prossime volte correranno da soli: Carlo tra tre giorni, Maria tra quattro e Tommaso tra cinque, poi Carlo e Maria correranno di nuovo, rispettivamente tra sei e tra otto giorni, e così via. I primi tra i tre che correranno di nuovo insieme saranno proprio Carlo e Maria, tra dodici giorni.

La situazione descritta è visualizzabile con un tratteggio: si tratta del tratteggio lineare (3, 4, 5):

Tabella 1: rappresentazione grafica di un problema sulla corsa mediante un tratteggio
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 \ldots
Carlo \ldots
Maria \ldots
Tommaso \ldots

L’interpretazione della tabella è molto semplice: le colonne rappresentano i giorni ed i trattini su ciascuna colonna indicano chi correrà quel giorno. Quindi leggiamo che oggi, giorno 0, corrono tutti e tre; domani e dopodomani, giorni 1 e 2, non correrà nessuno; il giorno 3 correrà solo Carlo; …; il giorno 20 correranno Maria e Tommaso.

Possiamo porci alcune domande:

  • Abbiamo detto che il primo che correrà di nuovo sarà Carlo, la seconda sarà Maria ed il terzo Tommaso… ma dato un qualunque numero intero positivo x, a partire da domani chi sarà l’x-esimo che correrà in ordine di tempo, a parità di giorno, in ordine alfabetico?
  • La persona che risponde al precedente quesito, tra quanti giorni correrà?
  • Ci sono dei giorni in cui non corre nessuno dei tre: il primo sarà domani, il secondo dopodomani, il terzo tra sette giorni… ma in generale quale sarà l’x-esimo di questi giorni?

La teoria dei tratteggi è pensata proprio per rispondere a questo genere di domande. Vediamo come.

Prima domanda: chi sarà l’x-esimo che correrà a partire da domani. Per rispondere con un metodo esclusivamente grafico, ordiniamo i trattini della Tabella 1 come segue:

Tabella 2: chi sarà l’x-esimo che correrà?
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 \ldots
Carlo 1 4 6 8 10 13 \ldots
Maria 2 5 9 12 14 \ldots
Tommaso 3 7 11 15 \ldots

Qui vediamo chiaramente che il primo che correrà di nuovo sarà Carlo, seguito da Maria e Tommaso, poi di nuovo Carlo e Maria, poi ancora Carlo, e così via: così, guardando il nome della riga a sinistra, abbiamo le risposte alla prima domanda, al variare di x. Ma, guardando invece i numeri di colonna, possiamo rispondere contemporaneamente anche alla seconda domanda (l’x-esima persona che correrà, tra quanti giorni lo farà). Ad esempio, cercando nella tabella il numero 7, che si trova sulla riga di Tommaso e sulla colonna 10, possiamo affermare che il settimo che correrà sarà Tommaso, ed egli correrà tra 10 giorni. Quindi la Tabella 2 ci permette di rispondere alle prime due domande: la risposta alla prima domanda è il nome della riga e la risposta alla seconda domanda è il numero di colonna.
Vi è poi il caso particolare di quando più persone corrono lo stesso giorno: ad esempio il dodicesimo giorno correranno sia Carlo che Maria. Prima di quel giorno, l’evento che qualcuno dei tre amici è andato a correre si è verificato 7 volte, come si può vedere nella tabella; per cui Carlo e Maria sono, presi insieme, l’ottava e la nona persona. Ma, dato che corrono lo stesso giorno, chi dei due è l’ottavo e chi è il nono? Abbiamo la risposta leggendo attentamente la prima domanda: “A partire da domani, chi sarà l’x-esimo corridore in ordine di tempo e, a parità di giorno, in ordine alfabetico?”. Se due o più persone corrono lo stesso giorno, dobbiamo contarle in ordine alfabetico: in questo caso Carlo è l’ottavo e Maria è la nona, semplicemente perché la C viene prima della M. Infatti, non a caso le righe delle Tabelle 1 e 2 sono ordinate dall’alto verso il basso secondo l’ordine alfabetico dei tre amici: in questo modo l’ordine delle persone che corrono lo stesso giorno corrisponde all’ordine delle righe, dall’alto verso il basso; in altri termini, se in una colonna vi sono più numeri, essi sono disposti in ordine crescente dall’alto verso il basso, come accade per le colonne 12, 15 e 20.
Tenendo conto contemporaneamente dell’ordine dei giorni e dell’ordine alfabetico all’interno di uno stesso giorno, potete facilmente ottenere la Tabella 2 dalla Tabella 1 leggendo quest’ultima per colonne, da destra verso sinistra e dall’alto verso il basso, numerando i trattini nell’ordine in cui li incontrate. È questo il senso della Definizione T.4 (Ordinamento dei trattini).

Passiamo all’ultima domanda: l’x-esimo giorno in cui non corre nessuno. Con riferimento alla rappresentazione di un tratteggio, come la Tabella 1, sappiamo che questi particolari giorni corrispondono agli spazi (Definizione T.3), ossia alle colonne che non contengono trattini. Per rispondere alla domanda basta ordinare gli spazi secondo il loro valore numerico: ciò corrisponde a contarli man mano che li troviamo leggendo la tabella da sinistra verso destra:

Tabella 3: quale sarà l’x-esimo giorno in cui non corre nessuno?
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 \ldots
Carlo 1 2 3 4 5 6 7 8 \ldots
Maria \ldots
Tommaso \ldots

Vediamo così che il primo giorno in cui non corre nessuno è il giorno 1 (domani), il secondo giorno è il giorno 2, il terzo è il giorno 7, il quarto è il giorno 11, e così via: così, guardando la Tabella 3, siamo in grado di rispondere alla terza domanda.

La formulazione matematica

Le tre domande che ci siamo posti sono tra i principali oggetti di studio della teoria dei tratteggi. Per affrontare questo studio in modo matematico, introduciamo le seguenti funzioni:

  • La funzione \mathrm{t}(x), che associa ad x l’x-esimo trattino, che sarà del tipo (1, n) se esso si trova sulla prima riga (quella di Carlo), del tipo (2, n) se si trova sulla seconda riga (quella di Maria), del tipo (3, n) se si trova sulla terza riga (quella di Tommaso).
  • La funzione \mathrm{t\_valore}(x), che associa ad x il valore (cioè la colonna) dell’x-esimo trattino.
  • La funzione \mathrm{t\_spazio}(x), che associa ad x l’x-esimo spazio.

Queste tre funzioni sono legate alle tre domande come segue:

  • La risposta alla prima domanda si trova nel numero di riga del trattino restituito dalla funzione \mathrm{t}(x). In particolare, posto \mathrm{t}(x) = (i, n), se i = 1 significa che la x-esima persona che correrà sarà Carlo, se i = 2 sarà Maria e se i = 3 sarà Tommaso.
  • La risposta alla seconda domanda è il risultato di \mathrm{t\_valore}(x).
  • La risposta alla terza domanda è il risultato di \mathrm{t\_spazio}(x).

Le funzioni \mathrm{t} e \mathrm{t\_valore} sono strettamente connesse: infatti \mathrm{t\_valore}(x) è il valore dell’x-esimo trattino, che a sua volta è \mathrm{t}(x). Ricordiamo a questo proposito che il valore di un trattino è dato dalla funzione tratteggio, che in questo caso, per il tratteggio T = (3, 4, 5), è

T(i, n) = \begin{cases} 3n & \text{se $i = 1$}\\4n & \text{se $i = 2$}\\5n & \text{se $i = 3$}\end{cases} \tag{1}

Allora, riassumendo, possiamo dire che vale la seguente uguaglianza:

\mathrm{t\_valore}(x) = T(x\text{-esimo trattino}) = T(\mathrm{t}(x))

Possiamo quindi considerare \mathrm{t\_valore}(x) una notazione semplificata, al posto di T(\mathrm{t}(x)).

A titolo di esempio, vediamo quali sono i primi valori delle tre funzioni, per x = 1, 2, 3, 4, 5, \ldots, nel tratteggio che abbiamo preso in esame:

  • \mathrm{t}(x): (1, 1), (2, 1), (3, 1), (1, 2), (2, 2), \ldots
  • \mathrm{t\_valore}(x): 3, 4, 5, 6, 8, \ldots
  • \mathrm{t\_spazio}(x): 1, 2, 7, 11, 13, \ldots

In questo caso è chiaro che le funzioni che abbiamo introdotto si riferiscono al tratteggio (3, 4, 5), perché è l’unico che abbiamo considerato fin dall’inizio. In generale però, ogni volta che occorre esplicitare il fatto che le funzioni \mathrm{t}, \mathrm{t\_valore} e \mathrm{t\_spazio} si riferiscono ad un determinato tratteggio T, le denotiamo come \mathrm{t}_T(x), \mathrm{t\_valore}_T(x) e \mathrm{t\_spazio}_T(x). Ecco le loro definizioni formali.

Funzione \mathrm{t}

Sia T un tratteggio di ordine k. Si definisce la funzione \mathrm{t}_T(x): \mathbb{N}^{\star} \rightarrow \{1, \dots, k\} \times \mathbb{N}:

\mathrm{t}_T(x) := x\text{-esimo trattino di }T

Si conviene che, quando si vuole dire che la funzione \mathrm{t}_T ha una certa proprietà P che vale per ogni tratteggio T, o per nessun tratteggio T, si dice brevemente “la funzione \mathrm{t} ha la proprietà P“, o “la funzione \mathrm{t} non ha la proprietà P“, per indicare che “la funzione \mathrm{t}_T ha la proprietà P, per ogni T“, o “la funzione \mathrm{t}_T non ha la proprietà P, per ogni T“.

Funzione \mathrm{t\_valore}

Sia T un tratteggio. Si definisce la funzione \mathrm{t\_valore}_T(x): \mathbb{N}^{\star} \rightarrow \mathbb{N}:

\mathrm{t\_valore}_T(x) := T(\mathrm{t}_T(x)) = \text{valore dell'}x\text{-esimo trattino di }T

Si usano le espressioni “\mathrm{t\_valore} ha la proprietà P” o “\mathrm{t\_valore} non ha la proprietà P” con un significato analogo a quello previsto dalla Definizione T.7.

Funzione \mathrm{t\_spazio}

Sia T un tratteggio. Si definisce la funzione \mathrm{t\_spazio}_T(x): \mathbb{N}^{\star} \rightarrow \mathbb{N}:

\mathrm{t\_spazio}_T(x) := x\text{-esimo spazio di }T

Si usano le espressioni “\mathrm{t\_spazio} ha la proprietà P” o “\mathrm{t\_spazio} non ha la proprietà P” con un significato analogo a quello previsto dalla Definizione T.7.

La soluzione

Abbiamo visto che per risolvere il problema iniziale occorre calcolare le funzioni \mathrm{t}, \mathrm{t\_valore} e \mathrm{t\_spazio}. Il calcolo di queste funzioni per qualsiasi tratteggio è uno dei problemi principali della teoria dei tratteggi. Al momento sono note le formule che calcolano le funzioni \mathrm{t} e \mathrm{t\_valore} per qualsiasi tratteggio lineare fino al terzo ordine, e la funzione \mathrm{t\_spazio} per qualsiasi tratteggio lineare fino al secondo ordine. Approfondiremo questi argomenti in articoli specifici ma, per avere un’idea, vediamo quali formule valgono per il tratteggio T = (3, 4, 5), in modo da avere delle risposte alle domande che ci siamo posti inizialmente.

Cominciamo dalla funzione \mathrm{t}(x). Abbiamo visto che essa calcola l’x-esimo trattino, che possiamo indicare con la coppia (i, n), cioè poniamo \mathrm{t}(x) = (i, n). Le formule della teoria dei tratteggi permettono di calcolare prima solo i e poi, sulla base di questo, anche n.
Per calcolare i, si procede sostanzialmente per tentativi: esiste una formula specifica per verificare se un determinato valore di i è quello giusto. Essendo i il numero di riga, il numero di valori possibili è pari al numero di righe del tratteggio, ossia il suo ordine. In questo caso i \in \{1, 2, 3\} perché il tratteggio T = (3, 4, 5) è di terzo ordine, e le formule sono le seguenti:

i = 1 \iff \begin{array}{c} 27 x \text{ ha lo stesso resto modulo } 47 \text{ di uno degli elementi dell'insieme } \\ \{9, 14, 19, 24, 13, 18, 23, 28, 17, 22, 27, 32, 21, 26, 31, 36, 25, 30, 35, 40\} \end{array} \tag{2}
i = 2 \iff \begin{array}{c} 32 x \text{ ha lo stesso resto modulo } 47 \text{ di uno degli elementi dell'insieme } \\ \{5, 10, 15, 8, 13, 18, 11, 16, 21, 14, 19, 24, 17, 22, 27\} \end{array} \tag{3}
i = 3 \iff \begin{array}{c} 35 x \text{ ha lo stesso resto modulo } 47 \text{ di uno degli elementi dell'insieme } \\ \{0, 4, 8, 3, 7, 11, 6, 10, 14, 9, 13, 17\} \end{array} \tag{4}

Nelle formule (2), (3) e (4), i numeri sono ottenuti in funzione delle componenti del tratteggio, come segue:

  • 47 = 3 \cdot 4 + 3 \cdot 5 + 4 \cdot 5
  • 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\}\}

Ora proviamo a fare i conti, ad esempio con x = 12.

Vediamo se i = 1, applicando la formula (2). Abbiamo che 27 \cdot 12 \mathrm{\ mod\ } 47 = 324 \mathrm{\ mod\ } 47 = 42. Nessuno degli elementi dell’insieme della formula (2), diviso per 47, dà resto 42, perciò i \neq 1.
Vediamo allora se i = 2, applicando la formula (3). Abbiamo che 32 \cdot 12 \mathrm{\ mod\ } 47 = 384 \mathrm{\ mod\ } 47 = 8. L’insieme riportato nella (3) contiene il numero 8, il cui resto modulo 47 è sempre 8, quindi i = 2. A questo punto possiamo fermarci, perché un solo valore di i è possibile. Volendo, comunque, si può calcolare anche la formula (4) e verificare che i \neq 3.

Avendo stabilito che i = 2, sappiamo che il dodicesimo trattino si trova sulla riga 2, come è possibile verificare nella Tabella 2. Questo risultato, rapportato al problema, significa che la dodicesima persona che correrà sarà quella della seconda riga, cioè Maria. Abbiamo ottenuto quindi la risposta alla prima domanda.

Ora che conosciamo il valore di i, possiamo calcolare il valore di n, per completare il calcolo della funzione \mathrm{t}. A questo proposito esistono diverse formule, più o meno complesse e più o meno esatte. Applichiamo qui la seguente formula esatta:

n = \left \lceil \frac{3 \left \lceil \frac{35x - 5}{47} \right \rceil}{7} \right \rceil \tag{5}

In questa formula, i numeri 35 e 47 sono stati ottenuti come prima, 3 è la più piccola componente del tratteggio, 7 è la somma delle prime due componenti. Inoltre il 5 che compare al numeratore della frazione più interna corrisponde con una delle componenti del tratteggio solo per una coincidenza, infatti è stato calcolato a partire dalle prime due componenti con la formula 3 \cdot 4 - (3 + 4).

Facendo i conti con x = 12, abbiamo che 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. Quindi, essendo i = 2 ed n = 4, possiamo dire che il dodicesimo trattino è \mathrm{t}(12) = (2, 4).

Ora che abbiamo calcolato il dodicesimo trattino, possiamo calcolare il suo valore mediante la funzione tratteggio data dalla (1):

\mathrm{t\_valore}(x) = T(\mathrm{t}(x)) = T(2, 4) = 4 \cdot 4 = 16

Questa è la risposta alla seconda domanda: la dodicesima persona che correrà, lo farà tra 16 giorni.

Una nota per i più curiosi: se volete potete provate le formule (2), (3) e (4) per diversi valori di x, anche molto grandi, per verificare la loro correttezza. La formula (5) però vale solo per i = 2, mentre in generale n è dato da:

n = \begin{cases} \left \lceil \frac{4 \left \lceil \frac{35x - 5}{47} \right \rceil + 1}{7} \right \rceil & \text{se $i = 1$}\\\left \lceil \frac{3 \left \lceil \frac{35x - 5}{47} \right \rceil}{7} \right \rceil & \text{se $i = 2$}\\\left \lceil \frac{5 \left \lceil \frac{32x - 7}{47} \right \rceil}{8} \right \rceil & \text{se $i = 3$}\end{cases}

Tra l’altro questa non è l’unica formula esatta possibile, ma vedremo le altre in articoli specifici.

Per quanto riguarda l’ultima domanda, cioè il calcolo dell’x-esimo spazio, ancora non esiste una formula generale per i tratteggi di terzo ordine, ma solo fino al secondo. Perciò rispondiamo ad una versione semplificata della domanda, ristretta ai primi due amici: quale sarà l’x-esimo giorno in cui non correranno né Carlo, né Maria? Le risposte sono visualizzate nella tabella seguente:

Tabella 4: quale sarà l’x-esimo giorno in cui non correranno né Carlo, né Maria?
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 \ldots
Carlo 1 2 3 4 5 6 7 8 9 10 \ldots
Maria \ldots

Stiamo quindi considerando il tratteggio di secondo ordine (3, 4). In questo caso la soluzione del problema è data dalla seguente formula:

\mathrm{t\_spazio}(x) = \begin{cases} \left \lfloor \frac{3 \frac{8x}{6} - 1}{2} \right \rfloor & \text{se $6 \mid x$}\\ \left \lfloor \frac{3 \left \lfloor \frac{8\left(x - \left \lfloor \frac{x}{6} \right \rfloor \right) - 3}{5} \right \rfloor - 1}{2} \right \rfloor & \text{altrimenti}\end{cases}

In questa formula, 3 e 4 sono le componenti del tratteggio, ed i numeri 5, 8 e 6 sono ottenuti dalle componenti come segue:

  • L’8 del primo caso è dato da \frac{(3 - 1)\mathrm{MCM}(3, 4)}{3}
  • 6 = (3 - 1)(4 - 1)
  • 5 = (3 - 1)(4 - 1) - 1
  • L’8 del secondo caso è dato da (3 - 1)4

Facciamo i conti con x = 10. Il numero 10 non è un multiplo di 6, perciò dobbiamo applicare la formula del secondo caso. Sostituendo abbiamo: \mathrm{t\_spazio}(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. Questa è proprio la risposta corretta, come si può vedere nella Tabella 4.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.