17. Maggiorazione della massima distanza tra spazi consecutivi

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.

Prendiamo il tratteggio T = (2, 3), limitandoci a rappresentarlo fino a 12. Questa semplificazione è sufficiente per i nostri scopi, dato che il tratteggio è periodico: visto che la sequenza degli spazi si ripete, anche le distanze tra di loro si mantengono le stesse per tutto il resto del tratteggio. La tabella del tratteggio è la seguente:

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:

  1. 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;
  2. La distanza minima tra due trattini della prima riga è 2, pari al più piccolo valore della prima componente;
  3. La distanza minima tra due trattini della seconda riga è 3, pari al più piccolo valore della seconda componente;
  4. 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;
  5. 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:

  1. 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.
  2. 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.
  3. 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:
    1. 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.
    2. 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:
      1. 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.
      2. 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.
  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:

(n_2 + n_3) \cdot n_1 x \mathrm{\ mod\ } (n_1 n_2 + n_1 n_3 + n_2 n_3) \in P_T(1)

dove

P_T(1) = \{n_2 a + n_3 b \mid a \in \{2, \ldots, n_3\}, b \in \{2, \ldots, n_2\}\}

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:

tot := n_1 n_2 + n_1 n_3 + n_2 n_3

Definiamo poi un insieme, che chiameremo X, contenente tutte le x che soddisfano la relazione precedente, che possiamo semplificare usando tot:

X := \{x \in \{0, \ldots, tot - 1\} \mid (n_2 + n_3) \cdot n_1 x \mathrm{\ mod\ } tot \in P_T(1) \}

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.
Il fatto che la cardinalità di X sia uguale a quella di P_T(1) necessita di una dimostrazione formale, ma è verificabile facilmente: dato ad esempio il tratteggio T = (2, 3, 5), si ha n_1 = 2, n_2 = 3, n_3 = 5, e tot = 2 \cdot 3 + 3 \cdot 5 + 2 \cdot 5 = 31. Gli insiemi P_T(1) e X sono:

P_T(1) = \{n_2 a + n_3 b \mid a \in \{2, \ldots, n_3\}, b \in \{2, \ldots, n_2\}\} = \\ \{3 a + 5 b \mid a \in \{2, \ldots, 5\}, b \in \{2, \ldots, 3\}\} = \{16,19,21,22,24,25,27,30\}
X = \{x \in \{0, \ldots, 30\} \mid (3 + 5) \cdot 2 x \mathrm{\ mod\ } 31 \in P_T(1) \} = \{x \in \{0, \ldots, 30\} \mid 16 x \mathrm{\ mod\ } 31 \in P_T(1) \}

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:

\{0,\underline{16},1,17,2,18,3,\underline{19},4,20,5,\underline{21},6,\underline{22},7,23,8,\underline{24},9,\underline{25},10,26,11,\underline{27},12,28,13,29,14,\underline{30},15\}

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:

S = \{\mathrm{t\_valore}(x) - 1 \mid x \in X\}

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\}:

A_i := \{n_2 \cdot i + n_3 \cdot b | b \in \{2, \ldots, n_2\} \}

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

X_i := \{x \mid (n_2 + n_3) \cdot n_1 x \mathrm{\ mod\ } tot \in A_i \}

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

S_i = \{\mathrm{t\_valore}(x) - 1 \mid x \in X_i\}

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:

