In questo articolo daremo, a tempo debito, la soluzione del quiz sul furto degli alberi. Lo scopo è principalmente quello di calcolare l'area del materiale espulso durante un'esplosione stellare estremamente suggestiva, come si vede in Fig. 1.

Una strana esplosione stellare

Essa, in fondo, è solo e soltanto un poligono molto particolare estremamente complesso.

Potremmo dire di usare la pazienza e di suddividere il poligono in tanti triangoli, calcolare la loro area e poi sommarli tutti assieme. Per calcolare l'area, però, sarebbe necessario conoscere le basi e le altezze di ogni triangolo... un bel lavoraccio, senza contare che dovremmo conoscere le coordinate di ogni singolo vertice dei triangoli.

I poligoni di Eulero

Partiamo, perciò, da Eulero e da una delle sue molteplici formule. Di questa abbiamo già parlato QUI, ma adesso la introduciamo in un modo un po' diverso, ricordando brevemente cosa sono i grafi planari. Sappiamo tutti cos'è un grafo: un insieme di punti del piano (vertici) più o meno connessi tra di loro da linee (lati). In particolare si definisce grafo planare un grafo in cui tutti i vertici sono connessi da lati, ma nessun lato si interseca con un altro al di fuori degli stessi vertici

Facciamo qualche esempio, considerando 4 vertici in Fig. 2.

Quelli a sinistra sono grafi non planari, in quanto vi sono lati che si intersecano in punti che non sono vertici (punti rossi). Quelli a destra, invece, sono grafi planari dato che tutti i lati non si intersecano fuori dai vertici.  In generale, molti grafi non planari diventerebbero planari cambiando uno o più lati, sempre tali da connettere due vertici senza intersecarsi. Per i nostri scopi, però, occupiamoci di grafi sicuramente planari: i poligoni semplici.

Ogni poligono concavo o convesso può, essere considerato un grafo planare, in cui i vertici e i lati sono quelli del poligono.

Iniziamo con il poligono più semplice, ossia il triangolo.

Quanti vertici ha? Ovviamente tre. Quanti lati? nuovamente tre. Introduciamo anche le facce del poligono. Una faccia è quella interna al poligono e un'altra faccia è quella esterna al poligono, ossia  2 facce.

Scriviamo l'espressione:

vertici - lati + facce = 3 - 3 + 2 = 2

Questa formula vale per qualsiasi poligono che corrisponda a un grafo planare. Non è difficile da comprendere dato che il numero dei lati è sempre uguale al numero dei vertici e le facce sono sempre due. D'ora in poi indicheremo con v i vertici, con l i lati e con f le facce.

Tuttavia, la formula sarebbe ancora applicabile se connettessimo tra loro anche qualche vertice non adiacente. Esso sarebbe ancora un grafo planare, dato che nessun lato ne intersecherebbe un altro. Ciò che cambierebbe sarebbe il numero di lati e di facce, poiché è considerata faccia ogni poligono interno chiuso.

In Fig. 3a i vertici sono 7, i lati sono 7, mentre le facce sono 2 (ricordiamo che deve essere considerata come faccia anche tutta la parte esterna al grafo).

v - l + f = 7 - 7 + 2 = 2

Ma allo stesso risultato porta la Fig. 3b. I vertici sono sempre 7, ma i lati sono 11 e le facce  6, per cui:

v - l + f = 7 = 7 - 11 + 6 = 2

Senza andare oltre, possiamo considerare come acquisita questa semplice formula. In particolare, ribadiamo che ogni poligono semplice può essere diviso in un certo numero di triangoli, soddisfacendo sempre la formula di Eulero.

Costruiamo un reticolo di punti

Eulero si è mostrato ancora un genio, ma la sua formula sembra avere poco a che fare con le aree dei poligoni.

Cambiamo un po' le cose...  Introduciamo un reticolo nel piano x, y tracciando tutte le rette x = n e y = n, con n numero intero positivo. Ogni punto di questo reticolo può essere considerato un vertice e ogni linea che ne congiunge due può essere considerato un lato. Disegniamo, in Fig. 4, un poligono che abbia come vertici solo punti del reticolo, ossia che abbiano coordinate pari a numeri interi positivi.

