Prerequisiti:
- 1. Dai numeri primi ai tratteggi
- 2. Tratteggi, trattini e spazi: alcune definizioni e semplici proprietà
- 5. I tratteggi lineari di primo ordine
In questo articolo parleremo di una proprietà di tipo ricorsivo, che vale per tutti i tratteggi lineari con componenti a due a due coprime. Dato un tratteggio T di questo tipo, vedremo che ogni suo sottotratteggio proprio T^{\prime} può essere ritrovato “immerso” in T; inoltre, ricorsivamente, anche ogni sottotratteggio proprio T^{\prime \prime} di T^{\prime} può essere ritrovato “immerso” in T^{\prime}, e così via.
Nel caso più semplice, cioè in un tratteggio di secondo ordine (n_1, n_2) con n_1 ed n_2 coprimi, la proprietà consiste nel fatto che, se si guarda la riga di n_1 in corrispondenza dei trattini di componente n_2 lungo tutto un periodo, si presenta esattamente lo stesso schema del tratteggio di primo ordine (n_1), ossia n_1 - 1 spazi seguiti da un trattino. Inoltre, la proprietà è simmetrica, perché succede una cosa analoga se si guarda la riga di n_2 in corrispondenza dei trattini di componente n_1.
Poniamo n_1 := 4 ed n_2 := 5. Evidenziamo le celle della riga del 4 corrispondenti a trattini della riga del 5:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| – | – | – | – | – | – | |||||||||||||||
| – | – | – | – | – |
Nelle celle evidenziate si può notare l’alternanza di tre spazi con un trattino, esattamente quella del tratteggio (n_1) = (4).
Viceversa, se guardiamo le celle della riga del 5 corrispondenti a trattini della riga del 4, possiamo riconoscere l’alternanza di quattro spazi con un trattino, proprio come accade nel tratteggio (n_2) = (5):
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| – | – | – | – | – | – | |||||||||||||||
| – | – | – | – | – |
Osserviamo che l’ipotesi che le componenti siano coprime è essenziale. Ad esempio, se nel tratteggio (n_1, n_2) = (4, 6) evidenziamo le celle della riga del 4 corrispondenti a trattini della riga del 6, otteniamo la seguente tabella:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| – | – | – | – | – | – | – | ||||||||||||||||||
| – | – | – | – | – |
L’alternanza che possiamo leggere nelle celle evidenziate è spazio-trattino-spazio-trattino, che non corrisponde alla tabella del tratteggio (n_1) = (4).
Per inciso, non è un caso che l’alternanza osservata spazio-trattino-spazio-trattino sia quella che si osserverebbe in due periodi del tratteggio (2), dove 2 = \mathrm{MCD}(4, 6). Quest’osservazione può portare alla formulazione di una versione generalizzata della proprietà che stiamo studiando, ma per i nostri scopi al momento ci interessa solo il caso in cui le componenti sono a due a due coprime.
Questa proprietà vale anche per i tratteggi di ordini superiori. Ad esempio, in un tratteggio di terzo ordine (n_1, n_2, n_3) con n_1, n_2, n_3 a due a due coprimi:
- nelle righe di n_1 ed n_2, in corrispondenza dei trattini di componente n_3 lungo tutto il periodo che va da 1 a n_1 n_2 n_3, si presenta esattamente lo stesso schema del tratteggio di secondo ordine (n_1, n_2);
- nelle righe di n_1 ed n_3, in corrispondenza dei trattini di componente n_2 e nello stesso periodo, si presenta esattamente lo stesso schema del tratteggio di secondo ordine (n_1, n_3);
- nelle righe di n_2 ed n_3, in corrispondenza dei trattini di componente n_1 e nello stesso periodo, si presenta esattamente lo stesso schema del tratteggio di secondo ordine (n_2, n_3).
Consideriamo il tratteggio (n_1, n_2, n_3) := (2, 3, 5). Guardiamo le celle delle righe del 2 e del 3 corrispondenti a trattini della riga del 5:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| – | – | – | – | – | – | – | – | – | – | – | – | – | – | – | – | |||||||||||||||
| – | – | – | – | – | – | – | – | – | – | – | ||||||||||||||||||||
| – | – | – | – | – | – | – |
Si può notare che, unendo le celle evidenziate, si ottiene esattamente lo schema di un periodo del tratteggio (2, 3):
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| – | – | – | – | |||
| – | – | – |
Nei tratteggi di terzo ordine vi è anche un altro modo di osservare questa proprietà. Se, invece di partire dai trattini di una singola componente, si considerano le colonne che contengono i trattini di due componenti simultaneamente, guardando la riga della componente rimasta, sulle stesse colonne, si potrà leggere lo stesso schema del corrispondente tratteggio.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| – | – | – | – | – | – | – | – | – | – | – | – | – | – | – | – | |||||||||||||||
| – | – | – | – | – | – | – | – | – | – | – | ||||||||||||||||||||
| – | – | – | – | – | – | – |
Questa volta, unendo le celle evidenziate, si ottiene un periodo del tratteggio (5):
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| – | – |
In generale, per un tratteggio lineare T di ordine k \gt 1, la proprietà che si osserva è la seguente: scelto un sottoinsieme delle componenti di T contenente tra una e k - 1 componenti, prese all’interno di un periodo di T le colonne che contengono simultaneamente i trattini di tutte le componenti scelte, evidenziando su queste colonne le celle relative alle componenti scartate, ed infine unendo tutte le celle evidenziate colonna per colonna, si ottiene lo schema del tratteggio lineare le cui componenti sono quelle scartate.
Proviamo ad esprimere questa proprietà in termini più formali, procedendo per passi successivi:
Ricorsività dei sottotratteggi di un tratteggio lineare con componenti a due a due coprime
Sia T = (n_1, \ldots, n_k), con k \gt 1, un tratteggio lineare con componenti a due a due coprime. Si consideri il seguente algoritmo:
- Si scelgano h componenti, con 1 \leq h \leq k - 1. Siano i_1, \ldots, i_h gli indici di queste componenti, con \{i_1, \ldots, i_h\} \subset \{1, \ldots, k\}. Siano j_1, \ldots, j_{k - h} gli indici delle componenti scartate, ossia \{j_1, \ldots, j_{k - h}\} = \{1, \ldots, k\} \setminus \{i_1, \ldots, i_h\}.
- All’interno del periodo che va dalla colonna 1 alla colonna M := n_1 \cdot \ldots \cdot n_k, si individuino le colonne che contengono simultaneamente i trattini di tutte le componenti scelte (i numeri di queste colonne sono tutti e soli i multipli del prodotto delle componenti scelte che si trovano all’interno del periodo, ossia M^{\prime} := n_{i_1} \cdot \ldots \cdot n_{i_h}, 2M^{\prime}, 3M^{\prime}, \ldots, M).
- All’interno delle colonne così individuate, si evidenzino le celle che appartengono alle righe di indici j_1, \ldots, j_{k - h} (quelli delle componenti scartate).
- Si affianchino colonna per colonna tutte le celle evidenziate, ottenendo una nuova tabella.
La tabella ottenuta mediante questo algoritmo è quella che rappresenta il periodo del tratteggio (n_{j_1}, \ldots, n_{j_{k-h}}) avente come prima colonna 1 e come ultima colonna n_{j_1} \cdot \ldots \cdot n_{j_{k-h}}.
Innanzitutto, contiamo quante colonne sono considerate nel passo 2. Il loro numero è pari al numero di multipli di M^{\prime} := n_{i_1} \cdot \ldots \cdot n_{i_h} compresi tra 1 ed M := n_1 \cdot \ldots \cdot n_k. Questo numero a sua volta è pari a \left \lfloor \frac{M}{M^{\prime}} \right \rfloor (abbiamo parlato di questa formula nell’articolo sui tratteggi lineari di primo ordine). Svolgendo i calcoli, si ha che:
Ma questo è proprio il numero di colonne della tabella che rappresenta un qualunque periodo del tratteggio (n_{j_1}, \ldots, n_{j_{k-h}}), considerando che le componenti di questo tratteggio sono a due a due coprime, e quindi \mathrm{MCM}(n_{j_1}, \ldots, n_{j_{k-h}}) = n_{j_1} \cdot \ldots \cdot n_{j_{k-h}}. Quindi, almeno come numero di colonne, ci ritroviamo con la tesi: il numero di colonne evidenziate, che è pari al numero di colonne della tabella ottenuta nel passo finale dell’algoritmo, coincide con quello della tabella che rappresenta il periodo del tratteggio (n_{j_1}, \ldots, n_{j_{k-h}}) che va dalla colonna 1 alla colonna n_{j_1} \cdot \ldots \cdot n_{j_{k-h}}. D’ora in poi chiameremo quest’ultima tabella T_T (da “Tabella del Tratteggio”), mentre chiameremo la tabella ottenuta dall’algoritmo T_A (“Tabella dell’Algoritmo”). Resta quindi da dimostrare che le tabelle T_T e T_A sono proprio identiche, cioè coincidono cella per cella.
Per fare ciò, consideriamo un generico numero di riga r e un generico numero di colonna c e vediamo se le corrispondenti celle delle due tabelle coincidono. Naturalmente, per costruzione, ci sono dei limiti per r e c, in particolare r \in \{j_1, \ldots, j_{k-h}\} e c \in \{1, \ldots, n_{j_1} \cdot \ldots \cdot n_{j_{k - h}}\}. Osserviamo che questi sono tutti e soli i valori consentiti per r e c in entrambe le tabelle, perché esse hanno lo stesso numero di righe e lo stesso numero di colonne, ed iniziano entrambe dalla colonna 1. Quindi se dimostriamo che, qualunque siano r e c, la cella (r, c) di T_T coincide con la cella (r, c) di T_A, allora significa che le due tabelle sono identiche.
Vediamo quindi cosa contiene la cella (r, c) di T_T. Essendo questa la tabella che rappresenta un tratteggio lineare, per costruzione la cella (r, c) contiene un trattino se e solo se c è multiplo di n_r:
Vediamo cosa contiene invece la cella (r, c) di T_A. Per come è definito l’algoritmo, essa corrisponde alla cella (r, cM^{\prime}) del tratteggio (n_1, \ldots, n_k). Infatti, l’operazione che dà luogo alla tabella finale, nel passo 4, non cambia i numeri di riga, mentre affianca le colonne che in origine, nella tabella del tratteggio (n_1, \ldots, n_k), corrispondevano ai multipli di M^{\prime}. Così la colonna M^{\prime} diventa la colonna 1 di T_A, la colonna 2M^{\prime} diventa la colonna 2 di T_A, …, in generale la colonna cM^{\prime} diventa la colonna c di T_A. Quindi possiamo dire che, per come è definito l’algoritmo:
Ma a sua volta, per la costruzione della tabella del tratteggio (n_1, \ldots, n_k), la cella (r, cM^{\prime}) di questa tabella contiene un trattino se e solo se cM^{\prime} è multiplo di n_r:
Ora osserviamo che, essendo M^{\prime} il prodotto delle componenti n_{i_1}, \ldots, n_{i_h}, tra le quali non vi è n_r perché r \in \{j_1, \ldots, j_{k-h}\}, ed essendo n_1, \ldots, n_k a due a due coprimi, n_r è coprimo con M^{\prime}. Allora, se n_r \mid cM^{\prime}, non avendo n_r fattori primi comuni con M^{\prime}, esso deve necessariamente dividere c. Viceversa, se n_r \mid c, a maggior ragione n_r \mid cM^{\prime}. Abbiamo così dimostrato che:
Unendo le formule (1), (2), (3) e (4) otteniamo infine:
Abbiamo così dimostrato che la cella (r, c) di T_T contiene un trattino se e solo se la cella (r, c) di T_A contiene un trattino. Per arbitrarietà di r \in \{j_1, \ldots, j_{k-h}\} e di c \in \{1, \ldots, n_{j_1} \cdot \ldots \cdot n_{j_{k - h}}\}, questo conclude la dimostrazione.
Rileggiamo l’esempio precedente alla luce della Proprietà T.7:
- Abbiamo scelto h = 2 componenti, con indici (i_1, \ldots, i_h) = (i_1, i_2) = (1, 2). Gli indici delle componenti scartate costituiscono l’insieme \{j_1, \ldots, j_{k - h}\} = \{1, \ldots, k\} \setminus \{i_1, \ldots, i_h\} = \{1, 2, 3\} \setminus \{1, 2\} = \{3\}. Quindi \{j_1, \ldots, j_{k - h}\} = \{j_1\} = \{3\}.
- L’ultima colonna del periodo considerato è M := n_1 \cdot \ldots \cdot n_k = 2 \cdot 3 \cdot 5 = 30. Il prodotto delle componenti scelte è M^{\prime} := n_{i_1} \cdot \ldots \cdot n_{i_h} = n_1 \cdot n_2 = 2 \cdot 3 = 6. I numeri delle colonne che contengono simultaneamente i trattini di tutte le colonne scelte sono perciò M^{\prime}, 2M^{\prime}, 3M^{\prime}, \ldots, M = 6, 12, 18, 24, 30.
- All’interno delle colonne così individuate, abbiamo evidenziato le celle della terza riga, perché j_1 = 3 è l’indice dell’unica componente scartata.
- La tabella ottenuta è quella che rappresenta un periodo del tratteggio (n_{j_1}) = (n_3).