Nodi di carta

“Cos'è un nodo?”.

“Un nodo… un nodo è… un nodo è un nodo!”.

“Certo. Un Vero Matematico non sarebbe molto contento di questa definizione”.

“I Veri Matematici non sono mai contenti di nulla. Come lo definiscono un nodo, loro?”.

“Direbbero che un nodo è una curva semplice chiusa nello spazio”.

“Ah”.

“Ma se vai nel dettaglio, la definizione potrebbe risultare leggermente più incomprensibile”.

“Naturalmente”.

“Per esempio, se vai a vedere la voce sulla Wikipedia in italiano, trovi una frase che afferma che sarebbe sbagliato definire un nodo come l'immagine di una funzione continua dalla circonferenza nello spazio, perché così tutti i nodi risulterebbero equivalenti”.

“Interessante”.

“Se vai sulla analoga voce in inglese, invece, trovi scritto: a knot is an embedding of a circle in 3-dimensional Euclidean space, considered up to continuos deformations”.

“Eh? Ma è esattamente quello che la voce in italiano segnala come sbagliato”.

“Appunto”.

“Roba da matti”.

“Insomma, dato che non dobbiamo fare teoria dei nodi, a noi basta sapere che un nodo è una cosa di questo tipo. Questo si chiama nodo trifoglio”.

“Ok”.

“Mentre questo non è un nodo”.

“E perché no?”.

“Perché non è una curva chiusa. Un finto nodo come questo puoi sempre scioglierlo, mentre un nodo vero come quello della prima immagine non può essere sciolto, in modo da formare una circonferenza non annodata. Devi tagliarlo”.

“Ah, ecco. Ammesso che gli estremi non siano collegati in qualche modo, questo puoi scioglierlo, e farlo diventare un segmento”.

“Proprio così. Ricordi che abbiamo lavorato con una striscia di carta, un po' di tempo fa?”.

“Ricordo”.

“Ora proviamo a annodarla con un nodo semplice, ma non incolliamo gli estremi”.

“Insomma, proviamo a fare una cosa che tutte le persone appartenenti al mondo normale, eccetto quindi i Veri Matematici, chiamano nodo”.

“Esatto. Ecco una simulazione di nodo, con la quale puoi giocare”.



“Ah, vedo. Mi aspettavo qualcosa di curvo, mentre vedo dei segmenti”.

“Se tu prendi una vera striscia di carta e provi a annodarla, è vero che la incurvi. Ma a un certo punto puoi decidere di schiacciare tutta la carta su un piano, formando delle pieghe. La sostanza del nodo non cambia”.

“Ah, va bene. Vedo che posso cambiare dei parametri, ma non capisco quello che sto facendo”.

“Puoi cambiare lo spessore della carta, e puoi anche cambiare gli angoli secondo i quali pieghi la carta”.

“Ah, ecco, vedo che posso fare nodi magrolini e nodi più pieni”.

“Sì. Puoi pensare di annodare una striscia sottile lasciando spazio intorno alle anse del nodo, oppure puoi pensare di stringere il nodo più che puoi. In questa simulazione, invece di stringere il nodo allarghiamo la striscia di carta”.

“Capisco: è la stessa cosa. Come se guardassimo il nodo con uno zoom regolabile, in modo da tenere costante la dimensione del nodo”.

“Proprio così. Ora, una domanda: qual è la figura più simmetrica che puoi ottenere?”.

“Fammi provare… Il foglio di carta si piega tre volte, devo cercare di fare in modo che i tre angoli siano uguali, uhm”.

“Gioca un po' con i parametri che puoi regolare”.

“Ah, ecco! Se impongo che i due angoli siano di 36 gradi, salta fuori una bella figura simmetrica”.

“Bene, ora allarga più che puoi lo spessore del foglio di carta”.

“Ok… Bello! Se allargo al massimo si vede che riesco a riempire un pentagono”.

“Un pentagono regolare, esatto”.

“Perché?”.

“Gli angoli con i quali hai giocato, e che ora misurano 36 gradi, sono gli angoli secondo i quali è stata piegata la carta. Se osservi bene la figura, noterai che il lato della striscia, prima di essere piegato, è parallelo a un lato del pentagono; dopo la piega, è ancora parallelo a un altro lato”.

“Ah, vedo: la striscia è parallela a un lato, si piega su un secondo lato, adiacente al primo, e dopo la piega è parallela al lato adiacente al secondo”.

“E questa è proprio una caratteristica del pentagono: gli angoli interni di un pentagono regolare misurano 108 gradi, e l'angolo formato da due lati non consecutivi è proprio di 36 gradi”.

“Davvero?”.

“Guarda questa figura”.

“Ah, ok, vedo”.

“Quindi se tu prendi una striscia di carta e l'annodi, in modo da non lasciare spazi vuoti intorno alle pieghe, la figura che ottieni è un pentagono regolare”.

“E questo, però, non è un vero nodo matematico”.

“No, perché i capi del nodo sono liberi, e puoi sempre scioglierlo. Però, se i capi sono molto lunghi, puoi continuare a piegarli intorno al pentagono con regolarità”.

“Uhm, in che modo?”.

“Un capo parallelo a un lato del pentagono, dopo la piega, sarà parallelo a un altro lato del pentagono: puoi continuare a piegare seguendo i lati. Ogni piega segue un lato, e puoi continuare finché hai carta”.

“In modo da fare un blocchetto pentagonale”.

“Esatto. Questo è quello che fanno in Giappone, per esempio, quando piegano le cinture”.

“Ehh?”.

“Guarda qua”.

Strisce

“Oh, cos'è?”.

“Mi sto divertendo a piegare fogli di carta”.

“Ah, fai degli origami?”.

“Mh, no, niente di complicato. Mi stavo chiedendo come funziona la piegatura di una strisciolina di carta”.

“Non ti basta semplicemente piegarla, vero?”.

“Eh eh, sì, mi basterebbe anche. Però, vedi, se cominci a piegarla più volte saltano fuori delle belle forme, e allora uno vorrebbe provare a capire cosa c'è sotto”.

“Capirai”.

“Non è facile vedere le cose in tre dimensioni, e questo è un bell'esercizio”.

“Ah, vedo. Quindi, cos'hai scoperto?”.

“Beh, per prima cosa una striscia di carta è definita dai suoi due bordi”.

“E fin qua ci siamo”.

“Poi, vedi che per piegare la striscia si deve effettuare una rotazione intorno alla piega”.

“Sì. Io faccio però fatica a capire cosa si può fare e cosa non si può fare, quando si piega della carta”.

“Cioè?”.

“Il problema è che la carta non è rigida, ma non è nemmeno gomma. Quindi ci sono movimenti che sono permessi, e movimenti che invece non sono permessi”.

“Esatto, puoi piegarla ma non puoi allungarla o accorciarla. Puoi fare rotazioni, ma le lunghezze dei segmenti devono rimanere invariate”.

“Sì, la teoria è abbastanza semplice. Il difficile qua è vedere quello che succede. Per esempio, di quanto risulta inclinata la striscia dopo la piega?”.

“Ah, ottima domanda. Come faresti per rispondere?”.

“Eh, qui sta il punto. Io prenderei in mano una striscia vera e proverei”.

“Ottimo inizio: c'è chi si diverte a fare geometria senza figure, ma noi non siamo tra questi”.

“Meno male. Però, dopo aver giocato con la carta, non saprei andare avanti”.

“Bisognerebbe riuscire a passare dalla figura tridimensionale a una figura bidimensionale, così le cose diventerebbero molto più semplici”.

“Ah, certo. Però, ora che ci penso, se faccio una piega completa arrivo a una figura bidimensionale…”.

“Vai avanti”.

“Il foglio iniziale è piano, no? Poi lo piego, e non rimango più su un piano. Ma se la piega compie una rotazione di 180 gradi…”.

“Ottimo, concludi”.

“Se la piega consiste in una rotazione di 180 gradi, il risultato finale è ancora un piano. Schiaccio il foglio su sé stesso.”.

“Giusto”.

“Ora dovrei capire come risulta la figura finale, però”.

“Hai già capito molto: hai detto che ruoti di 180 gradi intorno a un asse”.

