Chi occupa il miliardesimo posto?

Consideriamo una successione in cui il numero 1 compare una volta, il 2 due volte, il 3 tre volte e così via. Quale numero si trova esattamente al miliardesimo posto? L’intervallo occupato da ciascun numero permette di trovare la risposta senza costruire un miliardo di termini.

Elaborato originariamente preparato per il Corso Neoassunti 2011-2012 e stampato il 15 maggio 2012.

1. Riassunto

Questo elaborato propone una correzione della soluzione attribuita a Ferdinando Arzarello per la UMI: 44722 non è il risultato corretto. La risposta esatta è 44721. Il punto essenziale è che il numero n non occupa una sola posizione, ma un intero intervallo di n posizioni.

2. Il problema

Consideriamo la successione dei numeri naturali:

1  2 2  3 3 3  4 4 4 4  5 5 5 5 5  6 6 6 6 6 6  ...

Si scrive una volta il numero 1, due volte il numero 2, tre volte il numero 3 e, in generale, n volte il numero n. La domanda è: qual è il miliardesimo termine della successione?

3. Una soluzione mediante gli intervalli

Per trovare la posizione finale del numero 4, per esempio, sommiamo i primi quattro numeri:

1 + 2 + 3 + 4 = 10

La formula di Gauss fornisce la posizione finale del blocco contenente n:

fine(n) = n(n + 1) / 2 = (n² + n) / 2

Il blocco contiene n termini; la sua posizione iniziale è quindi la posizione finale meno n - 1:

inizio(n) = n(n + 1) / 2 - (n - 1)
          = n(n - 1) / 2 + 1
          = (n² - n + 2) / 2

Il numero n occupa tutte le posizioni, estremi compresi, da (n² - n + 2)/2 a (n² + n)/2.

4. La verifica con un foglio di calcolo

In Excel, o in qualsiasi altro foglio di calcolo, possiamo creare tre colonne: n, posizione iniziale e posizione finale. Le prime righe mostrano come crescono gli intervalli; le ultime due sono quelle decisive.

La soluzione esatta è il più piccolo intero n per cui fine(n) ≥ 1.000.000.000: tale intero è 44721. Il posto 1.000.000.000 appartiene infatti all’intervallo di 44721. Il numero 44722 comincia soltanto alla posizione 1.000.006.282, già oltre il miliardesimo termine. Omettere l’esistenza di questo intervallo può facilmente generare confusione.

5. Modellizzazione e approssimazione

Indichiamo con I la posizione iniziale e con F la posizione finale del blocco di n:

I = (n² - n + 2) / 2
F = (n² + n) / 2

2I = n² - n + 2
2F = n² + n
2I + 2F = 2n² + 2
I + F = n² + 1
n² = I + F - 1

Se M = (I + F)/2 è il valore medio delle posizioni occupate dal numero, allora:

n² = 2M - 1

Il quadrato di n è quindi il doppio della posizione media diminuito di 1. Poiché le funzioni considerate sono crescenti, sostituire a M un numero più piccolo produce un’approssimazione per difetto; sostituirne uno più grande produce un’approssimazione per eccesso. Se non conosciamo le posizioni iniziale e finale, non possiamo stabilire da quale lato cada l’approssimazione.

Nel nostro caso, usando direttamente un miliardo come valore di riferimento, otteniamo:

√(2 · 1.000.000.000)     = 44.721,3595499958
√(2 · 1.000.000.000 - 1) = 44.721,3595388155

Entrambi i valori sono vicinissimi alla soluzione intera 44721. Per n = 44721, la posizione media è:

M = (999.961.561 + 1.000.006.281) / 2
  = 999.983.921

Poiché 1.000.000.000 è maggiore di questa media, 44.721,3595388155 è un’approssimazione per eccesso. La verifica tramite l’intervallo stabilisce infine senza ambiguità che il miliardesimo termine è 44721.

A cura di Salvatore Mosaico.