Il bello della matematica

Da qualche anno sono il coordinatore distrettuale, per la mia zona, del progetto Olimpiadi della Matematica. Uno dei miei compiti è organizzare la gara di secondo livello, selezionare gli studenti e, ahimé, incontrare qualche giornalista locale che viene a fare un giro all'università per vedere che facce hanno quelli a cui piace la matematica. Purtroppo i giornalisti fanno domande.

Questa volta mi hanno chiesto: ma perché questi ragazzi vengono qua a fare matematica? Cosa ci trovano di bello?

Io ho farfugliato qualcosa che ho immediatamente cancellato dalla memoria, però adesso potrei spiegare cosa ci trovo io di bello.

Parto da un problema assegnato proprio alla gara provinciale: c'è una calcolatrice a 5 cifre che non funziona tanto bene, perché solo due tasti hanno ancora qualche effetto. C'è un tasto che permette di moltiplicare per 3 ciò che appare sul display (più precisamente: quando premo quel tasto, automaticamente il numero sul display viene triplicato) e un tasto che permette di aggiungere 1. Quest'ultimo, però, non può mai essere premuto due volte consecutivamente, altrimenti la calcolatrice esplode. La domanda è: quanti diversi numeri si possono ottenere sul display senza fare esplodere la calcolatrice?

Un abile risolutore, che si è allenato su quesiti di questo tipo, vede subito la soluzione e buonanotte. Ma non tutti sono abituati e risolvono problemi di questo tipo tutti i giorni, e io sono tra questi.

Ho provato quindi a risolvere questo esercizio facendo un po' di prove. Ho cominciato a riempire fogli con numeri, freccette, cercando di costruire un albero delle soluzioni per cercare di capirci qualcosa. Poi mi sono anche consultato con una collega, coordinatrice di un'altra zona (ai coordinatori il testo della gara viene consegnato in anticipo, in segreto, in modo da lasciare un po' di tempo per preparare le fotocopie delle prove), perché avevamo inizialmente interpretato male il testo e non ci tornavano i conti. Anche lei aveva fatto uno schema con le freccette.

Poi, dato che i conti non mi dicevano molto, ho aperto un foglio elettronico e ho cominciato a riempirlo di numeri. Se parto da 0, e uso solo il tasto che moltiplica per 3, rimango su 0, e fin qua è facile. Se schiaccio il tasto +1 una volta, e poi continuo a schiacciare il tasto ×3, ottengo tutte le potenze di 3. Bene, poi?

Ho cominciato a riempire le righe del mio foglio elettronico con le moltiplicazioni per 3, e ogni volta che selezionavo il tasto +1 iniziavo una nuova riga. Però i numeri calcolati dal foglio mi dicevano poco, e allora ho ricominciato a scrivere dei numeri a mano senza però svolgere i calcoli. Ho ottenuto righe come queste:

1, 3, 3², 3³, …
3+1, (3+1)×3, (3+1)×3², …
(3+1)×3+1, ((3+1)×3+1)×3,((3+1)×3+1)×3², …

Le formule cominciavano a diventare interessanti, anche se ancora mi sfuggiva qualcosa. Per essere sicuro che l'idea che mi stava venendo in mente fosse giusta, ho scritto i calcoli in un altro modo, svolgendoli. Per esempio, la seconda riga sarebbe diventata questa:

3+1, 3²+3, 3³+3², …

E la terza, questa:

3²+3+1, 3³+3²+3, 3⁴+3³+3², …

Ah-ha! Somme di potenze di 3: la scrittura in base 3! Ogni volta che moltiplico per 3 aggiungo uno 0 in fondo. E cosa significa che non si può usare il tasto +1 due volte di seguito? Significa che la cifra delle unità può passare da 0 a 1, ma non da 1 a 2. Anzi, non si potrà mai avere la cifra 2 in nessuna delle formule possibili, perché il 2 si può ottenere soltanto con due +1 consecutivi, ma questo è vietato.

Ed ecco che tutto va a posto, e un problema che sembrava bruttissimo si risolve improvvisamente in maniera elegante e immediata. Si tratta ora di capire quanti numeri di cinque cifre (decimali) si possono ottenere: come si fa? Scriviamoli in base 3, tenendo presente che non possiamo mai usare la cifra 2. Vediamo un elenco di potenze di 3 sufficientemente grandi

3⁴ = 9×9 = 81, e questo si sa a memoria,
3⁸ = 81² = 6561,
3⁹ = 19683,
3¹⁰ = 59049,
3¹¹ = 177147.

Ok, l'ultimo numero, che in forma ternaria si scrive come 100000000000, è troppo alto. Vediamo il precedente, che è 11111111111 (ricordiamo che non si possono usare le cifre 2). A quanto è uguale?

Sono 11 cifre 1 consecutive, e la formula della somma dei termini di una progressione geometrica ci permette di calcolarlo velocemente, perché è uguale a (3¹¹−1)/2, cioè 177146/2 = 88573, che è composto da cinque cifre, e quindi va bene. Così come vanno bene tutti i numeri composti da al massimo undici cifre 0 oppure 1.

Ora abbiamo la risposta: il numero dei valori ottenibili con la calcolatrice è uguale al numero di modi che si hanno di riempire undici caselle con la cifra 0 o 1, cioè 2¹¹ = 2048.

A quel punto ero soddisfattissimo, e ho voluto rendere la collega partecipe di questa scoperta. E ho fatto quello che fanno i Veri Matematici quando risolvono un problema: ho sistemato la dimostrazione, ho buttato via tutti i conti e le schifezze che avevo scritto, ho chiuso il foglio elettronico che era ancora aperto per cancellare le tracce degli orrori che avevo commesso, e ho scritto questo messaggio (era quasi mezzanotte):

Dopo aver trappolato con un po' di numeri e giocato con excel, 

ho trovato la soluzione bella.

Spero che tu abbia il cellulare silenzioso, 

altrimenti ti sto svegliando la casa.
🙂

Se scriviamo i numeri in base 3, il tasto +1 della calcolatrice 

corrisponde a mettere un 1 nell'ultima cifra, perché essa può 

solo essere 0 (partiamo da 0 e aggiungiamo +1 una sola volta 

alla volta) (magari posso dirlo meglio in italiano domani)

Il tasto x3 invece corrisponde a aggiungere uno 0 

in fondo al numero.

Il massimo numero che possiamo costruire è 11111111111 

(11 cifre 1 consecutive), che corrisponde a (3^11-1)/2=88573.

Il numero successivo costruibile è 100000000000 = 3^11 che è 

composto da 6 cifre, quindi è da scartare.

Il problema si traduce quindi in questa domanda: 

quanti numeri composti solo da cifre 1 e 0 lunghi 

11 cifre posso formare? La risposta è 2^11 = 2048

Ed ecco una dimostrazione elegante, breve, semplice, senza troppi calcoli, alla portata di tutti. Ed ecco, anche, la risposta alla domanda del giornalista:

Si dice che Dio abbia un libro che contiene tutte le Dimostrazioni Belle. La più grande soddisfazione del matematico è trovarne una.