“Sì”.

“E questo è come dire che stai facendo una simmetria assiale”.

“Mh, suppongo di sì, sì. A dir la verità, non mi risulta facile nemmeno vedere come funziona una simmetria di una retta rispetto a un'altra retta”.

“Beh, questo è molto semplice: l'angolo formato tra le due rette non cambia”.

“Ah, già, vedo. La retta blu viene trasformata nella retta rossa, vero? I due angoli formati dalle due rette con l'asse di simmetria non cambiano”.

“Sì. Naturalmente puoi anche dire che è la retta rossa che viene trasformata nella retta blu”.

“Giusto, certo. Posso piegare il foglio da sopra a sotto o da sotto a sopra, non importa”.

“Ok. Ora ti mostro l'applicazione di questa semplice regola a una striscia di carta”.

“Oh, quanti colori”.

“Sì, potevo fare ricorso a una maggiore sobrietà. Però così si distinguono tutte le parti”.

“Ok, vedo la striscia verticale”.

“Esatto”.

“Che poi viene piegata lungo la linea tratteggiata. Riconosco anche gli angoli uguali come mi hai fatto vedere prima, sono quelli verdi”.

“Molto bene”.

“Poi ci sono altri angoli, però”.

“Sì, qui ho fatto un passo avanti. Se la piega fosse perpendicolare ai bordi della striscia, si avrebbe una figura poco interessante: la striscia si ripiegherebbe completamente su sé stessa, e tanti saluti allo studio degli angoli”.

“Ok”.

“Allora la domanda è: se la piega è inclinata, rispetto all'orizzontale, di un certo angolo…”.

“Quello evidenziato di rosso, giusto?”.

“Proprio quello. Se la piega è inclinata, rispetto all'orizzontale, dell'angolo colorato di rosso, di quanto risulta inclinata la striscia?”.

“Non è una risposta facile, mi pare”.

“Diventa facile se osservi una sola cosa: l'angolo rosso e l'angolo verde sono legati da una certa relazione”.

“Uhm. Vedo un triangolo che li contiene entrambi”.

“Esatto”.

“Ah! Un triangolo rettangolo! Quindi l'angolo rosso e quello verde sono complementari”.

“Giusto, e adesso tutti gli angoli segnati in figura dovrebbero essere evidenti”.

“Lo sono, sì. Hai tracciato, in grigio, la perpendicolare all'asse di simmetria, quindi ecco un altro angolo retto, ed ecco i due angoli complementari”.

“Ecco fatto, quindi”.

“Mi pare, allora, che l'angolo con cui la striscia viene deviata, per così dire, sia il doppio dell'angolo rosso”.

“Ed è così”.

“E adesso?”.

“Adesso facciamo un nodo”.

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.

Il piccolo Fermat e i braccialetti

“Braccialetti?”.

“Braccialetti”.

“Cosa c'entrano i braccialetti con la matematica?”.

“I nostri braccialetti sono formati da perline colorate”.

“Ah, va bene. Quindi?”.

“Più precisamente: da un numero primo di perline colorate”.

“Uhm”.

“Chiamiamolo p, e per fare un esempio supponiamo che p sia uguale a 3”.

“Braccialetti con tre perline: una miseria”.

“Lo so, ma vorrei fare qualche disegnino, se aumentiamo il numero non finiamo più”.

“Ok, allora facciamo questi braccialetti con tre perline colorate. Ah, come le coloriamo?”.

“Con un certo numero di colori diversi, diciamo n colori diversi”.

“E anche in questo caso fissiamo un n di esempio?”.

“Sì, facciamo tre colori”.

“Uhm, non è che ci confondiamo tra n e p?”.

“Direi di no, perché faremo qualche schema: se indichiamo i colori con i numeri 1, 2 e 3, ci basta scrivere tre numeri per avere un braccialetto. Si dovrebbe distinguere bene tra il numero di cifre scritte e il fatto che le cifre vanno da 1 a 3”.

“Vediamo”.

“Allora, prima di rappresentare i braccialetti, risolviamo un problema più semplice: calcoliamo il numero di stringhe che si possono creare con tre perline colorate. Insomma, rispetto ai braccialetti qui abbiamo delle posizioni predefinite: una perlina può essere messa al primo posto, al secondo o al terzo. Nel caso dei braccialetti, invece, non esistono un primo, un secondo e un terzo posto, perché ogni posizione in cui compare la perlina è indistinguibile dalle altre”.

“A meno che non indichiamo anche dove si mette la fibbia di chiusura”.

“Esatto. Quella la nascondiamo, fabbrichiamo un braccialetto senza fibbia. Prima, però, le stringhe”.

“Forse riesco a calcolare le possibilità: ci sono tre posizioni, e in ogni posizione posso mettere uno dei tre colori. Quindi dovrei avere 3 possibilità per la prima posizione, 3 per la seconda e 3 anche per la terza. Totale: 27”.

“O, meglio, 3³”.

“Va bene”.

“Eccole qua:”.

123
312
231

132
213
321

133
313
331

122
212
221

112
211
121

223
322
232

113
311
131

332
233
323

111
222
333

“Vedo”.

“Ora, le tre stringhe monocolori le mettiamo da parte”.

“Sono le ultime tre: perché le mettiamo da parte?”.

“Perché per loro servono conteggi diversi: dopo le recuperiamo. Per ora ragioniamo sulle prime 24”.

“Ok”.

“Trasformiamo ogni stringa in un braccialetto: ogni stringa può essere ruotata in tutti i modi possibili, e quindi ogni braccialetto può essere generato da più stringhe diverse”.

“Fammi capire meglio”.

“Le tre stringhe 123, 312 e 231 generano lo stesso braccialetto, perché non importa quale sia il punto di partenza”.

“Ah, hai ragione, l'importante è che 1 sia seguito da 2, 2 da 3 e 3 di nuovo da 1”.

“Esatto. Ora si tratta di contare i braccialetti”.

“Beh, è facile, li hai già raggruppati quando li hai elencati”.

“Sì, in questo esempio. Vorrei trovare una formula generale”.

“Ah”.

“Allora: noi possiamo prendere l'ultima perlina di una stringa, sfilarla dalla sua posizione e reinserirla all'inizio. Così facendo otteniamo una stringa diversa ma lo stesso braccialetto, giusto?”.

“Giusto”.

“Quante di queste alterazioni si possono fare prima che la stringa torni a essere uguale a com'era all'inizio?”.

“Direi 3, no? A parte le stringhe monocolore”.

“Non fissare le idee su questo esempio, che è solo un esempio. Come funziona in generale? Il numero di alterazioni possibili sarà sempre uguale al numero di palline?”.

“Pensavo di sì, dici di no?”.

“Guarda questo braccialetto composto da 6 perline:”.

121212

“Ah. Dopo il primo movimento diventa 212121 e dopo il secondo torna come prima”.

“Esattamente”.

“E allora come facciamo a calcolare questo numero di spostamenti?”.

“Bisogna pensare a qualche formuletta”.

“Era quello che temevo”.

“Non sarà difficile. Chiamiamo k il minimo numero di spostamenti di perline da fare perché il braccialetto torni uguale a com'era all'inizio”.

“Va bene. Ah, è per questo che hai messo da parte le stringhe monocromatiche?”.

“Molto bene! Per quelle k vale 1, naturalmente, perché sono sempre uguali a sé stesse.”.

“Ho capito, anche se avrei detto che per esse k dovrebbe essere 0 ”.

“Beh, 0 allora va bene per tutte, no? Tutte quante con 0 mosse diventano uguali a sé stesse”.

“Già, hai ragione. Quindi k deve essere positivo”.

“Bene. E, escludendo le stringhe monocromatiche, k deve essere maggiore di 1”.

“Giusto”.

“Ora, supponi di aver trovato un valore di k che funziona per una certa stringa: se essa diventa uguale a sé stessa dopo k mosse, lo farà anche dopo 2k mosse, dopo 3k mosse, e così via”.

“Mi pare ovvio”.

“Allora, facciamo questo calcolo: dividiamo il numero p di perline per k”.

“Non so quanto possa risultare”.

“Beh, vogliamo una formula, non un risultato esatto. Cosa significa che p diviso k dà quoziente h e resto r?”.

