Visualizzazione post con etichetta teoria dei numeri. Mostra tutti i post
Visualizzazione post con etichetta teoria dei numeri. Mostra tutti i post

giovedì 7 febbraio 2013

Palle da cannone e pacchetti di sfere

La leggenda vuole che la notte precedente il 29 ottobre 1618, prima di essere decapitato per una presunta congiura contro re Giacomo I, dopo una dura detenzione durata quasi tre lustri, Sir Walter Raleigh abbia scritto la poesia The Lie, di cui questa è una strofa: 

Tell men of high condition, 
That manage the estate, 
Their purpose is ambition; 
Their practice only hate. 
And if they once reply, 
Then give them all the lie. 

In realtà l’opera era già comparsa in una raccolta miscellanea nel 1608 (e in un manoscritto del British Museum datato 1596), e probabilmente non è neanche sua. Mi piace tuttavia l’attribuzione romantica a un personaggio come Raleigh, favorito di Elisabetta I d’Inghilterra, esploratore, poeta, spia, corsaro, nonché colui che introdusse in Gran Bretagna la patata e il tabacco. 

Un’altra attribuzione a Raleigh, questa più veritiera, è quella di aver posto per primo il problema delle palle da cannone, il prototipo di quello generale dell’impacchettamento delle sfere.. Durante la sfortunata spedizione per insediare una colonia inglese sull’isola di Roanoke, vicino alla Virginia, tra il 1585 e il 1586, Raleigh chiese al matematico Thomas Harriot, che sulla nave fungeva da naturalista, astronomo e interprete (di lingua algonchina!), se era possibile sapere quante palle di cannone vi fossero in una piramide a base quadrata da esse formata, senza contarle una ad una. A quei tempi si costruiva un telaio di legno di forma triangolare o quadrata dentro il quale si impilavano le palle a piramide. In entrambi i casi si tratta di una struttura cubica centrata sulle facce, orientata diversamente rispetto al piano orizzontale. 

Harriot era il tipico intellettuale polivalente dell’epoca: matematico, fisico, astronomo, etnografo, fu in corrispondenza con Keplero. La relazione del viaggio in Virginia, in cui forniva anche gli elementi fondamentali della lingua dei nativi algonchini, uscì nel 1588 e resta l’unico testo pubblicato mentre egli era in vita. Alla sua morte lasciò ai suoi esecutori testamentari il compito di pubblicare un suo testo d’algebra, ma essi lo fecero rimaneggiandolo e togliendo le parti più innovative. Così l’Artis Analyticae Praxis, uscito postumo nel 1631, fu privato di inedite intuizioni sulle radici dei numeri negativi e sui numeri complessi. Il resto della sua opera scientifica, più di 400 fogli vergati con minuscola grafia, non fu stampato, finché non fu riscoperto tra il XIX e il XX secolo. Gli appunti astronomici di Harriot offrono la testimonianza delle sue precoci osservazioni telescopiche: essi contengono una mappa della Luna disegnata intorno al 1611, osservazioni dei satelliti di Giove fatte nello stesso periodo di quelle che Galileo pubblicò nel Sidereus Nuncius del marzo 1610, e appunti sulle osservazioni delle macchie solari che egli fece con il telescopio il 18 dicembre 1610, cioè qualche mese prima di quanto dichiarato da Galileo. 


Harriot non ebbe difficoltà a risolvere il problema posto da Raleigh. Se k è il numero di palle da cannone poste lungo il lato della piramide a base quadrata, il loro numero totale n è dato da:

  



Ad esempio, se k = 6, allora n = 91. I numeri che rappresentano le soluzioni dell’equazione sono chiamati numeri piramidali quadrati. I primi sono 1, 5, 14, 30, 55, 91, 140, 204, 285, 385, 506, 650, 819 (Sequenza A000330 della OEIS-On-Line Encyclopedia of Integer Sequences). 

Un’altra versione, più specifica, del problema delle palle da cannone chiede qual è il più piccolo numero di palle che può essere disposto in un quadrato n × n su cui poi si impilano altri quadrati di palle a formare una piramide alta k palle. In pratica, qual è il più piccolo quadrato che è anche un numero piramidale? La risposta è la soluzione più piccola dell’equazione diofantea:

 

Da cui risulta che k = 24, n = 70, che corrisponde a 4.900 palle. Nel 1875 Edouard Lucas congetturò che questa è anche l’unica soluzione possibile, e, nel 1918, George Neville Watson provò che aveva ragione. 