Vediamo come poterne calcolare l'area. Il modo concettualmente più semplice sarebbe quello di dividere il poligono in tanti triangoli, calcolarne l'area e poi sommarle tutte assieme. Il reticolo appena costruito ci permette, inoltre, di calcolare facilmente le aree dei triangoli in cui dividere il poligono. Questi triangoli sono chiamati triangoli minimi, ossia hanno come vertici punti del reticolo, ma non hanno punti del reticolo al loro interno o sui loro lati. I triangoli minimi hanno una caratteristica fondamentale: la loro area è sempre uguale a 1/2 (l'unità è il quadratino di lato unitario). La Fig. 5 ci aiuta a dimostrare questo fatto e mostra come qualsiasi triangolo minimo (rosa) abbia proprio l'area pari a 1/2.

Notiamo che nei due casi in basso, basta costruire un parallelogramma di area 3 e poi togliere i due triangoli azzurri di area 1, per ottenere che l'area del triangolo primitivo (rosa) è uguale a 1/2.

La faccenda, allora, diventa molto semplice... basta dividere il poligono nei suoi triangoli minimi, contare quanti ce ne sono e moltiplicare questo numero per 1/2. Questa conclusione permette di ricavare una formula ancora più semplice per l'area totale del poligono, senza bisogno di fare la divisione in triangoli minimi, dato che sappiamo che questa divisione è sempre possibile.

Da Eulero a Pick

Eulero ci direbbe che il poligono di Fig. 4 soddisfa la sua formula:

v - l + f = 2

Ogni triangolo minimo può essere considerato come faccia . Il nostro poligono deve , perciò, contenere (f - 1) triangoli minimi, dato che la formula di Eulero considera come faccia anche la parte del piano esterna al poligono.

Ogni triangolo ha tre lati per cui il numero di lati è pari a 3(f - 1). Tuttavia, ogni lato è contato due volte, tranne quelli (lc) del bordo esterno del poligono. Possiamo perciò scrivere la relazione:

3(f -1) + lc = 2l

Essa ci dice che il numero totale di lati dei triangoli più il numero di lati del contorno del poligono è  proprio uguale a due volte il numero di lati dell'intero poligono.

3f - 3 + lc = 2l

Togliamo 2f da entrambi i membri

f - 3 + lc = 2l - 2f

f = 2(l - f) - lc + 3

ricordiamo la formula di Eulero

v - l + f = 2

ossia:

l - f = v - 2

per cui:

f = 2(v - 2) - lc + 3

Ma v è il numero di punti del reticolo all'interno del poligono e sul contorno), dato che i triangoli minimi devono avere come vertici tutti i punti interni più i vertici del contorno. Chiamiamo i i vertici interni al poligono e b i vertici del contorno, ossia:

v = i + b

I lati lc del contorno sono sempre uguali al numero dei vertici del contorno, ossia:

lc = b

sostituendo abbiamo:

f = 2(v - 2) - lc + 3 = 2( i + b - 2) - b + 3 = 2i + 2b - 4 - b + 3 = 2i + b -1

Togliamo 1 da entrambi i membri:

f - 1 = 2i + b - 2

Ricordiamo che f - 1 è proprio il numero di triangoli minimi, per cui sappiamo anche che l'area totale del poligono è uguale al numero di triangoli minimi moltiplicato per l'area del singolo triangolo che è sempre uguale a 1/2. Ne consegue che:

A = 1/2(f - 1) = 1/2(2i + b - 2)

A = i + b/2 - 1

che è  la già nota formula di Pick, che avevamo presa per buona QUI.

Essa dice che l'area di un poligono è uguale al numero dei punti del reticolo interni al poligono più la metà dei punti del reticolo sul contorno, meno il numero uno.

Un poligono esplosivo

E' arrivata l'ora di occuparci della nostra esplosione stellare. Essa ha come vertici solo punti del reticolo, per cui è teoricamente piuttosto facile calcolarne l'area, anche se non è proprio banale riconoscere tutti i vertici se la stella ha troppe ... punte. Teoricamente basterebbe contare tutti i suoi vertici, che determinano il contorno, e applicare la formula di Pick, notando che i  suoi vertici sono tutti punti del reticolo e che il punto interno al contorno è uno e uno solo. La Fig. 6  mostra una stella  "meno esplosiva", che, comunque, contiene 96 vertici.

A = i + b/2 - 1 = 1 + v/2 - 1 = v/2

Tuttavia, è facile accorgersi di ovvie simmetrie, per cui Il poligono completo è facilmente divisibile in 8 parti uguali, quindi è sufficiente calcolare l'area della parte tra y = x e l'asse delle x positive (parte rosa) per ricondursi al poligono finale. Chiamiamo questa parte Parte Fondamentale (PF).

La PF ha v vertici. La sua area (rosa) è data da

A_PF= 0 + v/2 - 1 = v/2 - 1

8·A_PF = 8(v/2 - 1)

Aggiungiamo l'area del quadrato di 4 unità centrale la cui area è 4

Atot = 4v - 8 + 4 = 4(v - 1)

Ne segue che per ricavare l'area totale, basta conoscere solo i vertici della sua PF. Abbiamo ridotto il numero di vertici da contare, ma si può fare ancora meglio: basta sapere cosa rappresentano e quanti sono in funzione della stella da trattare.

Costruiamo l'esplosione

Per descrivere la procedura da seguire, abbandoniamo per un attimo la geometria e passiamo alla matematica e ai numeri frazionari compresi tra 0 e 1.

Ricordiamo che i numeri frazionari sono del tipo a/b dove a e b sono numeri interi e b≠0. Tra 0 e 1 esistono solo numeri frazionari in cui a deve essere minore di b, dato che il risultato deve essere minore di 1. Il denominatore indica le parti in cui vogliamo dividere l'intervallo tra o e 1, mentre il numeratore dice quante parti vogliamo considerare. Inoltre, vogliamo solo frazioni ridotte, ossia semplificate... Ad esempio la frazione 2/4 equivale alla frazione 1/2 (ossia, numeratore e denominatore sono coprimi, cioè senza divisore comune oltre a 1)

Consideriamo come massimo denominatore il 6. Otteniamo le seguenti frazioni: 1/6, 2/6, 3/6, 4/6, 5/6  a cui dobbiamo aggiungere lo 0 scritto come 0/1 e l'uno scritto come 1/1

Dobbiamo però semplificare alcune frazioni, ottenendo:

0/1, 1/6, 1/3, 1/2, 2/3, 5/6, 1/1

Sono veramente tutte le frazioni comprese tra 0 e 1, quando il denominatore massimo consentito è 6? Beh... no. L'intervallo 0-1 può infatti essere diviso anche in 5, 4, 3, e 2 parti che danno le frazioni

1/5, 2/5, 3/5 e 4/5

1/4, 2/4, 3/4 = 1/4, 1/2, 3/4         1/2 è già stato considerato

1/3, 2/3          entrambe sono già state considerate

1/2                  già considerata

Rimangono perciò

0/1, 1/6,  1/3,  1/2,  2/3,  5/6, 1/5, 2/5, 3/5,  4/5, 1/4, 3/4, 1/1

Per il denominatore massimo uguale a 6, abbiamo ottenuto 13 frazioni, ma dobbiamo ancora sistemarle in ordine crescente (un aiuto in tal senso verrebbe dato esprimendo le frazioni con denominatore pari al minimo comune multiplo e mettendo in ordine crescente solo il numeratore). A questo punto possiamo disegnare  il poligono che ha per vertici consecutivi le frazioni appena trovate, considerando il denominatore come ascissa e il numeratore come ordinata.

Chiamiamo la sequenza di frazioni con il simbolo F6, che prende il nome di Sequenza di Farey di ordine 6

F6 = 0/1⁠_, ⁠1/6⁠_, ⁠1/5⁠_, ⁠1/4⁠_, ⁠1/3⁠_, ⁠2/5⁠_, ⁠1/2⁠_, ⁠3/5⁠_, ⁠2/3⁠_, ⁠3/4⁠_, ⁠4/5⁠_, ⁠5/6⁠_, ⁠1/1

che permette di costruire la PF di Fig. 7.

Una sequenza di questo tipo può essere calcolata per ogni numero intero positivo n.

Una sua caratteristica interessante è anche dovuta al fatto che per passare dall'ordine n all'ordine n+ 1 è  necessario inserire soltanto le frazioni ridotte con denominatore n+1.

Nel caso dell'ordine 6 i vertici sono 13  e l'area dell'esplosione stellare di ordine 6 diventa:

A6 = 4(F6 - 1) = 4(12) = 48 unità

In generale

An = 4(Fn - 1)

Questa formuletta ci permette di conoscere l'area dell'esplosione stellare senza bisogno di disegnare la figura corrispondente e cercare punti nel disegno. Ad esempio, per la nostra grande esplosione stellare è facile capire che il denominatore più grande della sequenza è 10 e la sua PF è riportata in Fig. 8 (l'unità è pari alla lunghezza tra l'origine a il punto di coordinate (1,,0) oppure (0,1), ossia l'inizio della PF rossa).

Basta allora  calcolare F10 e l'area è presto data da:

A10 = 4(F10  - 1)

Per chi volesse saperlo (ma può provare a fare i calcoli da solo) posso dire che F10 = 33

A10 = 4 · 32 = 128 unità

Prima di dare la risposta al problema del furto degli alberi, facciamo un minimo di "gossip" scientifico.

Farey... chi era costui?

La sequenza porta con sé un "nome" del tutto sbagliato. In realtà, lo scopritore è stato, nel 1802, Charles Haros. Il suo lavoro, però, passò praticamente inosservato. John Farey, un geologo inglese, la ritrovò, intorno al 1816, a causa del  suo interesse al suono e alla matematica ad esso collegata e si fece carico di scrivere una lettera alla comunità scientifica che la richiamava. Il celebre matematico francese Augustine Cauchy lesse la lettera e  studiò la sequenza con grande interesse pensando che Farey fosse proprio lo scopritore e chiamandola, perciò, sequenza di Farey. Oggi, essa è fondamentale nella teoria dei numeri e ha applicazioni interessantissime nell'approssimazione dei numeri irrazionali, ma anche nei ritmi musicali, nella fisica delle risonanze e perfino negli ingranaggi degli orologi.

Oggi, per noi, ha grande importanza per riuscire a scoprire un furto di alberi.

Soluzione del furto degli alberi

La soluzione degli alberi rubati utilizza perfettamente la sequenza di Farey di ordine 6.  E' proprio lei a indicarci gli alberi che non possono essere rubati, mentre gli altri punti del reticolo (e quindi gli alberi) rimangono invisibili all'osservatore posto in O e possono essere trafugati senza problemi.

Il perché capiti questa situazione è molto semplice e dipende dal fatto che si sono semplificate tutte le frazioni che avevano divisori comuni tra numeratore e denominatore..

In Fig. 9, in rosso gli alberi non rubati, corrispondenti alla sequenza di Farey di ordine 6, mentre i punti vuoti sono gli alberi rubati.

La coltivazione di alberi originaria è formata da 48 alberi (49 meno il punto di osservazione). Il che corrisponde a due volte la PF a cui si deve togliere il punto (1,1), in comune  alle due PF considerate. Ne segue che gli alberi rubati sono 23.

alberi rubati = 48 - (2FP₆ - 1) = 48 - 25  = 23

P.S.: Su alcuni siti internet si trovano già calcolate le sequenze di Farey, ma è molto meglio mettersi alla prova da soli. Che ne dite di una bella esplosione di ordine 1000 ?!