“Non ne ho assolutamente idea”.

“Ma sì, lo sai dalle elementari. La maestra non ti faceva fare la prova?”.

“Ah, sì, dovevo moltiplicare il quoziente per il divisore e aggiungere il resto”.

“Esatto: vale la formula p = hk + r”.

“Vabbé. Questo mi aiuta?”.

“Certo. Cosa mi dici di r?”.

“So che è il resto”.

“E il resto, in una divisione, può essere grande quanto si vuole?”.

“Eh, no, il resto è sempre più piccolo del divisore”.

“Perfetto: quindi r è un numero compreso tra 0 e k”.

“Però non può essere uguale a k, solo a 0, no?”.

“Certo. Ora, se prendiamo una stringa di lunghezza p e facciamo p spostamenti di perline, la stringa torna a essere uguale a sé stessa indipendentemente dal valore di p, sei d'accordo”.

“Ah, certo, sposto tutte le perline fino a che non tornano nella posizione iniziale”.

“Benissimo. E anche se faccio hk spostamenti la stringa torna a essere uguale a sé stessa”.

“Perché?”.

“L'abbiamo detto prima: k è proprio quel numero di spostamenti da fare perché la stringa non cambi, e se ne puoi fare k ne puoi anche fare 2k, 3k, eccetera. Anche hk”.

“Ah, ok.”.

“Ora riprendiamo l'uguaglianza che definisce la divisione: p = hk + r. Questa ci dice che se prendiamo una stringa e facciamo hk spostamenti, questa diventa uguale a com'era all'inizio. Se poi ne facciamo altri r, in tutto ne abbiamo fatti hk + r, cioè p. Questo significa che di nuovo la stringa ritorna com'era all'inizio”.

“Giusto”.

“Mica tanto giusto, perché questo significherebbe che ci bastano r spostamenti per riportare la stringa alla posizione iniziale”.

“E perché non è possibile?”.

“Perché il resto di una divisione è minore del divisore: r è minore di k”.

“Vabbé, r sarà minore di k, qual è il problema?”.

“Il problema è che k dovrebbe essere il numero minimo di spostamenti da fare, e invece così facendo avremmo trovato un numero ancora più piccolo”.

“Ah. Allora c'è qualcosa di sbagliato nel ragionamento?”.

“No, c'è un'unica conclusione coerente con tutto quanto abbiamo detto: r deve essere 0”.

“Ah! Allora p è multiplo di k, e tutto torna”.

“Giusto. E cosa potremmo dire se p fosse un numero primo?”.

“O k è uguale a 1…”.

“Questo vorrebbe dire che le stringhe sono monocromatiche”.

“Giusto, e noi l'abbiamo escluso. Allora k e p devono essere uguali”.

“Ottimo. Riassumendo: avevamo p perline di n colori diversi, con le quali abbiamo costruito n^p stringhe diverse”.

“Poi abbiamo tolto tutte le stringhe monocolori, che sono tante quante i colori, cioè n”.

“E quindi sono rimaste n^p − n stringhe. E ci siamo chiesti quante di queste generano braccialetti uguali”.

“Uhm, abbiamo detto che potevamo raggrupparle k alla volta. Ah, k è p, quindi possiamo raggrupparle a gruppi di p”.

“Ed ecco il risultato, quindi: il numero di stringhe, escluse quelle monocromatiche, è divisibile per p”.

“Questo è un teorema? n^p − n è divisibile per p?”.

“Sì, si chiama piccolo teorema di Fermat, e ne avevamo già parlato, in altri termini”.

Un generatore di numeri primi

“Ehi, guarda, ho scoperto un generatore di numeri primi!”.

“Uhm”.

“Come uhm? Guarda:”.

P(n) = n² + n + 41

“Uhm”.

“Ma insomma, cosa c'è che non va? P(0) fa 41, che è un numero primo”.

“Questo è vero”.

“P(1) fa 43, che è ancora primo”.

“Vero anche questo”.

“P(2) fa 47, P(3) fa 53, tutti primi”.

“Certo”.

“E posso andare avanti così, i numeri successivi sono 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033”.

“Molto bene”.

“Quindi sto generando numeri primi”.

“Sì, certo. Hai calcolato P(41)?”.

“Aspetta che faccio i calcoli”.

“Forse non hai bisogno di fare tutti i conti per dire se è primo o no”.

“Perché?”.

“Beh, stai sommando tre numeri: 41² + 41 + 41”.

“Oh”.

“Come vedi, 41 è un fattore comune a tutti e tre”.

“Uffa, risulta un numero composto”.

“Sì, 41 × 43. Prova anche a calcolare P(40)”.

“Questo sarà primo, dai”.

“Prova”.

“Allora: 40² + 40 + 41”.

“Che, volendo, puoi scrivere come 40² + 80 + 1”.

“E perché questa scrittura dovrebbe essere meglio?”.

“Perché è uguale a (40 + 1)², cioè 41²”.

“Oh, è composto anche questo”.

“Già”.

“Ma ci sarà un polinomio che funziona, no?”.

“Cioè un polinomio P(n) a coefficienti interi in una variabile n che assuma valori primi per ogni n intero positivo?”.

“Uh, mamma mia, che pignoleria. Sì, un polinomio fatto così”.

“Certo, eccotene uno: P(n) = 2”.

“Eh? Ma no, che genera numeri primi diversi!”.

“Allora lo vuoi anche non costante”.

“Sì! Quanto sono noiosi questi Veri Matematici”.

“Capisci che bisogna esser precisi, altrimenti poi non si sa bene quello che si vuole”.

“Va bene, va bene. Esiste un polinomio così?”.

“No”.

“Ma come? Tra tutti gli infiniti polinomi che si possono costruire, non ce n'è nemmeno uno che genera solo numeri primi?”.

“Nemmeno uno”.

“Santo cielo. E perché?”.

“Immagina che ne esista uno, per esempio uno che assuma il valore 43 quando n = 1”.

“Come fa il mio”.

“Esatto: possiamo scrivere che P(1) = 43”.

“Bene”.

“Ora prova a calcolare P(1 + 43k)”.

“Cos'è k?”.

“Un qualunque numero intero”.

“Eh, ma come faccio a calcolare P(1 + 43k) se non so come sia fatto P?”.

“Allora, partiamo dall'inizio. Supponiamo che esista P, che sarà scritto in maniera molto generica in questo modo:”.

P(n) = a_nxⁿ + a_n−1xⁿ⁻¹ + … + a₁x + a₀

“Gulp”.

“Prova a calcolare, adesso, P(1 + 43k)”.

“Vediamo, risulterà una cosa del genere:”.

P(1 + 43k) = a_n(1 + 43k)ⁿ + a_n−1(1 + 43k)ⁿ⁻¹ + … + a₁(1 + 43k) + a₀

“Bene. Comincia a svolgere”.

“Stai scherzando?”.

“No, ma non devi svolgere tutto tutto. Per esempio, da tutte quelle parentesi del tipo (1 + 43k) elevate a una qualche potenza puoi estrarre il primo termine, che è 1”.

“Eh, ma poi c'è un sacco di altra roba”.

“Certo, cominciamo dal facile: ognuna di quelle parentesi genera sicuramente un 1”.

“Va bene. Ognuno di quegli 1 viene moltiplicato per un coefficiente diverso”.

“E quindi puoi cominciare a scrivere una cosa del genere:”.

P(1 + 43k) = a_n + a_n−1 + … + a₁ + a₀ + (altra roba)

“Non mi sembra una scrittura molto matematica, però va bene”.

“Ti ricordi quanto faceva P(1)?”.

“Abbiamo detto 43”.

“E, però, se sostituisci 1 nel tuo generico polinomio cosa ottieni?”.

“Ah, facile, ottengo a_n + a_n−1 + … + a₁ + a₀”.

“Benissimo. Quindi sai che a_n + a_n−1 + … + a₁ + a₀ = 43”.

“Ah. Ma allora posso scrivere così:”.

P(1 + 43k) = 43 + (altra roba)

“Certo. Adesso concentriamoci sull'altra roba”.

“E come facciamo? Dobbiamo svolgere tutte quelle potenze di binomio, non si finisce più”.

