Problema 1

Calcolare il massimo numero di parti nelle quali un piano può essere diviso da \(n\) rette.

SOLUZIONE 1.1

Una condizione necessaria è che le n rette devono intersecarsi a due a due e non ci siano tre rette con un punto in comune.
Si può ragionare per induzione:  una volta disegnate k rette, vediamo come un’ulteriore retta aumenta il numero di parti. La (k+1)-esima retta deve incontrare ognuna delle k rette già tracciate, ottenendo k punti di intersezione distinti, che dividono la retta aggiunta  in k+1 parti. Quindi la (k+1)-esima retta taglia esattamente k+1 delle parti nelle quali il piano era già diviso: ognuna di queste parti viene divisa in due e quindi il numero di parti aumenta di k+1.
Indicato con \(R_{n}\) il numero cercato, possiamo scrivere la seguente equazione di ricorrenza:

\[ R_{n} = R_{n-1} + n \]

con la condizione iniziale \(R_{2}=4\).
Per risolvere la ricorrenza, utilizziamo gli strumenti del calcolo delle differenze finite. Si trova prima la soluzione generale dell’equazione omogenea \(R_{n} – R_{n-1}=0\), che in questo semplice caso ha come soluzione una costante; quindi si cerca una soluzione particolare con il metodo dei coefficienti indeterminati. Si prova con un polinomio di secondo grado \(p(n)= a n^{2}+ bn + c\). Con pochi calcoli si trova la soluzione generale dell’equazione è la seguente:

\[ R_{n}= \frac{n^{2}}{2} + \frac{n}{2}+k \]

dove \(k\) è una costante da determinare. Utilizzando la condizione iniziale \(R_{2}=4\), si trova che \(k=1\) e quindi:

\[ R_{n}= \frac{n^{2}+n+2}{2} \]

Per i metodi di soluzione delle ricorrenze vedere ad esempio [1].

SOLUZIONE 1.2

Ricordiamo alcune definizioni sui grafi. Un grafo \(G = (V,A)\) è una coppia di insiemi, dove \(V\) è l’insieme dei vertici o nodi del grafo, e \(A\) è l’insieme degli archi, ognuno identificato da una coppia di nodi. Gli archi possono essere orientati o non.
Un grafo si dice planare se si può trovare almeno una rappresentazione grafica in cui gli archi (o spigoli) si intersecano esclusivamente nei vertici. Diciamo faccia del grafo ogni regione massimale del piano compresa fra due o più archi. Nell’insieme delle facce si comprende anche la regione infinita esterna al grafo. 
Ad esempio il grafo seguente è planare con 5 nodi, 7 archi e 4 facce.

Grafo planare

Teorema (Formula di Eulero) Sia G un grafo connesso e planare. Indichiamo con \(V,E,F\) il numero dei vertici, degli archi e delle facce. Allora vale la seguente relazione:

\[ V-E+F = 2 \]

Per una dimostrazione della formula di Eulero, vedere ad esempio [2].

Utilizziamo ora la formula di Eulero per risolvere il problema 1. Date le n rette, disegniamo un cerchio che contenga al suo interno tutti i punti di intersezione delle rette:

Cerchio e rette

Consideriamo ora il grafo i cui nodi sono i punti di intersezione delle rette tra loro e delle rette con la circonferenza. Si tratta di un grafo planare connesso e quindi si può applicare la formula di Eulero, nella forma \(V-E+F=1\), in quanto non dobbiamo considerare la regione esterna al cerchio.
Il numero dei vertici interni è \(\displaystyle \binom {n}{2}\); il numero dei vertici esterni è \(2n\). Per calcolare il numero degli archi, osserviamo che un vertice esterno contribuisce con \(3\), mentre un vertice interno con \(4\). Il numero totale degli archi è quindi \(E = \displaystyle \frac {3 \cdot 2n + 4 \binom{n}{2}}{2}\).
Applicando la formula di eulero abbiamo:

\[ R_{n}= 1 + n +\binom{n}{2} \]

Questo problema è equivalente al problema del massimo numero di parti di una pizza che è possibile fare effettuando n tagli.


Problema 2

Calcolare il massimo numero di parti nelle quali un piano può essere diviso da \(n\) cerchi.

SOLUZIONE 2.1

Come nel problema precedente, una condizione necessaria è che gli \(n\) cerchi si intersecano a due a due e che non ci siano tre cerchi con un punto in comune. Anche in questo caso si può ragionare per induzione:
una volta disegnati \(k\) cerchi, un nuovo cerchio interseca tutti gli \(n\) cerchi e quindi la circonferenza viene suddivisa in \(2n\) archi. Ognuno di questi archi divide in due una delle regioni che erano già presenti con gli \(n\) cerchi. Quindi l’aggiunta di un nuovo cerchio aumenta di \(2n\) il numero delle regioni nelle quali il piano viene diviso.
Indichiamo con\(R_{n}\) il numero massimo di regioni in cui viene suddiviso il piano da \(n\) cerchi. Possiamo quindi scrivere la seguente equazione di ricorrenza: \(R_{n} = R_{n-1} + 2(n-1)\). Risolviamo l’equazione e tenendo conto della condizione iniziale \(R_{2}=4\), otteniamo infine la soluzione:

\[ R_{n}= n^{2} – n + 2 \]
SOLUZIONE 2.2

Creiamo la seguente tabella cerchi-vertici-archi:

Tabella cerchi-vertici-archi

L’equazione di ricorrenza per i vertici è \(V_{n} – V_{n-1}= 2(n-1)\). Risolvendo questa equazione, tenendo conto della condizione iniziale \(V_{2}=2\), otteniamo \(V_{n} =n^{2}- n\).
Il numero degli archi è \(E_{n}= 2V_{n}\). Applicando la formula di Eulero \(R_{n}=E_{n}-V_{n}+2\), otteniamo:

\[ R_{n}=n^{2}-n+2 \]

I due problemi precedenti possono essere generalizzati nello spazio euclideo tridimensionale.


Problema 3

Calcolare il numero massimo di regioni in cui lo spazio tridimensionale può essere diviso da \(n\) piani.

SOLUZIONE 3

Seguendo un ragionamento simile a quello utilizzato per il piano nella soluzione 1.1, si trova la seguente soluzione:

\[ R_{n}=\frac {n^{3}+5n +6}{6} \]

Problema 4

Calcolare il numero massimo di regioni in cui lo spazio tridimensionale può essere diviso da \(n\) sfere.

SOLUZIONE 4

Seguendo un ragionamento simile a quello utilizzato per il piano nella soluzione 2.1, si trova la seguente soluzione:

\[ R_{n}=\frac {n^{3}-3n^{2}+8n}{3} \]

Per un approfondimento del problema di Steiner vedere ad esempio [3] e [4].


Bibliografia

[1]M. Spiegel – Differenze finite e equazioni alle differenze (Etas Libri)

[2]Tucker – Applied Combinatorics (Wiley)

[3]Knuth, Graham – Concrete Mathematics (Addison Wesley)

[4]Comtet – Advanced Combinatorics (D. Reidel)


0 commenti

Lascia un commento!