Perché ogni albero dei fattori ha lo stesso numero di coppie

Testo

In un albero dei fattori di un numero $n$ ogni nodo che non è primo si spezza in due fattori, fino ad arrivare ai numeri primi (le foglie). Dimostra che, comunque si costruisca l’albero, il numero di “coppie” (cioè di spaccature) è sempre lo stesso, uguale a $\Omega(n)-1$, dove $\Omega(n)$ è il numero di fattori primi di $n$ contati con la loro molteplicità.

Soluzione

Contiamo le foglie. L’albero parte con un solo nodo (la radice $n$). Ogni spaccatura sostituisce un nodo con due figli: rimuove una foglia e ne aggiunge due, cioè aumenta il numero di foglie esattamente di $1$. Alla fine le foglie sono i fattori primi contati con molteplicità, quindi sono $\Omega(n)$ (numero che, per il teorema fondamentale dell’aritmetica, non dipende dalle scelte fatte). Se $S$ è il numero di spaccature, partendo da $1$ foglia e arrivando a $\Omega(n)$ foglie si ha $1+S=\Omega(n)$, ovvero $S = \Omega(n)-1.$ Questo valore dipende solo da $n$, non dall’albero scelto. $\blacksquare$

Collegamenti

Argomenti: Numeri e operazioni
Concetti: Fattorizzazione in primi · Numero primo
Competenze: Dimostrare
Tipo di esercizio: Dimostrazione