“Non facciamolo. Sarai d'accordo con me se ti dico che lo sviluppo di qualunque potenza del tipo (1 + 43k)ⁿ contiene un termine uguale a 1, e tanti altri termini che contengono, almeno una volta, il fattore 43?”.

“Eh, sì, giusto. Tutti i termini dopo il primo 1 contengono le varie potenze di 43k. Non ricordo bene il calcolo dei coefficienti, però”.

“Beh, non importa ai fini dei calcoli che stiamo facendo. Senza conoscere nessuna regola, puoi immaginare di dover calcolare quella potenza in questo modo:”.

(1 + 43k)ⁿ = (1 + 43k)(1 + 43k) … (1 + 43k)

“Ah, certo”.

“Quando ti calcoli tutti i prodotti, vedi che c'è un solo caso in cui fai 1×1×…×1, mentre in tutti gli altri casi almeno un termine del tipo 43k lo devi prendere”.

“Giusto, e quindi un 43 c'è sempre”.

“Ottimo. Ed ecco allora che possiamo semplificare ulteriormente il calcolo che stavamo facendo, mettendo in evidenza il fattore comune 43:”.

P(1 + 43k) = 43 + 43(altra roba ancora)

“Bene, e quindi?”.

“E quindi P(1 + 43k) è divisibile per 43”.

“E allora?”.

“E allora non è primo, dunque P(n) non può assumere valori primi per ogni valore di n”.

“Ah!”.

“Volendo essere più precisi, bisognerebbe distinguere due casi nell'espressione P(1 + 43k) = 43 + 43(altra roba ancora)”.

“Quali?”.

“Se la parentesi (altra roba ancora) fosse uguale a 0, allora il risultato sarebbe 43, che è effettivamente un numero primo”.

“Allora potrebbe succedere?”.

“Eh, questo significherebbe che P(1 + 43k) dovrebbe essere uguale a 43 per infiniti valori di k”.

“E questo non è possibile?”.

“Lo è, ma un polinomio che assume infiniti valori uguali è un polinomio costante”.

“Ah, il caso banale P(n) = 43”.

“Già. Se vuoi un polinomio non costante e in grado di generare solo numeri primi, non ce la fai. Non esiste. Naturalmente 43 è solo un esempio, puoi rifare tutta la dimostrazione sostituendo, al posto di 43, un qualsiasi numero p primo. Quindi, niente da fare: non esiste un polinomio P(n) non costante a coefficienti interi in una variabile n che assuma valori primi per ogni n intero positivo”.

“Oh. Peccato”.

“Già”.

Minacce aliene — Parte 4

“Bene, quindi il problema diventa: se ciascuno dei numeri da 1 a n viene colorato di rosso o di blu, qual è il minimo valore di n per ottenere una progressione aritmetica monocromatica composta da 3, oppure 4, oppure k termini?”.

“Oh, due variabili?”.

“Eh, le cose si complicano”.

“Già mi pare un ottimo risultato affermare che un valore di n che risolve il problema esiste sempre”.

“E hai ragione, questo è il primo passo notevole. Dopo aver dimostrato l’esistenza di un tale n, van der Waerden ha provato anche a stabilirne un valore minimo. Il fatto è che questo valore minimo è enorme, così grande da non poter essere espresso nelle usuali notazioni a cui siamo abituati”.

“Eh? Come è possibile? La notazione scientifica permette di esprimere numeri enormi”.

“Che però sono ridicolmente piccoli se confrontati col numero trovato da van Der Waerden”.

“Incredibile”.

“Per definire il numero ha usato una successione di funzioni, che crescono sempre più velocemente”.

“Uhm, non capisco”.

“Aspetta, partiamo dal semplice. Non avrai difficoltà a immaginare la funzione DOPPIO(x), che raddoppia il suo ingresso”.

“Stai dicendo che DOPPIO(x) = 2x?”.

“Esatto”.

“E c’è bisogno di una funzione apposita?”.

“Per calcolare il doppio, certamente no. Per capire come è fatta la nostra successione di funzioni, invece, sì. Lasciami andare avanti”.

“Ok, vai”.

“Ora definisco la funzione ESPONENTE(x), che calcola il valore di 2 elevato a esponente x”.

“Una funzione esponenziale”.

“Sì, la cosa interessante è che questa funzione è definibile a partire da DOPPIO(x)”.

“In che modo?”.

“Cosa succede se calcoli per x volte il doppio di 1?”.

“Aspetta, allora… se calcolo 1 volta il doppio di 1, ottengo 2, e fin qua è facile. Se calcolo 2 volte il doppio di 1, ottengo 2 per 2, cioè 4. Se calcolo 3 volte il doppio di 1, ottengo 2 per 2 per 2… ah! Certo, se calcolo x volte il doppio di 1, ottengo 2 elevato a x, cioè ESPONENTE(x)”.

“Quindi possiamo dire che ESPONENTE(x) = DOPPIO(DOPPIO(...DOPPIO(1))), dove la funzione DOPPIO compare x volte”.

“Bello, comincio a capire”.

“Ora facciamo un altro passo, definiamo la funzione TORRE(x)”.

“Che immagino sia fatta dall'applicazione di x volte della funzione ESPONENTE”.

“Infatti.”.

“Da dove viene il nome TORRE?”.

“Prova a calcolare TORRE(3)”.

“Vediamo, TORRE(3) = ESPONENTE(ESPONENTE(ESPONENTE(1)))”.

“Ok, quindi partiamo da ESPONENTE(1)”.

“ESPONENTE(1) = DOPPIO(1), no?”.

“Certo”.

“E DOPPIO(1) = 2”.

“Giusto anche questo. Quindi TORRE(3) = ESPONENTE(ESPONENTE(2))”.

“Bene, allora adesso devo calcolare ESPONENTE(2), che è uguale a DOPPIO(DOPPIO(1)), cioè DOPPIO(2), cioè 4”.

“Infatti avevamo visto che ESPONENTE(2) calcola 2 elevato a 2, cioè 4”.

“Ah, ecco, vero. Quindi mi rimane da calcolare ESPONENTE(4)”.

“Si capisce meglio se calcoli ESPONENTE(2²), applicando direttamente l’esponenziale”.

“Applicando direttamente la definizione di ESPONENTE, verrebbe 2²²”.

“”Una torre di potenze. Ecco perché questa funzione si chiama TORRE: calcola torri di potenze.

“Non è come fare una potenza di una potenza?”.

“Eh, no, qui non ci sono parentesi: per calcolare una torre di potenze, si parte dall'alto. Per esempio, TORRE(4) è 2²²² = 2²⁴ = 2¹⁶, mentre ((2²)²)², che è la cosiddetta potenza di potenza, è uguale a 2⁸.

“Ok, ci sono”.

“Ora andiamo avanti, definiamo una nuova funzione, WOW(x). Ti anticipo che WOW non ha nessun significato se non quello di stupore, per quanto veloce cresce questa funzione”.

“Non ci posso credere”.

“Eh, in mancanza di nomi migliori… I numeri calcolati da WOW sono enormi. Naturalmente, WOW(x) è definita come TORRE(TORRE(…TORRE(1))), dove la funzione TORRE compare x volte”.

“Gulp. Chissà quanto vale WOW(4)”.

“Un numero enorme. WOW(4) = TORRE(TORRE(TORRE(TORRE(1))))”.

“Uhm, TORRE(1) è uguale a 2, fin qua è facile. Quindi mi rimane da calcolare TORRE(TORRE(TORRE(2)))”.

“Anche TORRE(2) è facile, no?”.

“Certo, è uguale a 2², cioè 4”.

“Ok, quindi ora devi calcolare TORRE(TORRE(4))”.

“TORRE(4) è una torre di 2 composta da 4 elementi, cioè 2²²², che è uguale a 65536”.

“Bene, ultimo passo, devi calcolare TORRE(65536)”.

“Argh”.

“O anche wow!”.

“Una torre di potenze composta da 65536 esponenti, una cosa impossibile da immaginare”.

“Esattamente”.

“E questo numero è quello trovato da van der Waerden?”.

“Oh, no, questo è ancora piccolo se confrontato con quello”.

