15. Quanti sono i numeri di cinque cifre (cioè fra 10000 e 99999) che non contengono zeri e sono multipli di 12 ?
15. La risposta è 4374. Per determinare quanti sono esattamente i numeri da contare, ricordiamo
innanzitutto che un numero è divisibile per 12 se e solo se è divisibile per 4 e per 3 , e i criteri di divisibilità ci dicono che:

- Le ultime due cifre del numero devono formare un multiplo di 4
- La somma delle cifre del numero deve essere divisibile per 3.

L'idea su cui si basa questa soluzione è quella di "generare" tutti i possibili numeri di questo tipo scegliendo nell'ordine le cifre dall'ultima alla prima.

(a) Contiamo innanzitutto in quanti modi possiamo scegliere le ultime due cifre: esse devono formare un multiplo di 4 di due cifre che non contiene zeri, e le possibilità per questa scelta sono 18 (tutti i multipli di 4 inferiori a 100 sono 25 , ma da questi vanno scartati $00,04,08$, 20, 40, 60, 80 che contengono almeno uno zero).

(b) La seconda e la terza cifra del numero possono essere scelte ognuna in 9 modi diversi (tutte le cifre da 1 a 9 ) indipendentemente da tutte le altre cifre. Ora ci resta da scegliere la prima cifra del numero, e da sistemare la divisibilità per 3 .

(c) La prima cifra può essere scelta in 9 modi diversi, ma non tutte quest scelte permettono di ottenere la divisibilità per 3. Però, visto che le nove cifre da 1 a 9 nella divisione per 3 hanno i resti uguali a tre a tre, una volta che abbiamo fissato tutte le cifre precedenti esattamente 3 delle possibili scelte per la prima cifra sono accettabili.

Riassumendo, possiamo scegliere un numero che rispetta le condizioni richieste in $18 \cdot 9 \cdot 9 \cdot 3=4374$ modi diversi. È semplice controllare che in questo modo generiamo tutti i numeri scelti, in quanto i criteri di divisibilità sono condizioni necessarie e sufficienti.

Seconda Soluzione

Imponiamo innanzitutto che il numero sia multiplo di 4, allora le sue due ultime cifre dovranno essere uno dei multipli di 4 tra 00 e 99; tali multipli sono 25 , ma tra questi ve ne sono 7 che contengono almeno uno zero e quindi vanno scartati. Rimaniamo con 18 possibilità per le cifre finali. Ora dobbiamo scegliere altre tre cifre (non zero) di modo che la somma di tutte e cinque le cifre sia multipla di 3 , per garantire la divisibilità per 3. Utilizzando le congruenze modulo 3 , osserviamo che, per ogni possibile resto della divisione per 3 , vi sono esattamente 3 numeri tra 1 e 9 che lo danno (1, 4, 7 - 2, 5, 8 - 3, 6, 9). A meno dell'ordine, i vari resti modulo 3 si possono ottenere come somma di 3 resti in questi modi : $0 \equiv 0+0+0 \equiv 1+1+1 \equiv 2+2+2 \equiv 0+1+2$ $\bmod 3,1 \equiv 0+0+1 \equiv 0+2+2 \equiv 1+1+2 \bmod 3,2 \equiv 0+1+1 \equiv 0+0+2 \equiv 1+2+2$ mod 3. Per tenere conto anche dell'ordine, osserviamo che $0+1+2$ si può permutare in 6 modi, $0+0+0$ e simili non hanno permutazioni, tutti gli altri si possono permutare in 3 modi. Quindi, tenendo conto dell'ordine, ogni resto si può scrivere in 9 modi diversi come somma di 3 resti; quindi, fissato un resto, possiamo realizzare un numero di 3 cifre che dia quel resto e che non contenga 0 in $9 \cdot 3^{3}$ modi e dunque, indipendentemente da quali ultime due cifre scegliamo, avremo $9 \cdot 3^{3}$ modi di completare il numero di modo che sia multiplo di 3 , senza inserire zeri. In totale avremo perciò $18 \cdot 9 \cdot 27=4374$ modi.