y_j := \lfloor (tot \cdot j) / n_2 \rfloor \text{, per }j \in \{0, \ldots , n_2 - 1\}
Y := \{y_0, \ldots , y_{n_2 - 1} \} \text{, l'insieme di tutte le }y_j
Y_q := Y \setminus \{y_q\} \text{, per } q \in \{0, \ldots n_2 - 1\}

Gli Y_q appena definiti possono essere usati a loro volta per suddividere gli X_i: si osserva infatti che

\exists k \in \{0, \ldots , tot - 1\}, \exists q \in \{0, \ldots , n_2 - 1 \} \mid X_i = \{ (k + y) \mathrm{\ mod\ } tot \mid y \in Y_q \} \tag{1}
La relazione precedente necessita ancora di una dimostrazione formale per via teorica, ma è verificabile facilmente; tale verifica viene omessa per brevità, ma è sufficiente partire da un tratteggio di terzo ordine, trovare tot e determinare gli X_i.

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.

Per definizione di y_j, la distanza tra y_{j+1} e y_j è:

y_{j + 1} - y_j = \lfloor (tot \cdot (j + 1)) / n_2 \rfloor - \lfloor (tot \cdot j) / n_2 \rfloor = \lfloor (tot \cdot j + tot) / n_2 \rfloor - \lfloor (tot \cdot j) / n_2 \rfloor \tag{2}

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:

\lfloor (tot \cdot j + tot) / n_2 \rfloor = \lfloor tot \cdot j / n_2 \rfloor + \lfloor (tot + (tot \cdot j) \mathrm{\ mod\ } n_2) / n_2 \rfloor

Sostituendo il primo addendo della (2) con quello ottenuto in questo modo, si ha:

y_{j + 1} - y_j = \lfloor tot \cdot j / n_2 \rfloor + \lfloor (tot + (tot \cdot j) \mathrm{\ mod\ } n_2) / n_2 \rfloor -\lfloor (tot \cdot j) / n_2 \rfloor = \\ \lfloor (tot + (tot \cdot j) \mathrm{\ mod\ } n_2) / n_2 \rfloor \tag{3}

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:

\lfloor(tot + (tot \cdot j) \mathrm{\ mod\ } n_2) / n_2 \rfloor = \lfloor tot / n_2 \rfloor + \lfloor ((tot \cdot j) \mathrm{\ mod\ } n_2 + tot \mathrm{\ mod\ } n_2) / n_2 \rfloor

In questo modo la (3) diventa

y_{j + 1} - y_j = \lfloor tot / n_2 \rfloor + \lfloor ((tot \cdot j) \mathrm{\ mod\ } n_2 + tot \mathrm{\ mod\ } n_2) / n_2 \rfloor \tag{4}

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:

(tot \cdot j) \mathrm{\ mod\ } n_2 + tot \mathrm{\ mod\ } n_2 \lt 2 \cdot n_2

Se riprendiamo a questo punto il secondo addendo della (4), possiamo quindi applicarvi la disuguaglianza

\lfloor ((tot \cdot j) \mathrm{\ mod\ } n_2 + tot \mathrm{\ mod\ } n_2) / n_2 \rfloor \lt \lfloor (2 \cdot n_2) / n_2 \rfloor

Dato che n_2 si può semplificare nella frazione, e che \lfloor 2 \rfloor = 2, questa disuguaglianza diventa

\lfloor ((tot \cdot j) \mathrm{\ mod\ } n_2 + tot \mathrm{\ mod\ } n_2) / n_2 \rfloor \lt 2

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:

\lfloor ((tot \cdot j) \mathrm{\ mod\ } n_2 + tot \mathrm{\ mod\ } n_2) / n_2 \rfloor \in \{0, 1\}

Combinando quest’ultima condizione con la (4), si ha:

y_{j + 1} - y_j = \lfloor tot / n_2 \rfloor + \lfloor ((tot \cdot j) \mathrm{\ mod\ } n_2 + tot \mathrm{\ mod\ } n_2) / n_2 \rfloor \in \{\lfloor tot / n_2 \rfloor + 0, \lfloor tot / n_2 \rfloor + 1\}

ossia

y_{j + 1} - y_j \in \{\lfloor tot / n_2 \rfloor, \lfloor tot / n_2 \rfloor + 1\} \tag{5}

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

tot / n_2 = (n_1 \cdot n_2 + n_2 \cdot n_3 + n_1 \cdot n_3) / n2 = \\ n_1 \cdot n_2 / n2 + n_2 \cdot n_3 / n_2 + n_1 \cdot n_3 / n_2 = n_1 + n_3 + n_1 \cdot n_3 / n_2

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:

\lfloor tot / n_2 \rfloor + 1 = \lceil tot / n_2 \rceil

Per cui la (5) si può riscrivere in questo modo:

y_{j + 1} - y_j \in \{\lfloor tot / n_2 \rfloor, \lceil tot / n_2 \rceil\}

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.

Partiamo da un esempio: prendiamo il tratteggio T = (2, 5, 7) e vediamo come sono fatti gli X_i. Per questo tratteggio si ha tot = 2 \cdot 5 + 2 \cdot 7 + 5 \cdot 7 = 59, n_1 = 2, n_2 = 5 e n_3 = 7:

y_j := \lfloor (59\cdot j) / 5 \rfloor \text{, per }j \in \{0, \ldots , 4\}

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\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.

Le proprietà, verificate nell’esempio precedente, secondo cui:

x_{j + 1} - x_j \in \{\lfloor tot / n_2 \rfloor, \lceil tot / n_2 \rceil\}, x_q \in X_i \cup \{m_i\} \tag{6}
m_{i + 1} - m_i \in \{\lfloor tot / n_3 \rfloor, \lceil tot / n_3 \rceil\}, m_q \in M \tag{7}
m_{i + 1} - m_i \geq \lfloor tot / n_3 \rfloor, m_q \in M \tag{8}

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

X_i = \{ (k + y) \mathrm{\ mod\ } tot \mid y \in Y_q \}

Definiamo inoltre un nuovo insieme, che chiameremo X'_i, formato a partire da X_i aggiungendovi l’elemento m_i:

X'_i = X_i \cup \{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

X'_2 \cup \ X'_3 \cup \ldots \cup X'_{n_3} = X \cup M \tag{9}

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:

I := \{(x + 1) \mathrm{\ mod\ } tot, (x + 2) \mathrm{\ mod\ } tot, \ldots \mid 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:

I = \{(x + 1) \mathrm{\ mod\ } tot, \ldots, x + \lfloor tot / n_2 \rfloor \mathrm{\ mod\ } tot\}

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:

|I| \geq n_3 - 2 \tag{10}

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

|I \cap (X \cup M)| \geq n_3 - 2\tag {11}

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:

Iniziamo applicando la proprietà distributiva tra unione e intersezione:

I \cap (X \cup M) = (I \cap X) \cup (I \cap M)

Passiamo alle cardinalità, tenendo presente che |A \cup B| = |A| + |B| - |A \cap B|:

|I \cap (X \cup M)| = |I \cap X| + |I \cap M| - |(I \cap X) \cap (I \cap M)| = |I \cap X| + |I \cap M| - |I \cap X \cap M|

Dato che X e M sono disgiunti, la loro intersezione è vuota, quindi la cardinalità dell’insieme a destra (che quindi di conseguenza è vuoto) è zero:

|I \cap (X \cup M)| = |I \cap X| + |I \cap M|

Scambiamo di posto i termini dell’uguaglianza e lasciamo a sinistra solo |I \cap X|:

|I \cap X| = |I \cap (X \cup M)| - |I \cap M|

Combiniamo questa relazione con la (11):

|I \cap X| \geq n_3 - 2 - |I \cap M|

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

|I \cap M| \leq \lceil \lfloor tot/n_3 \rfloor / \lfloor tot/n_2 \rfloor \rceil

Combiniamo questa disuguaglianza ottenuta con una particolare proprietà delle componenti dei tratteggi di terzo ordine, che è la seguente:

\lceil \lfloor tot/n_3 \rfloor / \lfloor tot/n_2 \rfloor \rceil \leq \lceil n_3 / n_2 \rceil
Questa relazione necessita di una dimostrazione, ma è possibile verificarla facilmente, partendo da un qualsiasi tratteggio di terzo ordine e calcolando tot.

da cui:

|I \cap M| \leq \lceil \lfloor tot/n_3 \rfloor / \lfloor tot/n_2 \rfloor \rceil \leq \lceil n_3 / n_2 \rceil

da cui:

|I \cap M| \leq \lceil n_3 / n_2 \rceil

da cui, invertendo il segno della disuguaglianza e sostituendo nella relazione precedente relativa a |I \cap X|:

|I \cap X| \geq n_3 - 2 - \lceil n_3 / n_2 \rceil

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 è

x + \lfloor tot/n_2 \rfloor - (n_3 - 2 - \lceil n_3 /n_2 \rceil - 1) = x + \lfloor tot/n_2 \rfloor - n_3 + 3 + \lceil n_3 /n_2 \rceil

Quindi, la massima distanza tra un qualsiasi elemento x di X e quello ciclicamente consecutivo è la differenza tra i loro due valori:

D := (x + \lfloor tot/n_2 \rfloor - n_3 + 3 + \lceil n_3 /n_2 \rceil) - x = \lfloor tot/n_2 \rfloor - n_3 + 3 + \lceil n_3 /n_2 \rceil

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:

D = \lfloor tot/n_2 \rfloor - n_3 + 3 + \lceil n_3 /n_2 \rceil = \lfloor tot/n_2 \rfloor - n_3 + 3 + \lfloor n_3 /n_2 \rfloor + 1 = \\ \lfloor tot/n_2 \rfloor - n_3 + 4 + \lfloor n_3 /n_2 \rfloor \tag{12}

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:

S = \{\mathrm{t\_valore}(x) − 1 \mid x \in X \}

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:

s' - s = \mathrm{t\_valore}(y) − 1 - (\mathrm{t\_valore}(x) − 1) = \mathrm{t\_valore}(y) - \mathrm{t\_valore}(x)

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:

s' - s = \mathrm{t\_valore}(y) - \mathrm{t\_valore}(x) \leq \mathrm{t\_valore}(x + D) - \mathrm{t\_valore}(x) \tag{13}

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:

\mathrm{t\_valore}(x) = n_1 \cdot \Bigg \lceil \frac{n_2 \cdot n_3 \cdot x + n_2 + n_3}{tot} \Bigg \rceil
\mathrm{t\_valore}(x) = n_1 \cdot \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 + n_3}{tot} \Bigg \rfloor

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

\mathrm{t\_valore}(x + D) = n_1 \cdot \Bigg \lceil \frac{n_2 \cdot n_3 \cdot (x + D) + n_2 + n_3}{tot} \Bigg \rceil
\mathrm{t\_valore}(x) = n_1 \cdot \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 + n_3}{tot} \Bigg \rfloor

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.