Più in generale, ci si può chiedere che cosa succede se la base della piramide è un poligono regolare qualsiasi. In pratica, quali sono i numeri piramidali triangolari, pentagonali, esagonali, ecc.? La formula generale, per una base a forma di poligono regolare con r lati è data da:


Nel caso particolare di una piramide a base triangolare (tetraedro), la formula diventa:




L’interesse di Thomas Harriot per le sfere non si limitava solo alle palle da cannone. Egli era un atomista nel senso classico del termine (come Democrito e Lucrezio), e pensava che la comprensione di come si impacchettano le sfere era fondamentale per capire come sono disposti i costituenti fondamentali della natura. Egli svolse numerosi esperimenti di ottica e divenne un’autorità in questo campo. Così, quando, nel 1609, Keplero gli scrisse per avere informazioni per dare maggiori base scientifiche alle sue teorie ottiche, l’inglese non solo gli inviò dati sul comportamento dei raggi luminosi che passano attraverso il vetro, ma gli espose anche le sue idee sul problema della disposizione delle sfere. 

L’effetto di queste idee deve essere stato notevole, visto che il tedesco pubblicò nel dicembre 1611 un libretto dal titolo Strena sue de nive sexangula (Sul fiocco di neve a sei angoli), che avrebbe influenzato la scienza della cristallografia nei due secoli successivi e che conteneva la cosiddetta congettura di Keplero sul modo più efficace di impacchettare le sfere. Egli sosteneva che non esiste alcun modo di sistemare delle sfere nello spazio con densità media superiore a quella dell'impacchettamento cubico a facce centrate o a quella dell'impacchettamento esagonale. La densità η di questi due modi di sistemare le sfere vale:

 

Secondo Keplero, nessun altro impacchettamento di sfere può avere una densità superiore.

Per quanto sia di facile comprensione, la congettura di Keplero si è dimostrata di assai difficile dimostrazione, resistendo ai tentativi di Gauss (1831) e di molti altri. Nel 1900 Hilbert la pose nella sua famosa lista dei 23 problemi non risolti della matematica. Nel 1953 l’ungherese Fejes Tóth dimostrò che il problema di determinare la massima densità di tutte le disposizioni di sfere, regolari ed irregolari, poteva essere ridotto a un numero finito, anche se molto grande, di calcoli, aprendo la strada a una dimostrazione per esaustione attraverso l’uso del computer. Tale dimostrazione è stata trovata da Thomas Hales nel 1998, applicando sistematicamente i metodi della programmazione lineare: essa consisteva di 250 pagine di annotazioni e 3 Gigabyte di programmi, dati e risultati. Molti matematici storcono tuttavia il naso quando sentono parlare di dimostrazioni ottenute grazie alle capacità di calcolo dei computer (lo abbiamo visto a proposito del problema dei quattro colori). I referee (presieduti dal figlio di Tóth) annunciarono nel 2003 che la commissione era “certa al 99%” che la dimostrazione fosse corretta, ma che non poteva garantire l’esattezza di tutti i calcoli fatti al computer. Hales si è allora impegnato a fornire una dimostrazione formale, che ancora deve arrivare.

mercoledì 31 ottobre 2012

Il 6174 e il 495 di Kaprekar

Dattaraya Ramchandra Kaprekar (1905–1986) era un insegnante indiano di matematica. Pur non avendo una specializzazione accademica, fece molte scoperte nella teoria dei numeri, tra i quali una costante e una classe di numeri che da lui hanno preso il nome, divulgati attraverso una serie di articoli su riviste di modesto prestigio scientifico. Si occupò anche di quadrati magici e matematica ricreativa. Studioso solitario e poco apprezzato dai colleghi indiani, diventò famoso quando Martin Gardner nel 1975 si occupò di lui in un articolo della rubrica Mathematical Games che teneva sullo Scientific American

Nel 1949 fu resa nota una tra le più famose scoperte di Kaprekar, che riguarda la curiosa proprietà del numero 6174, che ricorre come risultato finale di una serie di semplici operazioni con i numeri di quattro cifre, purché non siano tutte uguali. Ecco il procedimento, che ha lo stesso gusto perverso della congettura di Collatz

