8. Calcolo della riga nei tratteggi lineari di secondo ordine

Prerequisiti:

Abbiamo visto che per risolvere il problema del downcast è necessario risolvere le cosiddette equazioni caratteristiche del downcast, che però presuppongono che si conosca a quale riga, o più in generale a quale sottotratteggio proprio, appartenga l’x-esimo trattino di un tratteggio, dato x. Può sembrare strano, ma è possibile calcolare la riga di un trattino senza avere idea di quale sia il suo valore. Infatti, come abbiamo visto nell’articolo introduttivo Da un problema sulla corsa ai tratteggi, il calcolo della riga ed il calcolo del valore di un trattino sono due problemi ben distinti. In questo articolo vedremo come si calcola la riga per i tratteggi lineari di secondo ordine, mentre successivamente vedremo come si calcola il valore, col metodo del downcast.

Calcolo della riga nei tratteggi lineari di secondo ordine

Indichiamo con T un tratteggio lineare di secondo ordine. Assumiamo per semplicità che le sue righe abbiano indici 1 e 2. Vogliamo trovare una condizione che caratterizza l’appartenenza del suo x-esimo trattino ad una specifica riga. È indifferente considerare la riga 1 o la riga 2 perché, se la condizione di appartenenza alla riga 1 non è soddisfatta, necessariamente il trattino appartiene alla riga 2, e viceversa; comunque, per fissare le idee, scegliamo la riga 1.

Si può dimostrare (v. Teoria dei tratteggi, pagg. 146-150) che l’appartenenza dell’x-esimo trattino di T alla riga 1 può essere desunta dal calcolo di un particolare modulo:

(n_1 x - 1) \mathrm{\ mod\ } (n_1 + n_2) \tag{1}

Vediamo quali valori assume questo modulo nel caso del tratteggio T = (3, 5). Nella rappresentazione grafica del tratteggio, scriviamo il valore della (1) in corrispondenza dell’x-esimo trattino. Otteniamo così la seguente figura:

Figura 1: Valori della funzione (n_1 x – 1) mod (n_1 + n_2) = (3x – 1) mod 8 per il tratteggio (3, 5), per i vari ordinali x

Possiamo notare che i valori più piccoli (da 0 a 4) si trovano sulla prima riga, mentre quelli più grandi (da 5 a 7) si trovano sulla seconda riga. Questo non è un caso. In generale si dimostra che l’x-esimo trattino appartiene alla riga 1 se e solo se il modulo (1) assume un valore più basso di n_2 (in questo caso n_2 = 5):

\mathrm{t}_T(x) \in T[1] \Leftrightarrow (n_1 x - 1) \mathrm{\ mod\ } (n_1 + n_2) \lt n_2 \tag{2}

È questo il motivo per cui il massimo modulo sulla prima riga è 4 = n_2 - 1. Negando questa condizione, abbiamo quella che caratterizza l’appartenenza alla seconda riga:

\mathrm{t}_T(x) \in T[2] \Leftrightarrow (n_1 x - 1) \mathrm{\ mod\ } (n_1 + n_2) \geq n_2 \tag{3}

È utile, per completare il quadro, analizzare di nuovo la questione dal punto di vista della riga 2. Se nella (1) consideriamo n_2 x al posto di n_1 x - 1, otteniamo un altro modulo significativo:

n_2 x \mathrm{\ mod\ } (n_1 + n_2) \tag{4}

Calcolando questo modulo per le varie x nel tratteggio precedente, si ottiene quanto segue:

Figura 2: Valori della funzione n_2 x mod (n_1 + n_2) = 5x mod 8 per il tratteggio (3, 5), per i vari ordinali x

La situazione mostrata è l’opposto di prima: ora sono i trattini della seconda riga (e non quelli della prima) che hanno i valori del modulo minori di n_1 (e non di n_2). In generale si ha che:

\mathrm{t}_T(x) \in T[2] \Leftrightarrow n_2 x \mathrm{\ mod\ } (n_1 + n_2) \lt n_1 \tag{5}

E di conseguenza

\mathrm{t}_T(x) \in T[1] \Leftrightarrow n_2 x \mathrm{\ mod\ } (n_1 + n_2) \geq n_1 \tag{6}

Sta a noi quindi decidere quale modulo utilizzare, se (1) o (4): in entrambi i casi si ottengono delle condizioni che caratterizzano l’appartenenza dell’x-esimo trattino ad entrambe le righe. Naturalmente, le formule (2) e (6), che stabiliscono entrambe l’appartenenza alla riga 1, e le formule (3) e (5), che stabiliscono l’appartenenza alla riga 2, devono essere equivalenti; la dimostrazione, in una forma un po’ più generale che vedremo tra poco, si trova in Teoria dei tratteggi, Lemma 6.1 pagg. 147-148.