Partiamo da

\mathrm{t\_valore}(x + D) - \mathrm{t\_valore}(x) = \\ n_1 \cdot \Bigg \lceil \frac{n_2 \cdot n_3 \cdot (x + D) + n_2 + n_3}{tot} \Bigg \rceil - n_1 \cdot \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 + n_3}{tot} \Bigg \rfloor \tag{14}

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

n_1 (\cdot \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot (x + D) + n_2 + n_3}{tot} \Bigg \rfloor + 1) - n_1 \cdot \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 + n_3}{tot} \Bigg \rfloor =
n_1 \cdot \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot (x + D) + n_2 + n_3}{tot} \Bigg \rfloor + n_1 - n_1 \cdot \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 + n_3}{tot} \Bigg \rfloor =
n_1 \cdot \Bigg ( \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot (x + D) + n_2 + n_3}{tot} \Bigg \rfloor - \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 + n_3}{tot} \Bigg \rfloor \Bigg ) + n_1 \tag{15}

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:

\Bigg \lfloor \frac{n_2 \cdot n_3 \cdot (x + D) + n_2 + n_3}{tot} \Bigg \rfloor = \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 \cdot n_3 \cdot D + n_2 + n_3}{tot} \Bigg \rfloor = \\ \Bigg \lfloor \frac{(n_2 \cdot n_3 \cdot x + n_2 + n_3) + (n_2 \cdot n_3 \cdot D)}{tot} \Bigg \rfloor

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:

