Quanti “zero” sono necessari per scrivere tutti i numeri da 1 a un milione?

Anche questo problema, come spesso accade in matematica (si
pensi, per esempio, a quanto ho detto anche sul gioco del
100) può essere risolto iniziando a affrontare un problema
più semplice. Cerchiamo quindi per prima cosa la risposta a questa
domanda: quanti “zero” sono necessari per scrivere tutti i numeri di n
cifre?

      È abbastanza
facile rispondere alla domanda quando n è molto piccolo,
cioè 1 e 2. I numeri di una cifra (escludendo lo zero, visto che
è naturale iniziare a contare dall’1 come fa lo stesso lettore) sono
infatti quelli dall’1 al 9, nessuno dei quali è 0, quindi in questo
caso la risposta è zero. Gli unici numeri di due cifre (che sono 90,
da 10 a 99) che comprendono lo zero sono inoltre i multipli di 10 dal 10 al
90, quindi sono nove.

      Le cose si complicano
subito, però, già quando si cominciano a considerare i 900
numeri di tre cifre. Vale allora la pena di cercare di sviluppare un metodo
più o meno “induttivo” per capire come, conoscendo gli zeri necessari
per scrivere tutti i numeri di n cifre, si riescono a calcolare gli
zeri necessari per scrivere tutti i numeri di n + 1 cifre.
Indichiamo con z_n il numero di zeri che occorrono per
scrivere i 9 ^. 10^n-1 numeri di
n cifre: i numeri di n + 1 cifre che comprendono
degli “zero” al loro interno si possono ottenere in due modi (preciso come
sempre che questo modo di ragionare potrebbe non essere né l’unico
possibile né il migliore):

• prendendo un qualsiasi numero di n cifre e
  aggiungendo alla fine uno zero. I numeri che si possono ottenere in questo
  modo sono 9 ^. 10^n-1, cioè tanti
  quanti i numeri di n cifre, e gli zeri che si usano sono
  9 ^. 10^n-1 (uno per ognuno di quei
  numeri, a cui abbiamo aggiunto uno zero in fondo) più altri
  z_n (che servono per scrivere quegli stessi numeri!);

• prendendo uno dei numeri di n cifre che
  già contengono qualche “zero” e aggiungendo alla fine una qualsiasi
  cifra diversa da zero (altrimenti si otterrebbe un numero del primo tipo, che
  abbiamo già contato): in questo modo, ogni “zero” viene ripetuto nove
  volte (una per ogni cifra da 1 a 9) e si scrivono quindi
  9z_n “zero”.

Siamo riusciti quindi a ottenere una formula ricorsiva per
calcolare quanti “zero” occorrono per scrivere tutti i numeri di
n + 1 cifre:

z_n+1
=
(9 ^. 10^n-1 + z_n) + 9 ^. z_n
=
9 ^. 10^n-1 + 10 ^. z_n

Siamo allora pronti per scrivere una tabella nella quale
mettiamo in prima colonna (n) il numero di cifre che stiamo
considerando, in seconda colonna
(9 ^. 10^n-1) quanti numeri esistono con
quelle cifre e in terza colonna (z_n) numero di zeri che
servono per scriverli.

A questo punto sarebbe possibile dimostrare che esiste una
formula ancora più elegante, cioè che nei numeri con n
cifre ci sono esattamente
9(n – 1) ^. 10^n-2
“zero” (lasciamo al lettore il compito di dimostrarla per induzione), ma
questi dati sono già sufficienti per rispondere alla domanda. I
numeri da 1 a un milione comprendono infatti tutti i numeri che si possono
scrivere con 1, 2, 3, 4, 5 e 6 cifre, più il numero 1000000 che
contiene sei zeri. Il numero di zeri necessario è allora

9 + 180 + 2700 + 36000 + 450000 + 6 = 488895.

Vale anche la pena di dire che questo risultato potrebbe
essere raggiunto per via informatica, facendo generare a un computer tutti i
numeri da 1 a 1000000 e poi facendogli contare il numero di zeri che
contengono. Di seguito riporto il listato di un piccolo programma in BASIC
che ho realizzato a questo scopo (soprattutto, lo confesso, per controllare
il risultato che avevo ottenuto, visto che mi sembrava un po’ troppo
grande!).

          OPEN "temp.txt" FOR OUTPUT AS #1
            FOR n = 1 TO 1000000
              PRINT #1, n
            NEXT
          CLOSE

          OPEN "temp.txt" FOR INPUT AS #1
            n = 0
            WHILE NOT EOF(1)
              A(1, #1)
              IF A$ = "0" THEN n = n + 1
            WEND
          CLOSE

          KILL "temp.txt"
          PRINT n

A chiunque altro condividesse i miei dubbi sul numero
ottenuto in precedenza, confermo il fatto che il computer ha restituito
proprio il numero 488895.

      Concludo con un po’ di
divagazioni. Uno dei numeri normali più famosi che si conoscano (per
la definizione, anche se data in modo un po’ affrettato, si veda una mia
precedente risposta) è
quello che si ottiene scrivendo dopo la virgola tutti i numeri naturali uno
dopo l’altro, cioè 0,123456789101112… . Si noti che quando si
scrive il numero “un milione” si sono scritte
9 + 2 ^. 90 + 3 ^. 900 + … + 6 ^. 90000 + 7 = 5888896
cifre. Il conteggio che abbiamo fatto permette allora di calcolare che nelle
prime 5888896 cifre lo zero compare con frequenza 488895 / 5888896,
pari circa a 0.083, abbastanza (anche se non molto!) vicina alla frequenza
“teorica” di 0.1. Lasciamo al lettore la verifica del fatto che arrivando a
dieci milioni si ottiene una frequenza di 5888896 / 68888897, pari
circa a .085; ci si può anche convincere che tale frequenza tende
(sebbene abbastanza lentamente) a 0.1 al crescere del numero di cifre. Vale anche
la pena di notare che il numero di cifre necessarie per scrivere i numeri da
1 a 10ⁿ è esattamente uguale al numero di zeri
contenuti nei numeri tra 1 e 10ⁿ⁺¹: potrebbe essere
interessante trovare una ragione per questo fatto, eventualmente passando
attraverso un modo per contare gli “zeri” diverso da quello che ho suggerito
in precedenza.