Ora proviamo a scrivere le formule precedenti in una forma più generale. Indichiamo gli indici di riga del tratteggio con le lettere i e j, mediante la condizione che abbiamo visto nelle equazioni caratteristiche (in particolare nel Corollario 1 della Proposizione T.4), \{i, j\} = \{1, 2\}.
In questo modo il problema diventa stabilire una condizione per caratterizzare l’appartenenza dell’x-esimo trattino alla generica riga i (che può essere 1 o 2), indicando con j l’altra riga (rispettivamente, 2 o 1). Così le equazioni (2) e (5) si generalizzano con la singola equazione

\mathrm{t}_T(x) \in T[i] \Leftrightarrow (n_i x - (i \lt j)) \mathrm{\ mod\ } (n_i + n_j) \lt n_j \tag{2 + 5}

Qui abbiamo utilizzato la notazione abbreviata (i \lt j), grazie a cui si ottiene la (2) per i = 1 e la (5) per i = 2. Notiamo che in entrambi i casi n_i + n_j = n_1 + n_2 ma, dato che stiamo usando le lettere, per uniformità di scrittura preferiamo la notazione n_i + n_j.
Analogamente, le equazioni (3) e (6) possono essere generalizzare mediante la seguente:

\mathrm{t}_T(x) \in T[i] \Leftrightarrow (n_j x - (j \lt i)) \mathrm{\ mod\ } (n_i + n_j) \geq n_i \tag{3 + 6}

A partire da questa si ottiene infatti la (3) per i = 2 e la (6) per i = 1.

Possiamo enunciare quanto visto finora nel seguente Teorema:

Calcolo della riga dell’x-esimo trattino in un tratteggio lineare di secondo ordine

Sia T un tratteggio lineare di secondo ordine, avente insieme degli indici \{1, 2\}. Siano i e j tali che \{i, j\} = \{1, 2\}. Allora, per ogni x \gt 0:

\begin{aligned} \mathrm{t}_T(x) \in T[i] & \Leftrightarrow (n_i x - (i \lt j)) \mathrm{\ mod\ } (n_i + n_j) \lt n_j \\ & \Leftrightarrow (n_j x - (j \lt i)) \mathrm{\ mod\ } (n_i + n_j) \geq n_i \end{aligned} \tag{7}

In particolare, valgono le seguenti formule rispettivamente per le righe 1 e 2:

\begin{aligned} \mathrm{t}_T(x) \in T[1] & \Leftrightarrow (n_1 x - 1) \mathrm{\ mod\ } (n_1 + n_2) \lt n_2 \\ & \Leftrightarrow n_2 x \mathrm{\ mod\ } (n_1 + n_2) \geq n_1 \end{aligned} \tag{8}
\begin{aligned} \mathrm{t}_T(x) \in T[2] & \Leftrightarrow n_2 x \mathrm{\ mod\ } (n_1 + n_2) \lt n_1 \\ & \Leftrightarrow (n_1 x - 1) \mathrm{\ mod\ } (n_1 + n_2) \geq n_2 \end{aligned} \tag{9}
Il Teorema T.2 risponde alla nostra domanda iniziale, ossia a quale riga appartiene l’x-esimo trattino di un tratteggio lineare di secondo ordine T, senza però il calcolo esplicito della riga. Non abbiamo trovato, cioè, una funzione f(x) che, mediante calcoli algebrici, restituisce direttamente l’indice della riga di \mathrm{t}_T(x). Piuttosto, l’approccio è scegliere arbitrariamente un certo indice i, per esempio i = 1, e chiedersi: “\mathrm{t}_T(x) \in T[i]?”. La risposta è fornita dal Teorema T.2. Se è affermativa, vuol dire che effettivamente il trattino appartiene alla riga i; se è negativa, vuol dire che il trattino appartiene all’altra riga, che abbiamo indicato con j.

Applicando il Teorema T.2, stabiliamo a quale riga appartiene l’ottavo trattino del tratteggio (3, 5).

Verifichiamo se appartiene alla riga 1: applichiamo pertanto la formula (8) con (n_1, n_2, x) = (3, 5, 8), fermandoci alla prima forma delle due equivalenti, ottenendo:

\begin{aligned} \mathrm{t}_{(3, 5)}(8) \in T[1] & \Leftrightarrow (3 \cdot 8 - 1) \mathrm{\ mod\ } (3 + 5) \lt 5 \\ & \Leftrightarrow 23 \mathrm{\ mod\ } 8 \lt 5 \\ & \Leftrightarrow 7 \lt 5 \end{aligned}

La condizione è falsa: dunque l’ottavo trattino non appartiene alla prima riga, per cui, dovendo necessariamente appartenere a una delle due righe, appartiene alla seconda:

Figura 3: L’ottavo trattino del tratteggio lineare (3, 5) appartiene alla riga 2

Dall’immagine vediamo che, invece, il settimo trattino appartiene alla prima riga. Infatti, ripetendo i passaggi precedenti con x = 7, otteniamo una relazione vera:

\begin{aligned} \mathrm{t}_{(3, 5)}(7) \in T[1] & \Leftrightarrow (3 \cdot 7 - 1) \mathrm{\ mod\ } (3 + 5) \lt 5 \\ & \Leftrightarrow 20 \mathrm{\ mod\ } 8 \lt 5 \\ & \Leftrightarrow 4 \lt 5 \end{aligned}

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.