venerdì 8 maggio 2015

I rompicapi di Alice: I problemi della teoria dei numeri

ispirato da @Popinga1 @DarioBressanini @maddmaths et al!
La teoria dei numeri è piuttosto problematica. Forse è il caso di chiedere un colloquio con i genitori.
Uno degli ultimi problemi matematici virali, il compleanno di Ceryl, è, in effetti, un problema di logica, ma, come spero i lettori sappiano, è solo uno dei molti che sono giunti all'attenzione del pubblico. La storia della matematica ricreativa è infatti piena di molti di questi problemi e in apertura vorrei segnalarvi quello dei tre marinai (che magari potrebbe diventare - o ritornare a essere - anch'esso virale!):
Il problema dei tre marinai
Tre marinai naufragano su un'isola deserta dove l'unica fonte di cibo sono gli alberi di cocco. I tre decidono, allora, di raccoglierne una gran quantità. Alla fine della giornata, però, sono troppo stanchi per dividerle in tre parti uguali, così rimandano il problema al giorno dopo e vanno a dormire. Durante la notte uno dei marinai si sveglia e, non fidandosi dei suoi compagni, decide di prendersi quanto gli spetta dal mucchio di noci di cocco senza attendere il mattino successivo. Si mette così a contare le noci di cocco raccolte e osserva che, tolta una noce dal mucchio, le restanti sono perfettamente divisibili per 3. A questo punto seppellisce la sua parte e lascia il resto del mucchio intatto, quindi ritorna a dormire. Più tardi il secondo marinaio si sveglia e, anche lui non fidandosi dei suoi compagni, decide di prendere in anticipo la sua parte. Avvicinatosi al mucchio, scopre che, tolta una noce di cocco, le restanti sono perfettamente divisibili per 3. A questo punto seppellisce il suo terzo di noci di cocco e torna a dormire. Ancora più tardi è il terzo marinaio a svegliarsi, sempre con la stessa idea di anticipare la divisione delle noci: anche quest'ultimo, avvicinatosi al mucchio, osserva che, tolta una noce, le restanti sono perfettamente divisibili per 3. Così anch'egli si prende il suo buon terzo, lo seppellisce e va a dormire.
A questo punto la domanda è: quale è il numero minimo di noci di cocco che i tre devono aver raccolto affinché la storia proceda come raccontato senza alcun intoppo?
La soluzione standard, come segnalata da Paul Herwitz su un vecchio articolo di Scientific American scaturisce dal seguente ragionamento: detto $x$ il numero di noci di cocco iniziale, il primo marinaio lascia nel mucchio $2/3 (x-1)$ noci, il secondo $2/3 (2/3 (x-1) - 1)$, il terzo $2/3 (2/3 (2/3 (x-1) - 1)-1) = y$. Svolgendo i calcoli si ottiene l'equazione risolutiva: \[8x - 27y = 38\] Questa equazione(1), come tutte le equazioni in due variabili, prevede una coppia di valori infinita, sia nei numeri reali, sia in quelli naturali. Per fortuna ci viene in aiuto la domanda stessa, che ci chiede il numero minimo di noci di cocco, e questo, dopo un paio di conti(2), risulta essere 25.
Come ricordato nell'articolo di Herwitz, il gioco lo si può estendere a 4 e poi a $n$ marinai: \[(n-1)^n x - n^n y =\] \[= (n-1)^n + n (n-1)^{n-1} + n^2 (n-1)^{n-2} \cdots + n^{n-1}(n-1)\] ovvero avremmo in generale un'equazione della forma $ax + by = c$ con $a$, $b$, $c$ interi. Se, come stabilito dal problema, vogliamo che anche i valori di $x$ e $y$ siano a loro volta interi, siamo di fronte a una così detta equazione diofantea, dal matematico greco Diofanto, il primo che trattò con tali equazioni (o per meglio dire con problemi risolvibili con equazioni di questo genere) nell'Arithmetica, testo del 250 a.c. circa.
La più famosa delle equazioni diofantee è, però, il teorema di Pitagora: \[x^2 + y^2 = z^2\] ovviamente quando $x$, $y$, $z$ sono interi, cosa che per i greci era altamente preferibile. Come avrete già intuito ciò ci porta dritti dritti a Pierre de Fermat, avvocato e matematico francese, che proprio sul bordo di una copia dell'Arithmetica di Diofanto scrisse il suo famoso teorema, l'ultimo teorema di Fermat:
L'equazione \[x^n + y^n = z^n\] non ha alcuna soluzione a parte quella banale nei numeri interi per $n$ maggiore di 2.
dove per soluzione banale si intende $x = y = z = 0$.
Il teorema venne dimostrato solo nel 1995 (anno di pubblicazione degli articoli) da Andrew Wiles, un successo che fruttò al matematico britannico una doccia di premi, primo fra tutti il Fermat Prize.
Formule prime
Un altro interessante problema relativo alla teoria dei numeri è la ricerca delle formule in grado di generare una lista completa di numeri primi. Fu proprio Fermat a proporre una di queste formule: \[2^{2^n} + 1\] Fermat, evidentemente, si fermò ai primi numeri interi per verificare la sua equazione e fu così compito di Leonard Euler mostrare come, per $n = 5$ il numero generato fosse composto: \[4292967297 = 641 \times 6700417\] Un altro paio di formule note sono, ad esempio, $n^2 - n + 41$, che funziona per $n < 41$, e $n^2 - 79 n + 1601$ che funziona per $n < 80$. Ad ogni modo, fino a ora, non è stata determinata nessuna formula in grado di generare una lista completa, e d'altra parte se fosse stato così, avremmo sicuramente la possibilità di dimostrare la verità o la falsità dell'ipotesi di Riemann.
Il problema della distribuzione dei numeri primi è stato, però, piuttosto ricco e fecondo. Un altro esempio di ricerca nel campo è il teorema di Peter Gustav Lejeune Dirichlet, matematico tedesco, che stabilisce che, dati due numeri primi tra loro $k$, $l$, esiste un numero infinito di numeri primi della forma $k + y l$, con $y$ intero positivo. La notazione utilizzata è quella presente nella dimostrazione del teorema di Dirichler del 1959 scoperta da Atle Selberg, matematico norvegese il cui principale interesse furono proprio i numeri primi e la funzione di Riemann.
E visto che siamo in tema, è scontato citare la congettura di Goldbach: in uno scambio epistolare con Euler, il professore di matematica tedesco Christian Goldbach suggerì che ogni intero positivo pari poteva essere scritto come la somma di due numeri primi. La richiesta era quella di dimostrare la congettura o di fornire un controesempio. Ancora oggi non siamo giunti a nessuna delle due.
Congruenze
Narra la storia (o forse la leggenda) che quand'era un bimbetto alle scuole elementari Carl Friederich Gauss riscoprì la formula dei numeri triangolari per calcolare la somma dei primi 100 numeri naturali. Questo notissimo episodio nella vita del grande matematico tedesco serve solo per ribadire non solo la sua importanza nella storia della matematica, ma soprattutto il suo peso nella teoria dei numeri. In particolare, seguendo il percorso storico di Herwitz, dalle Disquisitiones arithmeticae possiamo estrarre un concetto estremamente importante come quello della congruenza in matematica. Gauss, nel suo testo, così definì la congruenza:
Se la differenza di due interi, $a-b$, è divisibile per un terzo intero $c$, allora si dice che $a$ è congruente con $b$ rispetto al modulo $c$, o in termini matematici \[a \equiv b \mod c\]
Ad esempio 17 è congruente con 5 modulo 3, perché 17-5=12 e 12 è divisibile per 3. La relazione di congruenza tra due numeri può essere scritta non solo con la notazione data da Gauss, ma anche in termini più espliciti con la relazione $a = b + kc$, dove $k$ è un numero intero positivo. E' interessante osservare come, nel caso in cui $b < c$, allora $b$ è il resto della divisione intera ($\div$) di $a$ con $c$. Ad esempio $17 \equiv 2 \mod 3$: infatti $17 \div 3 = 5$ con resto 2. Utilizzando il resto è possibile poi introdurre delle particolari classi di equivalenza, dove per classe di equivalenza si intende un insieme di numeri che godono di una comune proprietà. In questo caso si possono raggruppare i numeri in base al resto per la divisione con un dato intero $c$. Nel caso di 3 avremmo tre distinte classi di equivalenza contraddistinte dai possibili resti 0, 1, 2 ottenibili dalla divisione per 3.
Le classi di equivalenza modulari e più in generale l'aritmetica modulare sono utilizzate ogni giorno. L'esempio più semplice è quello dell'orologio: ad esempio $15 \equiv 3 \mod 12$, e infatti possiamo alternativamente dire che sono le 3 del pomeriggio o le 15. D'altra parte possiamo determinare l'ora di un dato evento sapendo il suo inizio e quanto tempo è trascorso per la sua fine. Supponiamo di partire per un viaggio che durerà 33 ora alle 7 di mattina. Arriveremo quindi alle 4 di mattina. Infatti $40 \equiv 4 \mod 12$, e possiamo dire che sarà mattina perché $40 \div 12 =3$.
Da qui il passo alle gettonatissime regole di divisibilità è breve: un numero pari è divisibile per 2 (e questa è facile); se sommiamo le cifre di un dato numero e questo risultato è divisibile per 3, allora il dato numero è anch'esso divisibile per 3 (il discorso vale anche per 9); un numero la cui ultima cifra è 0 o 5 è divisibile per 5; un numero è divisibile per 4 o 25 se le sue ultime due cifre sono divisibili per 4 o per 25.
Strettamente connessa con la divisibilità è la così detta prova del 9. Supponiamo di avere due numeri interi $a$, $b$. Ne calcoliamo il prodotto e otteniamo un terzo numero intero $c$. Come facciamo a sapere se il risultato è corretto, senza utilizzare la calcolatrice? Semplice: prima di tutto determiniamo il resto della divisione di $a$ con 9, quindi il resto della divisione di $b$ con 9. A questo punto confrontiamo il prodotto dei due resti precedenti con il resto della divisione di $c$ con 9: se questi due numeri sono identici, allora la moltiplicazione è corretta, altrimenti no.
Il metodo è abbastanza semplice da applicare se abbiamo numeri fino a un paio di cifre (in fondo la tabellina del 9 è una delle più facili), diverso il discorso per numeri da tre cifre in su. Come determinare il resto? Sappiamo che se la somma delle cifre di un dato numero è divisibile per 9, quel numero è a sua volta divisibile per 9. Allora per determinare il resto della divisione per 9 di un numero $n$, basta determinare il resto della somma delle cifre di $n$ diviso per 9: facciamo un esempio. Supponiamo di avere il numero 6743. La somma delle sue cifre è 20. Il resto della divisione tra 20 e 9 è 2, che è anche il resto della divisione di 6743 con 2.
Il vino di frate Luca Pacioli
Bolzone. Doi ànno a partire una bote de vino che tene some 8 e si ne deve ciaschuno avere some 4 in sua parte, e non ànno altri mesure né instrumenti de poderlo partire se non do' altre botti voite, che l'una tiene some 5 e l’altra tiene some 3. Dimando commo lo partiranno giustamente.
Il passo qui sopra è tratto da un manoscritto di giochi matematici del frate Luca Pacioli che, a quanto scrive Dario Bressanini, era la prima stesura del più noto e importante dei trattati di Pacioli, il De viribus quantitatis. Il problema qui sopra è un classico gioco matematico che potremmo definire problema del travaso, di cui una delle prime versioni a noi note si trova nell'Annales Stadenses di Albert von Stade, come ci ricorda lo stesso Dario che, a tal proposito, ha anche scritto un libro con Silvia Toniato, I giochi matematici di fra' Luca Pacioli.
In termini differenti il problema di cui sopra possiamo renderlo anche in questo modo:
Un oste ha tre botti le cui capacità sono rispettivamente di 3, 5, e 8 litri. La più grande è piena di vino. Egli vuole dividere questa quantità in due parti uguali, ma non può utilizzare altro se non le tre botti a disposizione. Quale è il modo più semplice per portare a termine questo compito?
La soluzione più semplice prevede 7 travasi e può essere determinata anche per via grafica, utilizzando un semplice diagramma proposto da M.C.K. Tweedie sul Mathematical Gazette nel 1939.
(1) Tutti gli oggetti vecchi in questo armadio sono incrinati;
(2) Nessuna caraffa nell'armadio è nuova:
(3) Nulla in questo armadio, che è incrinato, potrà contenere acqua.