“Cosa?”.

“Eh, sì. Per arrivare al numero trovato da van der Waerden, occorre immaginare questa successione di funzioni:”.

DOPPIO(1)
ESPONENTE(2)
TORRE(3)
WOW(4)
eccetera

“Ogni volta applichiamo tante volte la funzione precedente?”.

“Esattamente”.

“E dopo WOW che funzioni ci sono?”.

“Non sono stati definiti nomi per le funzioni successive. Sai come si fa, si definisce una regola e poi si va avanti così. Per scrivere i termini successivi si usa un nome generico, che è ACKERMANN”.

“Questo è un nome proprio, suppongo?”.

“Esatto, dal nome di chi l’ha definita. Una volta capito che a ogni passo si deve applicare la funzione precedente un certo numero di volte, possiamo definire la funzione ACKERMANN in questo modo:”.

ACKERMANN(1) = DOPPIO(1)
ACKERMANN(2) = ESPONENTE(2)
ACKERMANN(3) = TORRE(3)
ACKERMANN(4) = WOW(4)
eccetera

“Quell'eccetera fa paura”.

“Ed eccoci arrivati alla soluzione del problema proposto da van der Waerden”.

“Se ciascuno dei numeri da 1 a n viene colorato di rosso o di blu, qual è il minimo valore di n per ottenere una progressione aritmetica monocromatica composta da k termini?”.

“E la risposta è: ACKERMANN(k)”.

“Quindi, tornando al quesito iniziale, quello delle progressioni aritmetiche composte da 3 numeri dello stesso colore, siamo sicuri di trovarne se prendiamo i numeri che vanno da 1 a ACKERMANN(3), giusto?”.

“Giusto”.

“E ACKERMANN(3) è uguale a TORRE(3), cioè 16. Uhm, non avevo dimostrato che anche solo prendendo i numeri da 1 a 9 troverò sempre una progressione aritmetica monocolore?”.

“Sì, certo. La stima ACKERMANN(k) è una condizione sufficiente per essere sicuri di trovare la progressione monocolore. Non è detto che, con ulteriori studi, non si possa migliorare la stima. Anzi, un miglioramento è già stato fatto: nella dimostrazione originale di van der Waerden compare il numero ACKERMANN(k), ma successivamente, nel 1987, il matematico israeliano Sharon Shelah ha dimostrato che ci si può fermare a WOW(k)”.

“Ah, ecco. Rimane comunque un numero colossale”.

“E, per quanto riguarda il quesito iniziale, ancora più inutile: WOW(3) è uguale a 65536”.

“Se k aumenta, però, WOW(k) rimane a un livello inferiore rispetto a ACKERMANN(k), vero?”.

“Esatto. Sappi che Graham, un altro matematico che ha lavorato alla teoria di Ramsey, ha offerto un premio di 1000 dollari per chiunque sia in grado di dimostrare che, al posto di WOW(k), si può usare TORRE(k). O a chi sia in grado di dimostrare il contrario, cioè che TORRE(k) è un numero troppo basso”.

“Anche in questo campo, quindi, ci sono molti problemi aperti”.

“Già. Quella di Ramsey è una teoria affascinante, proprio perché si occupa di trovare strutture ordinate all'interno di strutture apparentemente casuali. Un articolo divulgativo di Graham e Spencer, comparso su Le Scienze nel 1990, si concludeva con questa domanda: oggi, grazie alla teoria di Ramsey, siamo in grado di riconoscere con facilità le costellazioni del cielo notturno. Quali configurazioni potremmo mai trovare in insiemi che sono ACKERMANN(9) volte più grandi?”.

“Speriamo di non trovare alieni cattivi, però”.

---

Questa è l'ultima parte di un articolo uscito sulla rivista Archimede, numero 4, del 2017. La prima parte è qua, la seconda qua, la terza qua.

Minacce aliene — Parte 3

“Come disse il matematico Theodore Motzkin descrivendo la teoria di Ramsey: complete disorder is impossible”.

“Uh, chissà cosa ne pensano i filosofi”.

“Eh, non è un’affermazione da poco: se l’insieme è abbastanza grande, emergeranno sempre strutture ordinate. Prima ancora che Ramsey sviluppasse tutta la sua teoria, i matematici hanno studiato strutture emergenti non solo in ambito geometrico, ma anche in ambito aritmetico”.

“Per esempio?”.

“Per esempio, nel 1926 un matematico olandese, Bartel van der Waerden, si mise a studiare strutture presenti all’interno di successioni aritmetiche ”.

“Che, ehm, sarebbero?”.

“Le successioni aritmetiche sono successioni di numeri in cui la differenza tra due termini consecutivi è sempre costante. Detto in un altro modo, ogni termine della successione si ottiene dal precedente aggiungendo sempre la stessa costante. Per esempio, la successione 4, 7, 10, 13, 16 è una successione aritmetica”.

“Vero, ogni volta aggiungi 3”.

“Sì: per definire una successione aritmetica serve il punto di partenza, che nel nostro caso è 4, e la costante, che i Veri Matematici chiamano ragione”.

“Che nel nostro caso è 3”.

“Sì. Ora, i problema che studiava van der Waerden è questo: scriviamo tutti i numeri da 1 a 9 in rosso oppure in blu. È sempre vero che possiamo trovare tre numeri rossi o tre numeri blu che formano una progressione aritmetica?”.

“Uhm, con così pochi numeri non mi sembra un problema difficile”.

“Hai ragione, questo è un esempio, giusto per capire come funziona il problema, Puoi risolvere il quesito senza sapere nulla della teoria di Ramsey”.

“Allora ci provo. Vediamo un momento, mi sembra utile partire dal centro della successione. Provo a vedere cosa succede se i numeri 4 e 6 sono colorati di rosso”.

1, 2, 3, 4, 5, 6, 7, 8, 9

“Molto bene”.

“Devo sicuramente evitare la progressione 4, 5, 6. E quindi devo colorare 5 di blu”.

1, 2, 3, 4, 5, 6, 7, 8, 9

“Pefetto”.

“Però così non ho escluso tutte le possibili progressioni. Per esempio, potrebbe esserci 2, 4, 6. Oppure anche 4, 6, 8. Ok, coloro di blu anche 2 e 8”.

1, 2, 3, 4, 5, 6, 7, 8, 9

“Uhm”.

“Cosa succede? Ah! Ho colorato di blu 2, 5, 8, che sono in progressione aritmetica!”.

“E quindi la tua supposizione iniziale non funziona”.

“Hai ragione. Allora 4 e 6 non possono essere colorati entrambi di rosso. E, simmetricamente, nemmeno di blu. Significa che devono avere due colori diversi!”.

“Forse”.

“Giusto, se hanno colori diversi posso sperare di evitare progressioni monocromatiche, ma devo capire se ci riesco. Allora, proviamo. Coloro 4 di rosso e 6 di blu”.

“Senza perdita di generalità”.

“wlog!”.

“Già”.

“Ahh, ho usato wlog anche io, come fanno i Veri Matematici! Allora, parto da qua:”.

1, 2, 3, 4, 5, 6, 7, 8, 9

“Bene”.

“Direi di poter colorare il 5 come voglio, anche qui non perdo di generalità se lo coloro di rosso o di blu: in ogni caso non ottengo una progressione aritmetica monocromatica”.

“Giusto”.

“Quindi lo coloro di rosso. Ora la situazione è questa:”.

1, 2, 3, 4, 5, 6, 7, 8, 9

“Se 5 fosse blu, la situazione sarebbe simmetrica”.

“Sì, vedo. Con questa configurazione, mi devo preoccupare di non avere il 3 rosso. Se invece 5 fosse blu, mi dovrei preoccupare di non avere il 7 blu. Ho capito. E allora coloro di blu il 3”.

1, 2, 3, 4, 5, 6, 7, 8, 9

“E così hai evitato la progressione rossa di ragione 1. Come prosegui?”.

“Ho già due numeri blu, devo evitare di avere il terzo in progressione. Direi quindi che 9 debba essere rosso”.

1, 2, 3, 4, 5, 6, 7, 8, 9

“Bene, così hai evitato di avere 3, 6, 9 monocolore. Hai altre possibilità?”.

