Divisione del Piano e dello Spazio (Problema di Steiner)

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

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.

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:

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

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

Creiamo la seguente 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 \]

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

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