La matematica in gioco: Reticoli euleriani

In una serie dedicata a Eulero non poteva mancare un articolo dedicato ai reticoli (o cammini) euleriani. Prima di addentrarci nei labirintici percorsi euleriani, vi ricordo che è da pochi giorni on line il 15.mo Carnevale della Matematica: i nostri Rudi amici si occupano, tra le altre cose, del gioco del 15, un particolare quadrato magico ideato nel 1874 dal postino Noyes Palmer Chapman e diffuso nel 1880 da Samuel Loyd.
Torniamo, però, a noi.
Tutto inizia con il problema dei ponti di Königsberg: in questo famoso problema, il solutore deve cercare di trovare l'eventuale percorso che consenta di attraversare ogni ponte una e una sola volta e tornare, alla fine, al punto di partenza. Non solo Eulero determinò che non esisteva alcun percorso di questo genere, ma diede di fatto il via alla teoria dei grafi. In particolare si possono fornire una serie di definizioni che possono aiutare a determinare se un reticolo è euleriano o meno, ma che possono anche aiutare a seguire meglio il ragionamento per la risoluzione del 15.mo problema del Project Euler.

La matematica in gioco: Terne pitagoriche

E torniamo a giocare con la matematica (e con quale altra disciplina, o scienza, o follia della mente potreste mai pensare di divertirvi seriamente?). In questo caso ci occupiamo del famigerato teorema di Pitagora, quello dei triangoli rettangoli, dei quadrati costruiti sui suoi lati, due dei quali, quelli ad angolo retto, detti cateti, e l'ultimo detto ipotenusa. Certo Pitagora non pretende che vi mettiate a costruire dei quadrati sopra ai poveri cateti o magari sopra alla delicata ipotenusa, ma potreste farlo semplicemente con carta e penna e poi con il righello verificare che quel geniaccio aveva semplicemente ragione. O magari provare a ricavare un'espressione tipo questa: \[c_1^2 + c_2^2 = i^2\] Per questo e molti altri risultati possiamo dire che la scuola di Pitagora fu una delle più grandi scuole filosofico-matematiche dell'antichità. Molte delle osservazioni di Pitagora e dei suoi allievi, infatti, non solo vennero successivamente confermate (ad esempio la teoria eliocentrica, una delle festeggiate in questo splendente anno astronomico), ma anche col tempo riscoperte, come ad esempio proprio il teorema di Pitagora, dimostrato da Euclide nel primo volume degli Elementi.

La matematica in gioco: Sul Carnevale della Matematica e il Project Euler

E giunse, puntuale come ogni mese, il 14.mo Carnevale della Matematica. Ospitato da Matematica 2005, questa volta, mi sembra, un po' in tono minore: sarà la primavera che se ne va, sarà il caldo che avanza, sarà l'antigelo che non funziona poi molto bene vista l'assenza del gelo, questa volta le segnalazioni sono pochine. D'altra parte prima o poi il 14.mo carnevale doveva arrivare e un po' tutti sembra si sono fatti trovare impreparati alla doppia ricorrenza.
Se facciamo una piccola ricerca sul 14, però, scopriamo alcune cose interessanti: innazitutto è il numero atomico del silicio, che è di casa in questi nostri lidi elettronici; quindi è il terzo numero quadrato piramidale: 14 = 1 + 4 + 9; è anche il numero massimo totale di giocatori che possono giocare una partita ufficiale di calcio.
Concentriamoci, però, sul numero piramidale, perché ci consentirà di risolvere il Problema n.6 del Project Euler. Il problema n.6 recita, più o meno, così:

La somma dei quadrati dei primi dieci numeri è 385, mentre il quadrato della somma dei primi dieci numeri è 3025.
Trovare la differenza tra il quadrato della somma e la somma dei quadrati dei primi 100 numeri.