“Uhm. Sì, bisogna evitare che 1, 5, 9 sia tutta rossa, quindi 1 va colorato di blu”.

1, 2, 3, 4, 5, 6, 7, 8, 9

“Bene, vai avanti”.

“Vedo che 5, 7, 9 rischia di essere tutta rossa, quindi coloro 7 di blu. Però devo evitare che 6, 7, 8 sia blu, quindi coloro 8 di rosso”.

1, 2, 3, 4, 5, 6, 7, 8, 9

“Ormai è fatta”.

“Per evitare che 1, 2, 3 sia tutta blu, devo colorare 2 di rosso. Ehi, ma se 2 è rosso dopo ho 2, 5, 8 tutta rossa!”.

“E quindi?”.

“E quindi non ce la faccio a colorare i numeri da 1 a 9 con due colori in modo da non ottenere successioni aritmetiche monocromatiche”.

“Ancora una volta, emerge un ordine”.

“Già. Bell’esercizio, ma van der Waerden non avrà studiato questo problema, vero?”.

“Beh, questo era un esempio semplice. Sai come fanno i Veri Matematici quando risolvono un problema: partendo dal caso semplice, guardano se possono...”.

“...generalizzarlo, ormai ho capito”.

---

Questa è la terza parte di un articolo uscito sulla rivista Archimede, numero 4, del 2017. La prima parte è qua, la seconda qua.

Minacce aliene — Parte 2

“Ora, naturalmente ai matematici piace generalizzare”.

“Capirai”.

“Eh, è nella loro natura. Si sono posti quindi questa domanda: se su un grafo formato dai lati e dalle diagonali di un esagono si trova sempre un triangolo monocromatico, che succede con un pentagono? Un quadrilatero? Qual è il numero minimo di vertici che deve avere un grafo completo affinché, colorando i suoi spigoli con due colori, si possa essere certi di formare sempre un triangolo monocromatico?”.

“Beh, certamente non più di 6, no?”.

“Infatti. Se riusciamo a trovare un triangolo che ci piace in un grafo con 6 vertici, aumentando i vertici aumentano anche gli spigoli, e quindi aumentano le possibilità di trovare triangoli monocromatici”.

“Quindi la domanda diventa: potrebbe essere 5, o meno ancora?”.

“Ed ecco la risposta:”.



“Uhm. Un pentagono”.

“Un pentagono con 5 spigoli colorati di rosso e 5 colorati di blu. Osservalo bene: ci sono triangoli monocromatici?”.

“Eh, no”.

“Quindi esiste almeno una colorazione di questo grafo che non produce triangoli monocromatici”.

“E quindi la nostra ricerca è finita: il numero minimo di vertici per avere i triangoli monocromatici è 6. Ottimo, fine della generalizzazione”.

“Non c’è mai fine alle generalizzazioni”.

“Capirai”.

“Per esempio: troverò triangoli anche se uso tre colori? Quattro? Di più?”.

“Ah. Non sembra facile”.

“Non lo è. Ma si può generalizzare anche in un altro modo: posso colorare con 2 colori in modo da trovare triangoli del primo o quadrati del secondo?”.

“Uh, che delirio”.

“E trovare le risposte a queste domande è difficilissimo. Anzi, alcune di queste risposte non le conosciamo ancora”.

“Davvero?”.

“Eh, sì. Il numero che abbiamo calcolato poco fa, il minimo numero di vertici che deve avere un grafo perché si possa sempre trovare al suo interno un triangolo blu o un triangolo rosso, si chiama numero di Ramsey per tre rosso e tre blu, e si indica con R(3,3). Erdős ha detto, una volta: supponete che gli alieni invadano la Terra e che minaccino di annientarla se entro un anno gli uomini non riusciranno a trovare il numero di Ramsey per cinque rosso e cinque blu. Potremmo far scendere in campo le menti migliori e i calcolatori più veloci del pianeta e probabilmente entro un anno riusciremmo a calcolare quel valore. Se tuttavia gli alieni volessero il numero di Ramsey per sei rosso e sei blu. non avremmo altra scelta se non un attacco preventivo.”.

“Eh eh, non credevo fosse così difficile”.

“Lo è, eccome se lo è. I matematici sono riusciti a dimostrare che un numero di Ramsey esiste sempre, qualunque sia il numero di colori e il numero di lati da colorare. Il problema è che non sappiamo quali siano, questi numeri, se non in pochi casi”.

“Ma pensa”.

“Già: per quanto riguarda il famoso R(5,5) di Erdős, nel 1989 si è scoperto che questo numero deve essere almeno 43. Mentre nel 2017, l'anno scorso, si è capito che non può essere più grande di 48”.

“Una scoperta recentissima!”.

“Eh, sì. E, dato che fregiarsi del titolo di potenziale salvatore dagli alieni dovrebbe essere uno stimolo enorme per un Vero Matematico, puoi renderti conto della difficoltà del problema”.

“Quindi di pensare a risolvere R(6,6) non se ne parla proprio, suppongo. Meglio sviluppare la tecnologia per combattere gli alieni?”.

“Le ultime stime per R(6,6) sono del 1965. Da allora, nessuno è riuscito a fare meglio. Sappiamo solo che R(6,6) è un numero compreso tra 102 e 165”.

“Eppure non sono numeri così grandi, come è possibile che non si riescano a migliorare le stime?”.

“Ricordati che i numeri di cui stiamo parlando sono i vertici. Sai quanti spigoli ha un grafo completo con 100 vertici?”.

“Eh, al momento no...”.

“Prova a pensare: quanti spigoli partono da ogni vertice?”.

“Eh, direi 99, uno per ogni vertice, tranne quello da cui parto”.

“E dato che ci sono 100 vertici...”.

“Ho 100×99 spigoli?”.

“Non esattamente. In questo modo, ogni spigolo verrebbe contato due volte, una per il vertice di partenza e una per quello di arrivo”.

“Ah, allora devo dividere per due il risultato!”.

“Già. Quindi un grafo con 100 vertici ha 50×99 spigoli, cioè 4950”.

“Anche questo non è un numero così esagerato, magari con un computer si può fare qualche stima, no?”.

“Eh, sai quante possibili colorazioni si possono fare, anche soltanto con due colori?”.

“Uhm, non saprei come calcolarle”.

“Non è difficile: per ogni spigolo hai due scelte, o lo colori di blu o di rosso. Quindi due scelte per il primo spigolo, moltiplicate per altre due scelte per il secondo, e così via”.

“Gulp, devo moltiplicare 2 per sé stesso 4950 volte”.

“Esatto. Un numero composto da 1491 cifre. Se passi a un grafo con 120 vertici ti risulta un numero di configurazioni da provare composto da 2150 cifre”.

“Comincia a diventare lunghetta”.

“E non è finita: in ognuna delle configurazioni devi cercare degli esagoni”.

“Argh”.

“In un grafo completo sei vertici scelti a caso sono sempre collegati da sei spigoli, quindi per calcolare il numero di esagoni ti basta calcolare il numero di possibili scelte di sei vertici”.

“E come faccio?”.

“Beh, il primo vertice lo puoi scegliere in 100 modi diversi, il secondo in 99, il terzo in 98, e così via, fino al sesto vertice, che puoi scegliere in 95 modi. In realtà queste scelte non sono tutte diverse, puoi mescolare i sei lati in 6! modi, come se fossero le lettere di un anagramma”.

“Totale: 100×99×98×97×96×95. Poi divido per il fattoriale di 6, vediamo… fa 1 miliardo e rotti. E dovrei controllarli tutti per ognuno dei grafi? Roba da matti”.

“Come vedi, non esiste ancora la potenza di calcolo necessaria per poter affrontare questo problema con la forza bruta. Meglio attaccare gli alieni”.

“Ma allora come hanno fatto a fare quelle stime di cui parlavi? ”.

“Erdős è stato il primo a farle, e ha escogitato un metodo che, a prima vista, è spiazzante. I Veri Matematici lo chiamano metodo probabilistico”.

“Uhm, usa la probabilità? Si può dimostrare un teorema con considerazioni di probabilità? Mi pareva che i teoremi dessero certezze”.

