Prerequisito:
Aspetti generali
Uno dei problemi ancora aperti della teoria dei tratteggi è, dato un tratteggio lineare T = (p_1, p_2, \ldots p_k) di ordine k, trovare un’espressione che sia in grado di maggiorare la distanza tra uno spazio e quello immediatamente precedente. Ossia, date due colonne s_1 e s_2 di un tratteggio, che siano entrambe spazi, tali che s_1 \lt s_2, e che non ci sia nessun altro spazio tra di loro, lo scopo di quest’indagine è trovare h tale che s_2 - s_1 \leq h, per ogni possibile coppia di spazi consecutivi (s_1, s_2) del tratteggio considerato.
Sicuramente h esiste, dato che, ad esempio, un suo possibile valore è la massima distanza d tra gli spazi, che è stato il punto di partenza per quest’indagine. Per calcolarla, è sufficiente prendere tutte le coppie possibili di spazi vicini di un dato tratteggio, calcolare la distanza per ognuna di esse, e prendere quella massima. Il Visualizzatore di tratteggi, tra le altre informazioni che fornisce, visualizza anche la distanza massima tra gli spazi consecutivi, per cui lo si può usare come base per possibili indagini in tal senso.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
2 | — | — | — | — | — | — | — | ||||||
3 | — | — | — | — | — |
Le coppie di spazi consecutivi sono le seguenti:
- Colonne 1 e 5, la cui distanza è 5 – 1 = 4;
- Colonne 5 e 7, la cui distanza è 7 – 5 = 2;
- Colonne 7 e 11, la cui distanza è 11 – 7 = 4.
La terza coppia, in realtà, non è altro che la ripetizione della prima, ma era importante andare oltre il periodo del tratteggio, dato che, proprio in corrispondenza della colonna pari al periodo (ossia la 6), c’è a sua volta una coppia di spazi.
Per cui, date tutte le possibili coppie (s_1, s_2), si ha s_2 - s_1 \leq 4.
Quindi, è sicuramente vero che la maggiorazione si può trovare tramite un algoritmo (ossia una procedura fatta da una serie di passaggi), ma lo scopo di quest’indagine è cercare una formula.
Maggiorazione della massima distanza per tratteggi di primo ordine
I tratteggi di cui è più facile trovare una maggiorazione valida universalmente sono quelli di primo ordine, perché la loro struttura è estremamente regolare: un tratteggio T_1(p_1) di primo ordine, infatti, è sempre costituito dalla ripetizione di una sequenza formata da un trattino seguito da p_1 - 1 spazi.
Ad esempio, questo è il tratteggio T = (5) fino a 25:
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 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
5 | — | — | — | — | — | — |
Per cui, le possibili coppie di spazi consecutivi, non solo per questo tratteggio di esempio ma per uno qualsiasi di primo ordine, sono solo due:
- Uno spazio immediatamente seguito da un altro spazio (come le colonne 2 e 3 dell’esempio); la distanza tra questi spazi è 1;
- Uno spazio immediatamente seguito da un trattino, immediatamente seguito da un altro spazio (come le colonne da 4 a 6 dell’esempio); la distanza tra questi spazi è 2.
Per un tratteggio di primo ordine, quindi, vale questa Proprietà:
Maggiorazione della massima distanza massima tra spazi consecutivi per tratteggi di primo ordine
In un tratteggio di primo ordine, la massima distanza tra spazi consecutivi è 2.
Maggiorazione della massima distanza per tratteggi di secondo ordine
Il ragionamento precedente è applicabile anche ai tratteggi di secondo ordine, ma va considerato che la loro struttura è leggermente più complessa di quelli di primo ordine. Il punto di partenza sono alcune proprietà, che valgono appunto per i tratteggi di secondo ordine e sono diretta conseguenza della loro stessa struttura:
- Ogni colonna del tratteggio può non contenere trattini (ossia essere uno spazio), o contenerne uno in entrambe le righe, o uno nella prima riga, o uno nella seconda;
- La distanza minima tra due trattini della prima riga è 2, pari al più piccolo valore della prima componente;
- La distanza minima tra due trattini della seconda riga è 3, pari al più piccolo valore della seconda componente;
- Un trattino, nella riga in cui si trova, non può essere né immediatamente preceduto né seguito da un altro trattino: è diretta conseguenza delle due proprietà precedenti;
- Una colonna che contiene un trattino in entrambe le righe è sempre immediatamente preceduta e seguita da almeno uno spazio: è diretta conseguenza della proprietà precedente.
Per trovare la maggiorazione che cerchiamo, dobbiamo determinare qual è il numero massimo di trattini che possono trovarsi tra due spazi consecutivi, ossia, data una colonna s che sia uno spazio, va cercato il massimo valore d tale che le colonne s + 1, s + 2, \ldots, s + d - 1 sono trattini, ed s + d è un altro spazio. Analizziamo quindi i vari casi che si possono presentare per queste colonne intermedie:
- Il caso più semplice è quello in cui s + 1 rientra nel primo caso della proprietà A, ossia è uno spazio: in questo caso abbiamo uno spazio seguito immediatamente da un altro spazio, per cui d = 1.
- Oppure, s + 1 rientra nel secondo caso della proprietà A, ossia contiene trattini in entrambe le righe: in questo caso, per la proprietà E, è immediatamente preceduto e seguito da uno spazio, per cui anche s + 2 è uno spazio. Quindi abbiamo uno spazio, una colonna che non è uno spazio, e poi un altro spazio, per cui d = 2.
- Oppure, s + 1 rientra nel terzo caso della proprietà A, ossia contiene un trattino nella prima riga. Relativamente alla colonna successiva, ossia s + 2, la proprietà D ci garantisce che non può contenere un trattino nella prima riga, per cui possono presentarsi solo due sottocasi:
- La colonna s + 2 non contiene neanche un trattino nella seconda riga, per cui è uno spazio: quindi abbiamo uno spazio, seguito da due colonne che non sono spazi, seguite da un altro spazio, per cui d = 3.
- La colonna s + 2 contiene un trattino nella seconda riga. Relativamente alla colonna successiva, s + 3, la proprietà D ci garantisce che non può contenere un tratttino nella seconda riga, per cui possono presentarsi a loro volta solo due sottocasi:
- La colonna s + 3 non contiene neanche un trattino nella prima riga, per cui è uno spazio: quindi abbiamo uno spazio, seguito da due colonne che non sono spazi, seguite da uno spazio, per cui d = 3.
- Oppure, la colonna s + 3 contiene un trattino nella prima riga. In questo caso, la colonna s + 4 è sicuramente uno spazio: infatti, la proprietà D ci garantisce che tale colonna non può contenere un trattino nella prima riga; ma non può contenerne uno neanche nella seconda, perché, se così fosse, avremmo sia s + 2 che s + 4 con un trattino nella seconda riga, ossia due trattini della seconda riga con distanza 2, il che porterebbe a una contraddizione con la proprietà C. Quindi, abbiamo uno spazio, seguito da tre colonne che non sono spazi, seguite da un altro spazio, per cui d = 4.
- Oppure, s + 1 rientra nel quarto caso della proprietà A, ossia contiene un trattino nella seconda riga. Il ragionamento, in questo caso, è identico al precedente, ma con la prima riga al posto della seconda e viceversa.
Quindi, in totale, dato un qualsiasi spazio s del secondo ordine, si ha 1 \leq d \leq 4. Per cui, relativamente alla distanza massima possibile, vale la seguente Proprietà:
Maggiorazione della massima distanza massima tra spazi consecutivi per tratteggi di secondo ordine
In un tratteggio di secondo ordine, la massima distanza tra spazi consecutivi è 4.
Maggiorazione della massima distanza per tratteggi di terzo ordine
La conformazione dei tratteggi di terzo ordine è più complessa di quelli di ordini inferiori, il che di fatto impedisce di applicare lo stesso ragionamento precedente per arrivare a trovare una maggiorazione: in linea di principio sarebbe possibile farlo, ma le casistiche da verificare sarebbero in numero eccessivo. Per poter giungere a una maggiorazione valida, in questo caso, è necessario utilizzare strumenti di tipo più teorico, attraverso cui si arriva al seguente risultato:
Maggiorazione della distanza massima tra spazi consecutivi per tratteggi di terzo ordine
In un tratteggio di terzo ordine T = (n_1, n_2, n_3) con componenti coprime, la massima distanza possibile tra spazi consecutivi non può superare n_1 \cdot (n_3 + 4).
Il punto di partenza della dimostrazione è la Caratterizzazione C.3 (Spazi di un tratteggio del terzo ordine), che afferma che, dato il tratteggio T = (n_1, n_2, n_3) con componenti coprime, tutti gli spazi x che precedono un trattino della prima riga sono dati dalla seguente relazione:
dove
L’insieme P_T(1), che non è presente nella formulazione originaria ma figura nella relativa dimostrazione, viene reintrodotto qui per motivi di chiarezza.
La quantità n_1 n_2 + n_1 n_3 + n_2 n_3 corrisponde al numero totale di trattini, per cui, per chiarezza, definiamo un simbolo per rappresentarla:
Definiamo poi un insieme, che chiameremo X, contenente tutte le x che soddisfano la relazione precedente, che possiamo semplificare usando tot:
Il vincolo iniziale sulle x deriva dal fatto che esse sono trattini, e quindi, se si indica il primo con 0, l’ultimo vale sicuramente tot - 1.
Gli insiemi X e P_T(1) hanno entrambi cardinalità (n_2 - 1) \cdot (n_3 - 1), perché:
- P_T(1), per costruzione, ha cardinalità pari al prodotto di quelle degli insiemi \{2, \ldots, n_3\} e \{2, \ldots, n_2\}, ossia (n_3 - 1) \cdot (n_2 - 1);
- Il numero di resti ammessi per la divisione su cui si basa la definizione di X, per com’è definito, è pari alla cardinalità di P_T(1), per cui, di conseguenza, lo è anche il numero delle x ammesse.
Data ogni x \in \{0, \ldots, 30\}, tutti i 16 x \mathrm{\ mod\ } 31 corrispondenti sono i seguenti, in cui quelli appartenenti anche a P_T(1) sono sottolineati:
Prendendo solo gli elementi sottolineati, si ottiene appunto P_T(1).
La definizione di X permette di semplificare la caratterizzazione degli spazi per il terzo ordine. Indicando con S l’insieme degli spazi che precedono un trattino della prima riga, la caratterizzazione può essere riscritta in questo modo:
Dato che stiamo considerando solo i trattini della prima componente, la funzione \mathrm{t\_valore} risulta essere strettamente crescente, perché, prendendo solo la prima riga, a ogni trattino corrisponde un valore distinto di \mathrm{t\_valore}, ossia una diversa colonna. Se invece avessimo considerato più righe, ci sarebbe potuta essere la possibilità di avere più trattini nella stessa colonna, e quindi avrebbero potuto avere lo stesso \mathrm{t\_valore} in corrispondenza di due trattini diversi.
A partire dalla definizione di P_T(1), si osserva inoltre che esso può essere visto come l’unione di più insiemi, dato i \in \{2, \ldots n_3\}:
Questi insiemi sono sicuramente disgiunti per costruzione, e la loro unione è P_T(1), per cui, per definizione, \{A_2, \ldots A_{n_3}\} è una sua partizione, di cardinalità n_3 - 2.
Applichiamo lo stesso principio a X, definendo, per i \in \{2, \ldots n_3\}, gli insiemi
Anche questi insiemi, la cui unione è X per costruzione, sono disgiunti, per cui \{X_2, \ldots X_{n_3}\} è a sua volta una partizione di X, e ha anch’esso cardinalità n_3 - 2 per costruzione.
Ora che abbiamo ottenuto una partizione di X, possiamo usarla per crearne una di S: dato sempre i \in \{2, \ldots n_3\}, definiamo
In questo modo, dato che anche gli S_i sono disgiunti per costruzione, si ha che \{S_2, \ldots S_{n_3} \} è appunto una partizione di S, e ha anch’essa cardinalità n_3 - 2.
Passiamo ora ad analizzare gli insiemi X_i per i \in \{2, \ldots, n_3\}, definendo i seguenti simboli:
Gli Y_q appena definiti possono essere usati a loro volta per suddividere gli X_i: si osserva infatti che
Per come sono stati definiti gli y_j, la distanza tra y_j e y_{j + 1} è sempre \lfloor tot / n_2 \rfloor oppure \lceil tot / n_2 \rceil; tale equivalenza si dimostra attraverso le proprietà delle funzioni “parte intera” \lfloor x \rfloor e \lceil x \rceil.
Applichiamo al primo addendo della (2) la proprietà 2.21 presente in Teoria dei tratteggi, a pagina 66, che afferma che \lfloor (a + k) / b \rfloor = \lfloor a / b \rfloor + \lfloor (k + a \mathrm{\ mod\ } b) / b\rfloor, ponendo a := tot \cdot j, b := n_2 e k := tot:
Sostituendo il primo addendo della (2) con quello ottenuto in questo modo, si ha:
Applichiamo la proprietà 2.21 al membro a destra della (3), ponendo stavolta a := tot, b := n_2 e k := (tot \cdot j) \mathrm{\ mod\ } n_2:
In questo modo la (3) diventa
Il secondo addendo della (4) è una frazione, che ha per numeratore (tot \cdot j) \mathrm{\ mod\ } n_2 + tot \mathrm{\ mod\ } n_2, formato a sua volta da due addendi, (tot \cdot j) \mathrm{\ mod\ } n_2 e tot \mathrm{\ mod\ } n_2. Questi due addendi sono entrambi resti di una divisione per n_2, quindi devono per forza essere minori di n_2. Per cui, sommandoli, si ha:
Se riprendiamo a questo punto il secondo addendo della (4), possiamo quindi applicarvi la disuguaglianza
Dato che n_2 si può semplificare nella frazione, e che \lfloor 2 \rfloor = 2, questa disuguaglianza diventa
Il membro a sinistra di questa disuguaglianza è una parte intera, per cui sicuramente è un numero intero, quindi esso è un numero intero minore di 2, ossia può essere solo 0 oppure 1:
Combinando quest’ultima condizione con la (4), si ha:
ossia
Questo ci permette di completare la dimostrazione, sfruttando l’uguaglianza \lfloor x \rfloor + 1 = \lceil x \rceil, che vale quando x non è un numero intero. Nel nostro caso, infatti
e, dato che n_1, n_2 e n_3 sono coprìmi essendo componenti del tratteggio, n_1 \cdot n_3 / n_2 non può essere un numero intero (altrimenti il numeratore sarebbe divisibile per il denominatore, il che sarebbe possibile solo se numeratore e denominatore avessero divisori comuni), quindi neanche tot / n_2 lo è. Per cui si ha:
Per cui la (5) si può riscrivere in questo modo:
il che completa la dimostrazione.
Abbiamo quindi dimostrato che l’insieme Y è fatto di elementi distanziati quasi a intervalli regolari; proviamo ora a fare lo stesso ragionamento sugli insiemi X_i, per verificare se i loro elementi presentino regolarità simili.
per cui le y_j sono:
- y_0 = \lfloor (59 \cdot 0) / 5 \rfloor = 0;
- y_1 = \lfloor (59 \cdot 1 / 5 \rfloor = 11;
- y_2 = \lfloor (59 \cdot 2 / 5 \rfloor = 23;
- y_3 = \lfloor (59 \cdot 3 / 5 \rfloor = 35;
- y_4 = \lfloor (59 \cdot 4 / 5 \rfloor = 47;
per cui Y = \{0, 11, 23, 35, 47\}. Gli insiemi Y_j sono:
- Y_0 = Y \setminus \{y_0\} = \{11, 23, 35, 47\};
- Y_1 = Y \setminus \{y_1\} = \{0, 23, 35, 47\};
- Y_2 = Y \setminus \{y_2\} = \{0, 11, 35, 47\};
- Y_3 = Y \setminus \{y_3\} = \{0, 11, 23, 47\};
- Y_4 = Y \setminus \{y_4\} = \{0, 11, 23, 35\};
Gli insiemi A_i sono:
- A_2 = \{5 \cdot 2 + 7 \cdot b \mid b \in \{2, \ldots, 5\}\} = \{24, 31, 38, 45\};
- A_3 = \{5 \cdot 3 + 7 \cdot b \mid b \in \{2, \ldots, 5\}\} = \{29, 36, 43, 50\};
- A_4 = \{5 \cdot 4 + 7 \cdot b \mid b \in \{2, \ldots, 5\}\} = \{34, 41, 48, 55\};
- A_5 = \{5 \cdot 5 + 7 \cdot b \mid b \in \{2, \ldots, 5\}\} = \{39, 46, 53, 60\};
- A_6 = \{5 \cdot 6 + 7 \cdot b \mid b \in \{2, \ldots, 5\}\} = \{44, 51, 58, 65\};
- A_7 = \{5 \cdot 7 + 7 \cdot b \mid b \in \{2, \ldots, 5\}\} = \{49, 56, 63, 70\};
Gli X_i sono (considerando che i resti della divisione tra m e 59 possono andare solo da 0 a 58):
- X_2 = \{x \mid (5 + 7) \cdot 2 \cdot x \mathrm{\ mod\ } 59 \in A_2\} = \{1, 24, 36, 48\};
- X_3 = \{x \mid (5 + 7) \cdot 3 \cdot x \mathrm{\ mod\ } 59 \in A_3\} = \{7, 19, 31, 43\};
- X_4 = \{x \mid (5 + 7) \cdot 4 \cdot x \mathrm{\ mod\ } 59 \in A_4\} = \{2, 14, 26, 49\};
- X_5 = \{x \mid (5 + 7) \cdot 5 \cdot x \mathrm{\ mod\ } 59 \in A_5\} = \{9, 32, 44, 56\};
- X_6 = \{x \mid (5 + 7) \cdot 6 \cdot x \mathrm{\ mod\ } 59 \in A_6\} = \{15, 27, 39, 51\};
- X_7 = \{x \mid (5 + 7) \cdot 7 \cdot x \mathrm{\ mod\ } 59 \in A_7\} = \{10, 22, 34, 57\}.
Analizzando gli X_i, si nota come hanno una struttura quasi simile a quella degli y_j, ma con una particolarità. Nel caso degli y_j, la distanza tra y_{j + 1} e y_j era sempre uguale a \lfloor tot / n_2 \rfloor = \lfloor 59 / 5 \rfloor = 11 oppure a \lceil tot / n_2 \rceil = \lceil 59 / 5 \rfloor = 12, mentre quella tra un elemento di X_i e il successivo vale quasi sempre quanto uno di questo valori, tranne che in una coppia di elementi. Ad esempio, le distanza tra gli elementi consecutivi di X_2 sono le seguenti:
- 24 - 1 = 23;
- 36 - 24 = 12 = \lceil tot / n_2 \rceil;
- 48 - 36 = 12 = \lceil tot / n_2 \rceil.
La distanza tra il secondo elemento e il primo non segue la regola principale, dato che 23 non è né \lfloor tot / n_2 \rfloor né \lceil tot / n_2 \rceil; si può però osservare che è pari alla loro somma. Se quindi fosse aggiunto a ogni X_i l’elemento giusto, la regola sarebbe rispettata.
Per trovare qual è questo elemento mancante in ogni insieme, possiamo sfruttare la (1), dato che, com’è possibile verificare:
- X_2 = \{(1 + y) \mathrm{\ mod\ } 59 \mid y \in Y_1\};
- X_3 = \{(43 + y) \mathrm{\ mod\ } 59 \mid y \in Y_1\};
- X_4 = \{(26 + y) \mathrm{\ mod\ } 59 \mid y \in Y_1\};
- X_5 = \{(9 + y) \mathrm{\ mod\ } 59 \mid y \in Y_1\};
- X_6 = \{(4 + y) \mathrm{\ mod\ } 59 \mid y \in Y_0\};
- X_7 = \{(34 + y) \mathrm{\ mod\ } 59 \mid y \in Y_1\};
Se, per ogni insieme ottenuto, sostituissimo Y_q con \{y_q\}, otterremmo insiemi contenenti un solo elemento, che chiameremo m_i, che sono i seguenti:
- \{m_2\} = \{(1 + y) \mathrm{\ mod\ } 59 \mid y \in \{y_1\}\} = \{(1 + y_1) \mathrm{\ mod\ } 59\} = \{(1 + 11) \mathrm{\ mod\ } 59\} = \{12\};
- \{m_3\} = \{(43 + y) \mathrm{\ mod\ } 59 \mid y \in \{y_1\}\} = \{(43 + y_1) \mathrm{\ mod\ } 59\} = \{(43 + 11) \mathrm{\ mod\ } 59\} = \{54\};
- \{m_4\} = \{(26 + y) \mathrm{\ mod\ } 59 \mid y \in \{y_1\}\} = \{(26 + y_1) \mathrm{\ mod\ } 59\} = \{(26 + 11) \mathrm{\ mod\ } 59\} = \{37\};
- \{m_5\} = \{(9 + y) \mathrm{\ mod\ } 59 \mid y \in \{y_1\}\} = \{(9 + y_1) \mathrm{\ mod\ } 59\} = \{(9 + 11) \mathrm{\ mod\ } 59\} = \{20\};
- \{m_6\} = \{(4 + y) \mathrm{\ mod\ } 59 \mid y \in \{y_0\}\} = \{(4 + y_0) \mathrm{\ mod\ } 59\} = \{(4 + 0) \mathrm{\ mod\ } 59\} = \{4\};
- \{m_7\} = \{(34 + y) \mathrm{\ mod\ } 59 \mid y \in \{y_1\}\} = \{(34 + y_1) \mathrm{\ mod\ } 59\} = \{(34 + 11) \mathrm{\ mod\ } 59\} = \{45\}.
Come si può facilmente verificare, gli insiemi X_i \cup \{m_i\} sono tali che la distanza tra un loro elemento e il successivo è sempre 11 o 12, quindi gli m_i sono proprio gli elementi mancanti che stavamo cercando.
Per proseguire, definiamo un nuovo insieme, che indicheremo con M (“Mancanti”), che contiene tutti gli m_i trovati nell’esempio. Tale insieme, che nel caso dell’esempio è M = \{4, 12, 20, 37, 45, 54\}, presenta a sua volta una regolarità simile a quella vista negli X_i: se infatti calcoliamo la distanza tra un suo elemento e il successivo, otteniamo
- 12 - 4 = 8;
- 20 - 12 = 8;
- 37 - 20 = 17;
- 45 - 37 = 8;
- 54 - 45 = 9.
In questo caso, si vede come la distanza tra un elemento e il successivo sia 8 oppure 9, tranne che in un caso (tra 20 e 37), in cui è pari alla loro somma. La regola principale, in questo caso, si rivela essere che la distanza è quasi sempre pari a 8 = \lfloor 59 / 7 \rfloor = \lfloor tot / n_3 \rfloor oppure a 8 = \lceil 59 / 7 \rceil = \lceil tot / n_3 \rceil; in particolare, si osserva che tale distanza non è mai minore di \lfloor tot / n_3 \rfloor, che è un aspetto importante per il resto della dimostrazione.
necessitano di dimostrazioni formali, ma sono verificabili per un tratteggio qualsiasi, seguendo gli stessi passaggi visti nell’esempio.
Grazie a queste considerazioni intermedie, possiamo prendere il problema principale, ossia maggiorare la distanza tra gli elementi di S (gli spazi), e rivederlo sfruttando gli insiemi che abbiamo definito: il calcolo della massima distanza tra gli elementi consecutivi di S può infatti essere ricondotto, per come sono definiti S e X, al calcolo della massima distanza tra gli elementi consecutivi di X, che a sua volta è stato partizionato come \{X_2, \ldots, X_{n_3}\}.
Ripartiamo dalla (1), che ci permette, dati due opportuni k e q, di riscrivere X_i come
Definiamo inoltre un nuovo insieme, che chiameremo X'_i, formato a partire da X_i aggiungendovi l’elemento m_i:
Per la (7), possiamo quindi affermare che la distanza tra i suoi elementi è pari a \lfloor tot / n_3 \rfloor oppure a \lceil tot / n_3 \rceil, per cui quella massima possibile è \lceil tot / n_3 \rceil.
Per com’è definito X'_i, è anche vero che
A questo punto, passiamo ad analizzare la distanza tra gli elementi consecutivi di X, considerando il fatto che il tratteggio di partenza ha periodo tot, per cui anche gli elementi di X hanno lo stesso periodo: per questo, dati due elementi x_p e x_q = x_p + tot che vi appartengano, si ha x_p \mathrm{\ mod\ } tot = x_q \mathrm{\ mod\ } tot. Per questo motivo, l’analisi può essere portata avanti anche solo tra gli elementi di X fino a tot, e si parlerà, piuttosto che di elementi consecutivi, di elementi “ciclicamente consecutivi”, dato che si susseguono appunto in un ciclo, periodo dopo periodo.
Chiediamoci quindi, preso x \in X_2, quanto può valere la distanza massima tra due elementi ciclicamente consecutivi. Il fatto di riferirsi a X_2 invece che a X è una semplificazione sufficiente, dato che il ragionamento sarebbe identico se prendessimo ad esempio X_3 o un altro X_i qualsiasi.
Per proseguire, definiamo un nuovo insieme I, che contenga tutti gli interi ciclicamente consecutivi rispetto a un generico x \in X_2:
La cardinalità dell’insieme, che si può ricavare dalla definizione di X_2, è sicuramente \lfloor tot / n_2 \rfloor, quindi possiamo riscrivere l’espressione in questo modo:
Questo insieme è correlato al nostro X, infatti gli elementi ciclicamente consecutivi degli altri insiemi X'_3, \ldots, X'_{n_3}, per la (7), hanno una distanza pari a \lfloor tot / n_3 \rfloor oppure \lceil tot / n_3 \rceil, e questi insiemi, per come sono definiti, sono sicuramente disgiunti. Quindi, I contiene sicuramente un elemento di ognuno di essi, e tale elemento è unico, perché:
- Se I non contenesse un elemento di X'_3, allora, per com’è definito tale insieme, esisterebbe un suo elemento minore di x ed un altro maggiore di x + \lfloor tot/n_2\rfloor, e questi due elementi sarebbero tra loro distanti almeno x + \lfloor tot/n_2 \rfloor + 1 - (x-1) = \lfloor tot/n_2 \rfloor + 2 = \lceil tot/n_2 \rceil + 1 \gt \lceil tot/n_2 \rceil, e questo non è possibile, perché sarebbe maggiore della distanza ammessa;
- Se I contenesse più di un elemento di X'_3, questi elementi sarebbero distanti tra loro al più x + \lfloor tot/n_2 \rfloor - (x + 1) = \lfloor tot/n_2 \rfloor - 1 \lt \lfloor tot/n_2 \rfloor, e questo non è possibile, perché sarebbe minore della distanza ammessa;
- Lo stesso ragionamento è applicabile agli altri X'_i, variando l’indice.
Quindi, I contiene un elemento per ognuno degli X'_3, \ldots, X'_{n_3}, per cui contiene almeno tanti elementi quanti sono questi insiemi, ossia n_3 - 2:
Per la (9), dato che sicuramente X'_3 \cup \ldots \cup X'_{n_3} \subset X \cup M, questi n_3 - 2 elementi di I appartengono anche a X \cup M, per cui si ha
Cerchiamo poi un criterio per escludere da I gli elementi di M: per come sono definiti, sappiamo che essi hanno una distanza minima di \lfloor tot / n_3 \rfloor, per cui I, che è formato da \lfloor tot / n_2 \rfloor interi consecutivi, può contenere al massimo \lceil \lfloor tot / n_3 \rfloor / \lfloor tot / n_2 \rfloor \rceil elementi, dato che, in generale, un insieme di n interi consecutivi può contenere al massimo \lceil n / m \rceil multipli di un altro intero m.
Tramite questa relazione, possiamo trovare una maggiorazione per la cardinalità dell’insieme che contiene gli elementi di I che sono anche in X:
Passiamo alle cardinalità, tenendo presente che |A \cup B| = |A| + |B| - |A \cap B|:
Dato che X e M sono disgiunti, la loro intersezione è vuota, quindi la cardinalità dell’insieme a destra (che quindi di conseguenza è vuoto) è zero:
Scambiamo di posto i termini dell’uguaglianza e lasciamo a sinistra solo |I \cap X|:
Combiniamo questa relazione con la (11):
Abbiamo detto che I \cap M non può contenere più di \lceil \lfloor tot/n_3 \rfloor / \lfloor tot/n_2 \rfloor \rceil interi consecutivi, ossia che
Combiniamo questa disuguaglianza ottenuta con una particolare proprietà delle componenti dei tratteggi di terzo ordine, che è la seguente:
da cui:
da cui:
da cui, invertendo il segno della disuguaglianza e sostituendo nella relazione precedente relativa a |I \cap X|:
Quindi, gli elementi di I che sono anche in X sono almeno n_3 - 2 - \lceil n_3 / n_2 \rceil.
Ora possiamo calcolare la massima distanza tra un elemento di X e quello ciclicamente consecutivo, che è l’ultimo passaggio necessario per poter passare al calcolo della massima distanza tra gli spazi consecutivi. Per farlo, partiamo dall’ultimo elemento di I, che è x + \lfloor tot + n_2 \rfloor, e procediamo a ritroso fino ad arrivare al primo elemento e a superarlo: avremo, nell’ordine, x + \lfloor tot + n_2 \rfloor - 1, x + \lfloor tot + n_2 \rfloor - 2, fino a raggiungere quello ciclicamente consecutivo, che è
Quindi, la massima distanza tra un qualsiasi elemento x di X e quello ciclicamente consecutivo è la differenza tra i loro due valori:
Dato che n_2 e n_3 sono coprimi, n_3 /n_2 non è un numero intero, per cui vale la relazione \lfloor n_3 /n_2 \rfloor + 1 = \lceil n_3 /n_2 \rceil, quindi:
Ora che abbiamo calcolato la massima distanza possibile tra due qualsiasi elementi ciclicamente consecutivi di X, possiamo completare la dimostrazione, passando a calcolare quella tra spazi consecutivi. Torniamo alla definizione iniziale dell’insieme S degli spazi che precedono un trattino della prima riga di un tratteggio:
Prendiamo uno spazio qualsiasi s \in S, e il suo consecutivo s' \gt s. Allora, per com’è definito S, esisteranno x e y appartenenti a X tali che s = \mathrm{t\_valore}(x) − 1, e s' = \mathrm{t\_valore}(y) − 1. Dato che, nel nostro caso, la funzione \mathrm{t\_valore} è strettamente crescente (perché stiamo considerando solo i trattini della prima riga), la distanza tra s' e s è massima quando lo è quella tra y e x.
Ma la distanza massima tra x e y è uguale a D, da cui y \leq x + D, quindi si ha:
Essendo y \leq x + D, dato che \mathrm{t\_valore} è strettamente crescente nel nostro caso, si ha anche \mathrm{t\_valore}(y) \leq \mathrm{t\_valore}(x + D), quindi la relazione precedente diventa:
Applicando l’Ipotesi T.1 (Intervallo di valori possibili per una funzione di downcast di t dal terzo ordine al primo), sostituendo j = 2, k = 3, e n_i n_j + n_i n_k + n_j n_k = tot, determiniamo i valori estremi di \mathrm{t\_valore}(x) per la prima riga:
Facciamo lo stesso per \mathrm{t\_valore}(x + D); le relative formule sono identiche alle precedenti, ma con x + D al posto di x. Considerando tutte le combinazioni possibili, la distanza ottenuta nella (13) è massima quando il valore di \mathrm{t\_valore}(x + D) è il più alto possibile, e quando quello di \mathrm{t\_valore}(x) è il più basso possibile, ossia dobbiamo prendere
Ora, per terminare la dimostrazione basta partire dalla distanza \mathrm{t\_valore}(x + D) - \mathrm{t\_valore}(x), sostituire i due termini come sopra, in modo da massimizzare la distanza, ed effettuare i calcoli intermedi.
La frazione di sinistra non può essere un numero intero, dato che n_2, n_3 e tot sono coprimi, quindi possiamo sostituire \lceil \ldots \rceil con \lfloor \ldots \rfloor + 1, per cui la relazione precedente diventa
L’espressione tra parentesi, che risulta essere la differenza tra due parti intere, può essere maggiorata, applicando alcune proprietà della parte intera. Partiamo dal primo termine della differenza:
Applichiamo la proprietà 2.21 presente in Teoria dei tratteggi, a pagina 66, che afferma che \lfloor (a + k) / b \rfloor = \lfloor a / b \rfloor + \lfloor (k + a \mathrm{\ mod\ } b) / b\rfloor, ponendo a := n_2 \cdot n_3 \cdot D, k := n_2 \cdot n_3 \cdot x + n_2 + n_3 e b := tot:
Sicuramente \forall q : q \mathrm{\ mod\ } tot \leq tot, quindi:
Se k è un numero relativo, \lfloor a + k \rfloor = \lfloor a \rfloor + k, quindi:
In totale, da questa sequenza di calcoli si ottiene la seguente relazione, che riprende il primo termine della sottrazione presente nella (15):
da cui
Usando questa disuguaglianza, possiamo maggiorare la (15) in questo modo:
Usiamo la (12) per sostituire D con il suo valore:
Dato che \lfloor q \rfloor \leq q, quest’espressione si può a sua volta maggiorare con la seguente:
Analizziamo il termine -n_2 (n_3)^2 + 4 n_2 n_3 + (n_3)^2: si ha
(essendo n_2 \geq 3 per ipotesi, da cui -(n_2 - 1) \leq 2)
(essendo n_2 \geq 3 per ipotesi)
(dato che sicuramente p + q \gt p se q \gt 0)
(per definizione di tot)
In totale:
Usiamo questa relazione per maggiorare a sua volta la (16):
Combinandola con la (14) da cui siamo partiti, si ha:
Il risultato finale è quindi il seguente:
Ossia, la distanza massima tra un qualsiasi spazio s e il consecutivo s' è n_1 \cdot (n_3 + 4), che era la tesi iniziale da dimostrare.
Maggiorazione della massima distanza per tratteggi di ordine qualsiasi
Lo scopo finale di questo studio è trovare una maggiorazione che valga per tratteggi qualsiasi, per cui il passo successivo è analizzare quelli dal quarto ordine in su, in modo da coprire la parte mancante dell’analisi. Una possibile pista d’indagine è il fatto che la maggiorazione trovata per il terzo ordine, ossia n_1 \cdot (n_3 + 4), può essere vista come n_1 \cdot (n_k + 4) con k = 3. Vista in questo modo, prendendo k \in \{1, 2\}, la formula è valida anche per primo e secondo ordine, considerando che:
- In un tratteggio di primo ordine si ha n_k = n_1, per cui la maggiorazione varrebbe n_1 \cdot (n_1 + 4). Dato che n_1 \geq 2, vuol dire che il valore minimo della maggiorazione è 2 \cdot (2 + 4) = 12. Sappiamo che la distanza massima possibile per i tratteggi del primo ordine è 2, e sicuramente 2 \leq 12, quindi la maggiorazione data dalla formula è accettabile.
- In un tratteggio di secondo ordine si ha n_k = n_2, per cui la maggiorazione varrebbe n_1 \cdot (n_2 + 4). Dato che n_1 \geq 2 e n_2 \geq 3, vuol dire che il valore minimo della maggiorazione è 2 \cdot (3 + 4) = 14. Sappiamo che la distanza massima possibile per i tratteggi del secondo ordine è 4, e sicuramente 4 \leq 12, quindi la maggiorazione data dalla formula è accettabile anche in questo caso.