I numeri piramidali quadrati fanno proprio al caso nostro: tali numeri sono definiti come la somma dei quadrati dei primi $n$ numeri interi: \[Q_n = \sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}\] Allora, utilizzando la formula per i numeri triangolari, già utilizzata per il Problema n.1, combinata con quella per i numeri piramidali quadrati otteniamo la risposta al nostro problema: \[R_{100} = T_{100}^2 - Q_{100}\] che risulta una soluzione molto elegante per il Problema n.6, che i più arguti di voi ricorderanno che vi avevo già proposto.
Ritornando al Carnevale, vi ricordo che per leggere l'elenco dei passati Carnevali e prenotarsi, fate riferimento a Matematti.
Alla prossima!

La matematica in gioco: Numeri palindromi

Oggi si parla del quarto problema del Project Euler: trovare il palindromo più grande generato dal prodotto tra due numeri di tre cifre ciascuno. La risposta a tale quesito può essere trovata, come negli altri casi, sia attraverso un algoritmo specifico, sia utilizzando carta e penna. Al di là di come il problema viene risolto, ci sono alcune considerazioni preliminari che possono essere fatte, come ad esempio provare a capire come è fatto il numero palindromo cercato: \[A \cdot (10^5+1)+B \cdot (10^4+10^2)+C \cdot 1100 =\] \[= 11 \cdot (A \cdot 9091 + B \cdot 910 + C \cdot 100)\] Esso deve quindi essere divisibile per 11, ma non per il suo quadrato. Questo vuol dire che solo uno dei due moltiplicatori è divisibile per 11. A questo punto si può fare una considerazione estremamente semplice: andiamo a cercare i multipli di 11 compresi tra 900 e 1000:

902, 913, 924, 935, 946, 957, 968, 979, 990

Il massimo palindromo che cerchiamo inizia con la stessa cifra con cui finisce, quindi dovremmo cercare un numero che inizia e quindi finisce per 9. Questo esclude tutti i multipli di 11 che sono anche pari e tutti quelli che sono divisibili per 5. Dall'elenco di cui sopra restano allora: 913, 957, 979.
A questo punto, decidendo che stiamo cercando il moltiplicatore massimo, e che quindi la cifra delle centinaia è un 9 anche per il secondo moltiplicatore, facciamo alcune ulteriori considerazioni, ognuna per ogni numero considerato:

1. se il primo moltiplicatore è 913, il secondo deve necessariamente finire per 3 in modo tale da avere 9 come ultima cifra;
2. per lo stesso motivo di prima, nel caso di 957 l'ultima cifra deve essere 7;
3. e quindi per 979, l'ultima cifra del secondo moltiplicatore deve essere 1.

Per il primo numero possiamo impostare la seguente equazione: \[(900+10+3)(900+10x+3) = 824439 + 9130x\] dove $x$ è la cifra cercata.
Valutiamo $x$: (900000-824439)/9130=75561/9130=8,2761... e quindi la cifra cercata può essere solo 9. E, guarda un po', il prodotto \[913 \cdot 993 = 906609\] è palindromo.
Fatto lo stesso ragionamento anche per gli altri due numeri (957, 979) si trova che non ci sono altri numeri palindromi, e quindi 906609 è il palindromo cercato!
Dal lato programmazione ho condotto una piccola ricerca, trovando alcuni link interessanti. Ad esempio uno script per VB [link morto], o in alternativa potete consultarne uno pubblicato su Coder Profile. Su codesling, invece, ho trovato un paio di codici per i problemi 4 e 6 che possono facilmente essere adattati per qualunque linguaggio di programmazione.
Per C# eccovi un articolo su Functinal Fun sul problema #4 e infine una raccolta di codici su The Research Kitchen che possono essere utilizzati per risolvere alcuni dei problemi proposti dal Project Euler.

---

P.S.: la bellezza della matematica è che si possono trovare dimostrazioni identiche o quasi anche quando non ci si può confrontare prima: per gli iscritti al Project Euler suggerirei di controllare la dimostrazione proposta dall'utente Begoner.