Lewis Carroll
Una variazione sui problemi del travaso sono, invece, quelli delle pesate. Prendiamo, per esempio, quello proposto da Harold Hopwood, ottantaduenne enigmista di Gravesend, ripescato dagli archivi del Daily Telegraph del 1937: egli, scrivendo al giornale, chiedeva la risoluzione di un enigma, che non era ancora riuscito a risolvere:
Supponiamo di avere 12 monete apparentemente tutte identiche. Sappiamo, però, che una di queste è falsa, ma non sappiamo se sia più pesante o più leggera. Per trovarla il numero minimo di pesate necessario è tre.
Una possibile soluzione, citata da Ian Stewart ne La piccola bottega delle curiosità matematiche del professor Stewart (l'intero micro-capitolo è disponibile in inglese: To find fake coin), è quella proposta da Thomas H. O'Beirne su New Scientist negli anni Novanta del XX secolo. Nel suo articolo, O'Beirne fa risalire questo rompicapo al 1945, per mano di Howard Grossman, anche se probabilmente le sue origini vanno ricercate nel XVII secolo.
Una soluzione molto bella è invece scritta in versi dal prode Blanche Descartes e pubblicata nel 1950 su Eureka:
F set the coins out in a row
And chalked on each a letter, so,
To form the words "F AM NOT LICKED"
(An idea in his brain had clicked).
And now his mother he'll enjoin:
MA DO LIKE
ME TO FIND
FAKE COIN
Ovviamente le monete vengono identificate dalle lettere maiuscole e sono divise in gruppi di quattro. Per determinare la moneta falsa, bisogna comunque utilizzare una tabella. Alcune di queste tabelle e una serie di altre con disposizioni differenti possono essere trovate su 12 coins problem, pagina di Franciscus Johannes Faase, che segnala anche la soluzione di Bennett Haselton al problema con 13 anziché 12 monete.
Quadrati magici
Uno dei più antichi giochi matematici legati alla teoria dei numeri è sicuramente il quadrato magico, ovvero un insieme di $n^2$ numeri interi sistemati in una matrice di $n$ righe ed $n$ colonne in maniera tale che la somma dei numeri in ogni riga, colonna e diagonale principale è identica ed è detta costante magica: \[\frac{n}{2} \left ( n^2 + 1 \right )\] dove $n$ è anche detto ordine del quadrato.
Come ricorda Popinga, il più antico quadrato magico di ordine 3 noto è cinese. Meglio noto come Lo Shu, a esso sono associate un gran numero di leggende, di cui la più nota risale al 2800 a.C. circa:
quando si sarebbe verificata una disastrosa piena del fiume Lo causata dall'ira del dio del fiume: in quell'occasione, narra la leggenda, la popolazione offrì sacrifici al dio per far cessare il disastroso evento. Dopo ogni sacrificio dal fiume emergeva una tartaruga, ma la furia del fiume non si placava. Solo dopo vari tentativi un bambino si accorse che la tartaruga inviata dal dio aveva segnata sul guscio una rappresentazione del quadrato magico. Questo significava che il dio chiedeva un sacrificio di 15 entità e l'accoglimento del messaggio portò alla fine della piena.
Anche Lewis Carroll inventò un quadrato magico, utilizzando i francobolli delle poste vittoriane \[\frac{1}{2} d, 1d, 1 \frac{1}{2} d, 2 d, 2 \frac{1}{2} d, 3 d, 3 \frac{1}{2} d, 4 d, 5 d\] I francobolli vanno posti su un quadrato $3 \times 3$ e in uno dei quadratini andranno due francobolli, per un totale di 10.
Finisce qui questo breve viaggio in alcuni dei problemi della teoria dei numeri. La guida per questo post è stata The theory of numbers di Paul S. Herwitz e così come l'articolo uscito su Scientific American non voleva essere esaustivo, nemmeno questo (più o meno lungo) post vuole minimamente esserlo. D'altra parte la teoria dei numeri è ricca di stimoli non solo per i ricercatori veri e propri, ma anche per la matematica ricreativa propriamente detta, diventando così una casa accogliente praticamente per chiunque voglia entrare!
(1) Dal modo con cui l'equazione viene determinata, dobbiamo supporre che la noce di cocco eccedente subisca uno dei seguenti destini: venire inclusa nel mucchio seppellito o gettata via. Se invece supponiamo che la noce di cocco venga rimessa all'interno del mucchio, l'equazione risolutiva alla fine risulta leggermente modificata: \[8x - 27y = 8\] Il ragionamento è semplice: il primo marinaio lascia un mucchio di noci di cocco pari a $x_1 = x - 1/3 (x-1)$; il secondo marinaio lascia un mucchio di $x_2 = x_1 - 1/3 (x_1-1)$; e infine il terzo lascia $x_3 = y = x_2 - 1/3 (x_2-1)$. Sostituendo a ritroso si ottiene l'equazione di prima, che porta a un numero minimo di 28.
(2) Senza scendere troppo nel dettaglio, $x$ deve essere un numero intero tale che \[x = \frac{27 \cdot k + 19}{4}\] con $k$ numero dispari. Già con $k = 3$ la nostra ricerca è finita!
Selberg, Atle (1949). An Elementary Proof of Dirichlet's Theorem About Primes in an Arithmetic Progression The Annals of Mathematics, 50 (2), 297-304 DOI: 10.2307/1969454
Tweedie M.C.K. (1939). A Graphical Method of Solving Tartaglian Measuring Puzzles, The Mathematical Gazette, 23 (255) 278. DOI: http://dx.doi.org/10.2307/3606420
Paul S. Herwitz (1951). The Theory of Numbers Scientific American, 185, 52-55 : 10.1038/scientificamerican0751-52

1 commento:

  1. segnalata da Martin Gardner c'è anche una soluzione all'enigma delle noci di cocco che prevede di utilizzare noci di cocco negative.

    Se il mucchio inziale è di 2 noci di cocco negative, il primo marinaio toglie una noce (positiva) al mucchio, che diventa a questo punto di -3 noci.
    Dopodiché prende la sua parte (1 noce negativa) e lascia le altre 2 noci negative nel mucchio per il marinaio successivo. E così via

    RispondiElimina