“Eh, è proprio per questo che il metodo è spiazzante: Erdős ha usato la probabilità per arrivare a una vera dimostrazione”.

“Uh”.

“Erdős partiva da questa idea: supponiamo di colorare gli spigoli di un grafo in maniera casuale, tirando una moneta. Se viene testa coloro lo spigolo di rosso, se viene croce lo coloro di blu”.

“Va bene”.

“Ora, supponiamo di voler fare una stima dal basso di R(34,34)”.

“Un numero impossibile da calcolare, se già R(6,6) è intrattabile”.

“Esattamente: questo esempio serve per capire la potenza del metodo probabilistico. Ci chiediamo, ad esempio, se un grafo con un milione di vertici potrebbe essere sufficiente per garantire la presenza di poligoni di 34 lati monocromatici”.

“Mi immagino il disegno”.

“Eh eh. Ora, un grafo completo con 34 vertici ha 561 spigoli”.

“Vediamo se ho capito: per ogni spigolo posso scegliere il primo vertice in 34 modi, e il secondo in 33, però così facendo conto gli spigoli due volte, quindi dopo aver moltiplicato 34 per 33 devo dividere per 2. Sì, risulta 561”.

“Esattamente. Ora la probabilità che questi 561 vertici siano tutti dello stesso colore”.

“Ho probabilità un mezzo per ogni lato, quindi dovrebbe essere (1/2)⁵⁶¹”.

“Bene, però i colori sono due”.

“Quindi moltiplico per due, e mi viene (1/2)⁵⁶⁰”.

“Ok. Quanti poligoni di 34 lati abbiamo in un grafo di un milione di vertici?”.

“Oh, tanti. Avevamo visto che già il calcolo con 100 dava un numero molto grande”.

“Eh, sì. Procedendo allo stesso modo, risulta che il numero di combinazioni è circa 3×10¹⁶⁵. A questo punto, possiamo chiederci quanto vale la probabilità di trovare un poligono di 34 lati monocromatico”.

“Devo moltiplicare la probabilità che un singolo poligono sia monocromatico con il numero dei poligoni, no?”.

“Vero”.

“Quindi devo moltiplicare (1/2)⁵⁶⁰ per 3×10¹⁶⁵”.

“Quanto viene?”.

“Poco meno di un millesimo”.

“Non importa il valore esatto, ciò che conta è che il risultato sia minore di 1”.

“Perché?”.

“Perché se tutte le possibili colorazioni di spigoli contenessero poligoni di 34 lati monocromatici, allora questa probabilità dovrebbe essere uguale a 1”.

“Ah, vero: avremmo la certezza di trovare un poligono monocromatico”.

“Dunque, se la probabilità è minore di uno, ciò significa che esiste almeno una colorazione che non ci dà poligoni monocromatici”.

“E quindi?”.

“E quindi un milione di vertici sono troppo pochi: abbiamo trovato una limitazione inferiore per R(34,34)”.

“Ah. Non è stato così difficile”.

“Per questo il metodo è potente: permette di capire qualcosa in un universo di calcoli proibitivi”.

“Ordine nel caos”.

“Proprio così. Come disse il matematico Theodore Motzkin descrivendo la teoria di Ramsey: complete disorder is impossible”.

---

Questa è la seconda parte di un articolo uscito sulla rivista Archimede, numero 4, del 2017. La prima parte è qua.

Minacce aliene — Parte 1

Gli alieni invadono la Terra e minacciano di annientarla se entro un anno gli uomini non riusciranno a trovare il numero di Ramsey per cinque rosso e cinque blu. Potremmo far scendere in campo le menti migliori e i calcolatori più veloci del pianeta e probabilmente entro un anno riusciremmo a calcolare quel valore. Se tuttavia gli alieni volessero il numero di Ramsey per sei rosso e sei blu, non avremmo altra scelta se non un attacco preventivo.

“Com’è questa faccenda degli alieni?”.

“Te lo spiego con un gioco”.

“Oh, bene!”.

“Abbiamo questo schema. A turno dobbiamo colorare i segmenti che collegano i punti: io uso il rosso, tu usi il blu. Naturalmente se uno di noi ha colorato un segmento, l’altro non può colorarlo di nuovo”.



“Ok”.

“Perde il primo che forma un triangolo. Comincia tu ”.

“Uhm”.

“Cosa c’è?”.

“Di solito, quando un Vero Matematico propone un gioco, è sicuro di vincere”.

“Eh, c’è del vero in quello che dici”.

“E quindi, se le cose stanno così, io non ho nemmeno la speranza di riuscire a pareggiare. Figuriamoci se posso pensare di vincere”.

“In effetti in questo gioco non è possibile pareggiare, nemmeno giocando male”.

“Davvero? E come è possibile? Non dirmi che, anche colorando i lati a caso, si riesce sempre a creare un triangolo”.

“E invece è proprio così. In questo gioco è impossibile non avere un triangolo. Prova: colora a caso alternativamente di rosso e di blu i segmenti, e guarda come va a finire”.




“Uh, è vero. Però, se non sbaglio, un caso favorevole non dimostra un’affermazione, no?”.

“Molto bene, vedo che i miei sforzi hanno prodotto qualche risultato”.

“Eh, so che i Veri Matematici tengono molto alle loro dimostrazioni, e so che questa non lo è. E mi è venuta anche la curiosità di sapere come si possa affermare che è sempre possibile trovare un triangolo colorato”.

“Bene, bene. La dimostrazione non è difficile: il campo di gara di questo gioco...”.

“A proposito: ha un nome?”.

“Sì, si chiama Sim. Dicevo, il campo di gara è quello che i Veri Matematici chiamano grafo completo composto da 6 vertici”.

“Un esagono con tutte le sue diagonali”.

“Esatto. Qui trattiamo le diagonali vere e proprie e i lati dell’esagono allo stesso modo: li chiamiamo spigoli. Da ogni vertice escono naturalmente cinque spigoli”.

“Naturalmente”.

“Quindi almeno tre verranno colorati allo stesso modo”.

“Uhm, perché?”.

“Vuoi assegnare ogni diagonale a un colore: è come se tu dovessi distribuire cinque maglie in due cassetti, quello rosso e quello blu”.

“Cosa c’entrano le maglie?”.

“E’ un esempio: distribuisci cinque maglie in due cassetti. Quante maglie andranno in ogni cassetto?”.

“Boh, dipende”.

“Mettere una maglia in un cassetto corrisponde a colorare uno dei cinque spigoli. Riesci a fare in modo che nessuno dei due cassetti contenga tre maglie?”.

“Eh, no, è impossibile: posso mettere due maglie in ogni cassetto, per un totale di quattro maglie. Poi però mi rimane la quinta, e da qualche parte devo mettere pure quella”.

“Quindi uno dei due cassetti avrà almeno tre maglie”.

“Perché almeno?”.

“Perché potresti anche mettere tutte le maglie nello stesso cassetto. Qualunque cosa tu faccia, un cassetto conterrà certamente più di due maglie”.

“Va bene”.

“E quindi, comunque tu scelga una colorazione dei cinque spigoli che partono da un vertice dell’esagono, almeno tre di essi avranno lo stesso colore”.

“D’accordo”.

“Supponiamo che sia il blu”.

“Immagino che la dimostrazione con tre spigoli rossi sia simmetrica a questa”.

“Esattamente. I Veri Matematici usano così spesso queste simmetrie che hanno coniato un acronimo apposta: invece di scrivere che la scelta che hanno fatto non fa perdere di generalità al problema, scrivono wlog”.

“Una funzione? Una specie di logaritmo? Che roba è?”.

“Un acronimo: without loss of generality. Alcuni lo usano anche quando parlano”.

“Sono pazzi”.

“Eh, un po’. Ma andiamo avanti: chiamiamo V il vertice che abbiamo scelto. V è connesso con altri tre vertici, che possiamo chiamare R, S e T. Se uno qualsiasi degli spigoli RS, ST o RT è blu, allora abbiamo trovato un triangolo blu. Se nessuno dei tre invece è blu...”.

“...allora abbiamo un triangolo rosso!”.

“Quello di vertici R, S e T, esatto.”.