La matematica in gioco: Scarto quadratico medio

Per l'occasione del nuovo post della serie La matematica in gioco, parliamo del problema n.6 del Project Euler, che ricorda molto da vicino il calcolo della deviazione standard in statistica: il problema, infatti, ci propone di calcolare la differenza tra il quadrato della somma dei primi 100 numeri naturali e la somma del quadrato di ciascuno dei primi 100 numeri.
In formule quello che ho scritto vuol dire: \[(100 + 99 + \cdots + 2 + 1)^2 - (100^2 + 99^2 + \cdots + 2^2 + 1^2)\] Al di là della risoluzione del problema (a causa dei grandi numeri utilizzati sembra che sia necessario l'utilizzo di un algoritmo), una delle cose più interessanti è il possibile utilizzo (ancora una volta!) dell'aritmogeometria pitagorica, che i lettori abituali del blog già conoscono.

La matematica in gioco: Il minimo comune multiplo

La bellezza della matematica è che, affrontando giochini di logica e sfide di vario genere, si riescono a riscoprire anche indipendentemente e con poche conoscenze, risultati antichi come il mondo, ma in fondo non troppo noti. E' il caso della nostra piccola disfida con Dario Casertano che ritrova semplicemente la risposta al problema che avevo proposto un po' di tempo fa. Un grazie a Dario e alla sua grande curiosità e allo spirito matematico che ha dimostrato!
Comunque, continuando a ispirarmi al Project Euler, eccovi un piccolo quesito abbastanza semplice e anch'esso risolubile solo con carta, penna e l'ausilio di una calcolatrice. Supponiamo di prendere i primi 20 numeri naturali: quale è il minimo comune multiplo di tutti e 20?
La domanda, semplice in se, ha una risposta banale ma che, nei fatti, potrebbe non essere così semplice. L'invito è come sempre quello di risolverlo, questa volta però prima di continuare a leggere il post.

La matematica in gioco: La somma dei numeri compresi tra due interi dati

Nella ricerca che avevo condotto per scrivere il primo post ispirato al Project Euler, oltre ad aver scoperto un altro paio di post che affrontavano il primo problema con algoritmi, ne avevo anche scoperto uno interessantissimo di Dario Casertano sulla somma di tutti i numeri interi compresi tra due estremi dati.
E' possibile ricavare la formula di Dario a partire dall'aritmogeometria pitagorica: basta semplicemente sommare tutti i numeri fino all'estremo maggiore, sottrargli gli interi fino all'estremo inferiore e avere cura di sommare l'estremo inferiore, altrimenti eliminato dalla somma. In formule matematiche, detti $n_2$ l'estremo superiore ed $n_1$ quello inferiore, si ottiene \[n_2 \frac{n_2 +1}{2} - n_1 \frac{n_1 +1}{2} + n_1 = \frac{(n_2-n_1+1)(n_2+n_1)}{2}\] che è la formula ottenuta da Casertano!
L'emozione è tanta e la potenza della matematica anche: ha consentito di ottenere lo stesso risultato utilizzando due ragionamenti differenti, entrambi altrettanto validi e corretti: in questo senso fa ridere la diatriba tra Casertano e un suo lettore su chi ha ottenuto la formula migliore, considerato che entrambe sono vecchie quanto la matematica, anche se giovani quanto chi le ha riscoperte.
Comunque Dario, nel suo post, ricava con una serie di brillanti ragionamenti logici e passaggi matematici, una formula che gli consente di determinare tale somma: emozionato per aver risolto il problema senza l'uso del computer, utilizza il suo esempio per sottolineare una differenza fondamentale tra il programmatore, che parte lancia in resta utilizzando il cannone, e uno sviluppatore. Personalmente avrei allargato il confronto tra un programmatore qualsiasi (preferibilmente aziendale!) e uno scienziato: quest'ultimo, abituato anche a cercare la soluzione più semplice, nel suo percorso di ricerca, laddove possibile, prova a scoprire strade semplici per risolvere problemi complessi, o quanto meno per semplificarli e ridurre all'essenziale ogni utilizzo di computer e algoritmi.
Diverso, invece, il caso di altri due post, comunque interessanti, ma concentrati solo sugli aspetti algoritmici del primo problema: Problemi, gare e algoritmi e di Progetto Eulero: Problema 1.

La matematica in gioco: La somma dei multipli di 3 e 5

Come promesso è giunto il momento di dare la soluzione del post precedente (anche se probabilmente in molti l'avranno trovata... spero!): la somma dei numeri naturali da 1 a $n$ è data semplicemente dalla formula $n(n+1)/2$, nota sin dai tempi di Pitagora e della sua aritmogeometria. A questo punto resta solo da adattare la formula al nostro problema: trovare la somma di tutti i multipli di 3 e 5 fino a 1000.
Innanzitutto dobbiamo trovare la somma di tutti i multipli di 3 fino a 1000: la prima cosa da notare è che l'ultimo multiplo di 3 sotto il 1000 è 999 = 3*333. Quindi sotto il 1000 esistono 333 numeri interi, incluso il 3, che possono essere scritti come un numero compreso tra 1 e 333 e moltiplicato per 3. Quindi basta sommare tutti i numeri naturali tra 1 e 333 e moltiplicare questo risultato per 3 per ottenere la prima somma. Allo stesso modo per i multipli di 5, basta notare che 1000 = 5*200 e quindi fare la stessa operazione, con l'avvertenza di fermarsi al 199.mo multiplo della serie di 5, poiché dobbiamo escludere l'estremo finale, 1000.
Il risultato sarà pertanto dato da \[3 \cdot 333 \cdot \frac{334}{2} + 5 \cdot 199 \cdot \frac{200}{2} = 166833 + 100500 = 267333\] C'è però una cosa di cui, in ultima analisi, bisogna tenere conto: i multipli comuni tra 3 e 5, ovvero i multipli di 15. E' facile scoprire, dividendo 1000 per 15, che tali multipli sono 66 e la loro somma è data dalla formula \[15 \cdot 66 \cdot \frac{67}{2} = 33165\] e quindi il risultato finale è 234168, e tutto questo utilizzando come massimo ausilio la calcolatrice.
Ovviamente tutto il processo può essere automatizzato attraverso un programma, ma questa è una sfida che al momento non raccolgo, ma che spero i lettori in... ascolto colgano al volo: l'invito è quindi quello di realizzare algoritmi in grado di automatizzare il processo, sfruttando tutti gli artifici matematici necessari per rendere l'algoritmo stesso più efficiente e chiaro alla lettura.
D'altra parte altri hanno già affrontato il problema, basti leggere Problemi, gare e algoritmi e Progetto Eulero: Problema 1.

---

In un prossimo post vorrei affrontare un problema un po' più complesso, ma più semplicemente risolubile alla luce di quanto abbiamo appreso finora.

La matematica in gioco: Somme continue

Leonhard Euler

Alcuni mesi fa mi sono imbattuto in un post interessante di nexusdue pubblicato su downloadblog: il nostro ci propone un interessante sito logico/matematico, Project Euler, in cui vengono proposti ben 230 problemi. Il sito lancia la sfida ai navigatori chiedendo loro di risolvere i quesiti proposti, sia utilizzando la logia e la matematica, sia utilizzando algoritmi vari.
Certamente la dimestichezza nella programmazione è un ottima base per risolvere i vari quesiti, ma come vedremo con il primo problema della lista, sarebbe un po' come sparare con un cannone contro un bersaglio piccolo pochi centimetri!

Se scriviamo tutti i multipli di 3 e 5 fino a 10, otteniamo 3, 5, 6, 9, la cui somma è 23. Trovare la somma dei multipli di 3 e 5 fino a 1000.