1. Prendiamo un qualsiasi numero di quattro cifre, usandone almeno due diverse. (Si possono inserire degli zero anche all'inizio.) 
2. Sistemiamo le cifre in ordine decrescente e poi in ordine crescente così da ottenere due numeri di quattro cifre, aggiungendo degli zero iniziali se necessario. 
3. Sottraiamo il numero più piccolo da quello più grande. 
4. Ripetiamo il processo partendo dal punto 2. 

Questo processo, conosciuto come operazione di Kaprekar, andrà sempre incontro al suo punto fisso, o kernel, il 6174. Una volta raggiunto il 6174, il processo continuerà a dare 7641 – 1467 = 6174. Per esempio, consideriamo il numero 2155: 

5521 – 1255 = 4266 
6642 – 2466 = 4176 
7641 – 1467 = 6174 
7641 – 1467 = 6174

Facciamo un altro esempio, questa volta con il numero 8082: 

8820 – 0288 = 8532 
8532 – 2358 = 6174 
7641 – 1467 = 6174 

Il numero fisso si raggiunge con 7 iterazioni al massimo, come nel caso del numero 2005: 

5200 – 0025 = 5175 
7551 – 1557 = 5994 
9954 – 4599 = 5355 
5553 – 3555 = 1998 
9981 – 1899 = 8082
8820 – 0288 = 8532 
8532 – 2358 = 6174 
7641 – 1467 = 6174 


Notiamo che, in ogni iterazione dell’operazione di Kaprekar, i due numeri di cui si fa la differenza hanno la stessa somma delle cifre, e quindi lo stesso resto (mod 9). Pertanto il risultato di ogni iterazione è un multiplo di 9. 

Il matematico giapponese Yutaka Nishiyama, con un programma specifico, ha verificato già nel 1975 le occorrenze del numero di iterazioni per tutti gli 8891 8991 numeri di quattro cifre da 1000 a 9999 nei quali non si hanno tutte le cifre uguali. Ne ha ricavato la seguente tabella: 


Si può dimostrare che 6174 è l’unico numero verso il quale convergono le successive iterazioni dell’operazione di Kaprekar. Consideriamo che per un numero di quattro cifre la combinazione ascendente può essere generalizzata come:

9 ≥ a b c d ≥ 0 

dove a, b, c, d non sono la stessa cifra. Così il massimo numero che si ottiene è abcd e il minimo è dcba. Quando eseguiamo la sottrazione, si ha che: 


che dà le relazioni: 

D = 10 + d a (poiché a > d
C = 10 + c – 1 – b = 9 + c b (poiché b > c – 1) 
B = b –1 – c (poiché b > c
A = a d 

Per i numeri in cui a>b>c>d.

Per trovare i numeri limite dell’operazione di Kaprekar, bisognerà considerare tutte le possibili combinazioni delle cifre di {a, b, c, d} e verificare che soddisfino le relazioni sopra scritte. Ciascuna delle 4! = 24 combinazioni dà luogo a un sistema di quattro equazioni con quattro incognite. Ne risulta un’unica combinazione che soddisfa 9 ≥ a b c d ≥ 0. Questa combinazione è bdac, con a = 7, b = 6, c = 4 e d = 1. Perciò ABCD = 6174. Non ne esistono altre: questo numero è unico. 

E se le cifre del numero non sono quattro? Lo stesso Kaprekar scoprì che un numero di due cifre non converge verso un solo valore, ma si impantana nel loop 9→81→63→27→45→9. Le cose cambiano con tre cifre: l’operazione questa volta converge verso un solo valore, il numero 495. Ad esempio, prendiamo 586. In ordine decrescente le cifre danno 865 e in ordine crescente danno 568. 

865 – 568 = 297. 
972 – 279 = 693. 
963 – 369 = 594 
945 – 459 = 495 
945 – 459 = 495. 

Con le cifre 4, 5 e 9 la cifra finale sarà sempre 495. 

Attraverso lo stesso procedimento usato per il caso delle quattro cifre e del numero 6174, si può dimostrare che 495 è l’unica soluzione possibile per un numero di tre cifre.

Per numeri con un numero di cifre superiore a 4 si è scoperto quanto riportato nella tabella, sempre fornita da Yutaka Nishiyama:


Notate la somiglianza tra i numeri che sono multipli di 2 e quella tra i numeri che sono multipli di 3: chissà che cosa c’è dietro. Dimostrazioni più avanzate e generali le trovate qui.

AGGIORNAMENTO DEL 2/11/2012

Gli amici di Webfract mi segnalano di aver reso disponibile online un calcolatore del procedimento di Kaprekar, che offre la possibilità di studiare il comportamento di interi positivi fino a un massimo di 16 cifre. Li ringrazio anche per avere segnalato il mio articolo.