“E quindi è vero che in una qualsiasi colorazione degli spigoli di questo grafo troviamo sempre un triangolo con i lati dello stesso colore”.

“Una qualsiasi colorazione fatta con due soli colori, naturalmente”.

“Ah, sì, certo. Dunque, al gioco del Sim non si può pareggiare”.

“Proprio così. Ora, naturalmente ai matematici piace generalizzare”.

“Capirai”.

---

Questa è la prima parte di un articolo uscito sulla rivista Archimede, numero 4, del 2017.

Come di consueto, classifiche (questa volta non olimpiche)

Ecco la classifica definitiva dei campionati europei 2018, ordinata come al solito secondo la proposta di Simon Tatham.

Uno stato X è stato migliore di un altro stato Y se il medagliere di Y può essere trasformato nel medagliere di X mediante una sequenza di aggiunte di medaglie oppure di sostituzione di medaglie basse con medaglie alte.

L'inverso del teorema di Pitagora

“L'inverso del teorema di Pitagora?”.

“Eh, sì”.

“Ma cosa significa inverso?”.

“Ti giro la domanda: cosa dice il teorema di Pitagora?”.

“Dice che il quadrato costruito sull'ipotenusa è equivalente alla somma dei quadrati costruiti sui cateti”.

“No”.

“Come no?”.

“No: prendi un triangolo equilatero di lato 1 e dimmi se è vero che 1 + 1 = 1”.

“Ma cosa c'entra un triangolo equilatero? Il triangolo deve essere… Ok, non l'ho detto”.

“Già”.

“Riprovo: il teorema di Pitagora dice che in un triangolo rettangolo il quadrato costruito sull'ipotenusa è equivalente alla somma dei quadrati costruiti sui cateti”.

“Ottimo. Qual era l'errore, quindi?”.

“Avevo dimenticato di specificare il contesto in cui si applica il teorema”.

“Sì, avevi dimenticato l'ipotesi: il teorema di Pitagora vale se il triangolo è rettangolo”.

“E l'inverso, allora?”.

“L'inverso risponde a quest'altra domanda: è vero o no che il quadrato costruito sull'ipotenusa è equivalente alla somma dei quadrati costruiti sui cateti solo se il triangolo è rettangolo?”.

“Ovvio”.

“Mica tanto ovvio: prendi un triangolo, indica con a, b e c i suoi tre lati, sai che vale la relazione a² + b² = c². Puoi dire che il triangolo è rettangolo?”.

“Ma per forza, no?”.

“NO! NON ESISTONO DIMOSTRAZIONI PER FORZA!”.

“Ok, ok, mamma mia che brutto carattere”.

“Scusa eh, ma se tu sai che il verificarsi di qualcosa implica il verificarsi di qualcos'altro, puoi dire che automaticamente il verificarsi della seconda cosa implica il verificarsi della prima?”.

“Fino a pochi secondi fa avrei detto di sì, ma mi pare di capire che invece non sia così. Ho un po' paura a chiedere perché, però”.

“Prendi un numero divisibile per 4: puoi dire che è divisibile anche per 2?”.

“Certo”.

“Perché?”.

“Perché se contiene 4 contiene anche 2, dato che 4 è divisibile per 2”.

“Questa proprietà vale per tutti i numeri divisibili per 4?”.

“Certo”.

“Puoi dire il contrario? Puoi dire che ogni numero divisibile per 2 è divisibile anche per 4?”.

“Eh, no, non tutti. Se prendo 8 va bene, se prendo 6 no”.

“Quindi questo è un esempio di teorema che funziona in una sola direzione: il suo inverso non è un teorema”.

“Ah”.

“È vero che un quadrato ha quattro angoli retti?”.

“Certo”.

“È vero il contrario? Che se un quadrilatero ha quattro angoli retti allora è un quadrato?”.

“Eh, no, un rettangolo ha quattro angoli retti ma non è un quadrato”.

“Non è detto che lo sia, volendo essere precisi”.

“Può esserlo?”.

“Beh, sì. Se la definizione di rettangolo è quadrilatero con quattro angoli retti, allora esso potrebbe anche essere un quadrato. Ma non è vero che ogni rettangolo è un quadrato”.

“Va bene, ho capito”.

“Tornando al teorema di Pitagora: è vero che se in un triangolo il quadrato di un lato è equivalente alla somma dei quadrati degli altri due lati, allora quel triangolo è rettangolo”.

“A questo punto non so più quale sia la risposta. Direi di sì, ma non so perché”.

“La risposta è sì, anche se ormai il motivo per cui quella risposta è affermativa è sparito dai libri scolastici”.

“Perché?”.

“Non ne ho idea. Pigrizia? Poca voglia di spiegare? Chissà”.

“Ma è una dimostrazione difficile?”.

“No, non direi. Te la mostro, nella versione di Euclide. Cominciamo da un triangolo ABC per il quale vale la relazione AB² + AC² = BC². Eccolo qua”.

“Ok. Quindi non sappiamo se è rettangolo, e vogliamo dimostrarlo”.

“Esatto: vogliamo dimostrare che l'angolo in A è retto”.

“Va bene, cominciamo”.

“Dobbiamo fare una costruzione: costruiamo un segmento DA che forma un angolo retto con CA”.

“Quindi prolunghiamo AB? Ma non sappiamo se l'angolo A è retto oppure no”.

“Esatto, ottimo: non prolunghiamo, ma costruiamo noi un angolo che sia retto. Questo vuol dire che ancora non possiamo sapere se i tre punti D, A e B sono allineati oppure no”.

“Ho capito. Quanto deve essere lungo il segmento DA?”.

“Tanto quanto AB”.

“Perfetto, eccolo qua”.

“Poi congiungiamo D con C e formiamo un triangolo”.

“E, questa volta, sappiamo che è un triangolo rettangolo”.

“Proprio così, ecco la figura completa”.

“Ora che si fa?”.

“Scriviamo un po' di uguaglianze. La prima è questa, sei d'accordo? DA² = AB²”.

“Eh, beh, sì, se DA è uguale a AB lo saranno anche i loro quadrati”.

“Già. Ora aggiungiamo, a destra e a sinistra dell'uguale, la stessa quantità, cioè AC²”.

“Così? DA² + AC² = AB² + AC²”.

“Esatto. Ora guarda cosa c'è a sinistra dell'uguale”.

“C'è la somma dei quadrati di DA e AC… Ah! Il triangolo DAC è rettangolo, quindi per quello posso applicare il teorema di Pitagora, vero?”.

“Certo: questa dimostrazione si appoggia su quel teorema. Prima dimostri il teorema diretto, poi questo”.

“Ah. Ma si può?”.

“Certo, non stai facendo le cose in modo circolare: prima dimostri il teorema di Pitagora, senza usare questo teorema, poi dimostri questo usando quello che hai appena dimostrato”.

“Ok, mi piace. Quindi siamo arrivati al fatto che a sinistra dell'uguale si può applicare il teorema di Pitagora: lo facciamo?”.

“Sì, e quindi possiamo sostituire, al posto di DA² + AC², il quadrato dell'ipotenusa, cioè DC²”.

“A destra dell'uguale, però, non posso farlo, perché non so se il triangolo sia rettangolo oppure no”.

“No, ma non ti serve saperlo: per la parte di destra puoi usare direttamente l'ipotesi. Tu sai già quanto vale quella somma”.

“Ehi, ma è vero, è proprio l'ipotesi! So che AB² + AC² è uguale a BC²”.

“Certo, e quindi l'uguaglianza è diventata DC² = BC²”.

“Ma allora posso dire che DC e BC sono uguali”.

“Proprio così: quindi i due triangoli ABC e ACD hanno i tre lati ordinatamente congruenti”.

“E allora sono triangoli congruenti, no?”.

“Sì, è così, per il cosiddetto terzo criterio di congruenza dei triangoli. A questo punto, abbiamo concluso: se i due angoli DAC e CAB sono congruenti…”.

“…dato che DAC è retto, dovrà esserlo anche CAB!”.

“Ed ecco fatto”.

“Avevi ragione, non era difficile. Dicevi che sui libri di scuola non si trova più questa dimostrazione, ma perché? Non è difficile, mi sembra un peccato non metterla”.

“Anche a me”.