\Bigg \lfloor \frac{(n_2 \cdot n_3 \cdot x + n_2 + n_3) + (n_2 \cdot n_3 \cdot D)}{tot} \Bigg \rfloor = \\ \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot D}{tot} \Bigg \rfloor + \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 \cdot n_3 + (n_2 \cdot n_3 \cdot D) \mathrm{\ mod\ } tot}{tot} \Bigg \rfloor

Sicuramente \forall q : q \mathrm{\ mod\ } tot \leq tot, quindi:

\Bigg \lfloor \frac{n_2 \cdot n_3 \cdot D}{tot} \Bigg \rfloor + \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 \cdot n_3 + (n_2 \cdot n_3 \cdot D) \mathrm{\ mod\ } tot}{tot} \Bigg \rfloor \leq \\ \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot D}{tot} \Bigg \rfloor + \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 \cdot n_3 + tot}{tot} \Bigg \rfloor = \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot D}{tot} \Bigg \rfloor + \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 \cdot n_3}{tot} + 1 \Bigg \rfloor

Se k è un numero relativo, \lfloor a + k \rfloor = \lfloor a \rfloor + k, quindi:

\Bigg \lfloor \frac{n_2 \cdot n_3 \cdot D}{tot} \Bigg \rfloor + \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 \cdot n_3}{tot} + 1 \Bigg \rfloor = \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot D}{tot} \Bigg \rfloor + \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 \cdot n_3}{tot} \Bigg \rfloor + 1

In totale, da questa sequenza di calcoli si ottiene la seguente relazione, che riprende il primo termine della sottrazione presente nella (15):

\Bigg \lfloor \frac{n_2 \cdot n_3 \cdot (x + D) + n_2 + n_3}{tot} \Bigg \rfloor \leq \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot D}{tot} \Bigg \rfloor + \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 \cdot n_3}{tot} \Bigg \rfloor + 1

da cui

\Bigg \lfloor \frac{n_2 \cdot n_3 \cdot (x + D) + n_2 + n_3}{tot} \Bigg \rfloor - \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 \cdot n_3}{tot} \Bigg \rfloor \leq \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot D}{tot} \Bigg \rfloor + 1

Usando questa disuguaglianza, possiamo maggiorare la (15) in questo modo:

n_1 \cdot \Bigg ( \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot (x + D) + n_2 + n_3}{tot} \Bigg \rfloor - \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot x + n_2 + n_3}{tot} \Bigg \rfloor \Bigg ) + n_1 \leq \\ n_1 \cdot \Bigg ( \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot D}{tot} \Bigg \rfloor + 1 \Bigg ) + n_1

Usiamo la (12) per sostituire D con il suo valore:

n_1 \cdot \Bigg ( \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot (\lfloor tot/n_2 \rfloor - n_3 + 4 + \lfloor n_3 /n_2 \rfloor)}{tot} \Bigg \rfloor + 1\Bigg ) + n_1

Dato che \lfloor q \rfloor \leq q, quest’espressione si può a sua volta maggiorare con la seguente:

n_1 \cdot \Bigg ( \Bigg \lfloor \frac{n_2 \cdot n_3 \cdot (tot/n_2 - n_3 + 4 + n_3 /n_2)}{tot} \Bigg \rfloor + 1\Bigg ) + n_1 =
n_1 \cdot \Bigg \lfloor \frac{n_3 tot - n_2 (n_3)^2 + 4 n_2 n_3 + (n_3)^2)}{tot} \Bigg \rfloor + 2n_1 \tag{16}

Analizziamo il termine -n_2 (n_3)^2 + 4 n_2 n_3 + (n_3)^2: si ha

-n_2 (n_3)^2 + 4 n_2 n_3 + (n_3)^2 = (n_3)^2 \cdot (n_2 - 1) + 4 n_2 n_3 \leq

(essendo n_2 \geq 3 per ipotesi, da cui -(n_2 - 1) \leq 2)

-2 (n_3)^2 + 4 n_2 n_3 \lt

(essendo n_2 \geq 3 per ipotesi)

-2 n_2 n_3 + 4 n_2 n_3 = 2 n_2 n_3 \lt

(dato che sicuramente p + q \gt p se q \gt 0)

2 (n_2 n_3 + n_1 n_2 + n_1 n_3) =

(per definizione di tot)

2 \cdot tot

In totale:

-n_2 (n_3)^2 + 4 n_2 n_3 + (n_3)^2 \leq 2 \cdot tot

Usiamo questa relazione per maggiorare a sua volta la (16):

n_1 \cdot \Bigg \lfloor \frac{n_3 tot - n_2 (n_3)^2 + 4 n_2 n_3 + (n_3)^2)}{tot} \Bigg \rfloor + 2n_1 \leq n_1 \cdot \Bigg \lfloor \frac{n_3 tot + 2 \cdot tot}{tot} \Bigg \rfloor + 2n_1

Combinandola con la (14) da cui siamo partiti, si ha:

\mathrm{t\_valore}(x + D) - \mathrm{t\_valore}(x) \leq n_1 \cdot \Bigg \lfloor \frac{n_3 \cdot tot + 2 \cdot tot}{tot} \Bigg \rfloor + 2n_1 = \\ n_1 \cdot \Bigg \lfloor \frac{(n_3 + 2) \cdot tot}{tot} \Bigg \rfloor + 2n_1 = \\ n_1 \cdot \lfloor n_3 + 2 \rfloor + 2n_1 = (\text{dato che }\lfloor q \rfloor = q)\\ n_1 \cdot (n_3 + 2) + 2n_1 = \\ n_1 \cdot n_3 + 2n_1 + 2n_1 = \\ n_1 \cdot n_3 + 4n_1 = \\ n_1 (n_3 + 4)

Il risultato finale è quindi il seguente:

s' - s \leq n_1 \cdot (n_3 + 4)

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.
Se si volesse trovare una maggiorazione per la massima distanza tra spazi consecutivi in un tratteggio lineare generico, seguendo l’approccio della dimostrazione per il terzo ordine, bisognerebbe prima cercare una formula generale per \mathrm{t\_valore}. Questo è un punto aperto della teoria dei tratteggi, ma è possibile che la formula per il terzo ordine possa valere anche per gli ordini superiori, ampliandola con ulteriori termini, presumibilmente dipendenti dalle componenti dalla quarta in poi. Un possibile modo di procedere per la generalizzazione della formula, attualmente in fase di studio, è spiegato in una pagina dedicata.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *