Skip to content

SQL è disuguaglianza triangolare

22 settembre 2015

In questo articolo intendo, con un esempio tratto dalla mia realtà lavorativa, mostrare un legame inaspettato tra un’applicazione informatica e una teoria matematica. Legami di questo tipo sono talvolta difficili da individuare, perché se da un lato la pratica è travolgente e “sporca”, dall’altro la teoria è complicata e distaccata. Ricondursi ad una teoria comporta solitamente l’astrazione di una situazione concreta, esercizio a volte difficoltoso ma potenzialmente utile perché può dare fondamento a quella che altrimenti è solo un’intuizione.

Parlo di SQL, che è un linguaggio informatico per interrogare (query) database. Per semplicità, consideriamo un database composto da una singola tabella, con un certo numero di righe (record) e un certo numero di colonne (campi). Con l’SQL è possibile effettuare operazioni su tutti i valori presenti in determinati campi, come ad esempio totalizzare il contenuto di un campo numerico o estrarre tutti i valori univoci di un campo alfanumerico.

Supponiamo di avere un database con due campi, uno che presenta n valori distinti e uno che contiene valori numerici sia positivi che negativi. Siano i record del database partizionati sulla base del primo campo, quindi il generico record x appartiene necessariamente ad uno degli insieme A_1, \ldots, A_n, la cui unione determina l’insieme complessivo A.

Un esempio è una tabella contenente tutti i movimenti di cassa di un conto corrente nel corso di un anno. In questo caso n=12, e A_3 rappresenta l’insieme delle righe riferite al mese di marzo. Chiamiamo f(x) il valore numerico del flusso di cassa situato nel record x. Il saldo finale a fine anno è

\sum_{x\in A} f(x),

che è uno dei classici risultati che si possono calcolare agevolmente in SQL.

Poniamo ora di essere interessati al totale delle entrate, vale a dire di ignorare le righe con f(x) negativo. Matematicamente stiamo usando la funzione ()_+, chiamata parte positiva. Si definisce (z)_+ = z se z \geq 0, ed è (z)_+ = 0 se z < 0. Siamo però di fronte ad un ostacolo, perché SQL non calcola la funzione ()_+ sui dati di una singola riga, così come non calcola la funzione \max tra due valori. Al più può trovare il \max tra tutti i valori di un campo, ma la funzione non può essere usata per determinare il massimo tra due numeri, anche perché in caso contrario avremmo potuto scrivere \max(x, 0) invece di ()_+.

E’ anche vero che in SQL si possono fare filtri per escludere i valori negativi, ma nel mio esempio questi valori dovevano essere invece posti a 0. Come fare senza la funzione che calcola la parte positiva? Si dà il caso che in SQL ci sia la funzione \mbox{abs} che calcola il valore assoluto dell’input. Per chi vuole distrarsi, propongo di interrompere la lettura e di provare invece a definire la funzione ()_+ avendo a disposizione solo \mbox{abs} e le quattro operazioni. La soluzione sarà data a tradimento più sotto.

La funzione ()_+ non è lineare, quindi l’applicarla in varie fasi di raggruppamento porta a risultati diversi. Ad esempio la si può applicare a monte, su ogni riga del database, per trasformare in 0 tutte le transazioni negative. La comparazione che mi sono ritrovato a fare prevedeva invece di applicarle in fasi successive di raggruppamento. In un primo caso consideravo solo i saldi mensili positivi, sommandoli poi insieme:

\sum_{i = 1}^n \left( \sum_{x \in A_i} f(x) \right)_+;

un secondo caso considerava il saldo totale solo se positivo:

\left( \sum_{x \in A} f(x)\right)_+ = \left( \sum_{i = 1}^n \sum_{x \in A_i} f(x) \right)_+.

Dalle mie estrazioni sembrava che il primo risultato fosse sempre maggiore o uguale al secondo. E’ sempre vero? Perché? lo si può dimostrare?

Così come descritto, il problema potrebbe sembrare fin troppo semplice, ma è appena il caso di dire che capire cosa stesse succedendo nella situazione reale non era altrettanto palese: molti campi e molte tabelle aggiunte in tempi diversi, una partizione meno visibile rispetto ai mesi di calendario e un significato più articolato di semplici transazioni monetarie contribuivano a confondere le acque. Quindi già la formulazione in termini matematici è stata di grande aiuto.

Per proseguire nell’astrazione, chiamo y_i = \sum_{x\in A_i} f(x), quindi quello che succedeva empiricamente era che

(y_1 + \ldots + y_n)_+ \leq (y_1)_+ + \ldots + (y_n)_+.

Per tornare al problema della mancanza della funzione ()_+ in SQL, una soluzione è scrivere

(x)_+ = \frac{x + |x|}{2}.

Chi si fosse perso l’occasione di trovare autonomamente questa formuletta rimedi ora verificando che sia corretta. Usando questa formula, dobbiamo allora dimostrare che

\frac{y_1 + \ldots + y_n + |y_1 + \ldots + y_n|}{2} \leq \frac{y_1 + \ldots + y_n}{2} + \frac{|y_1| + \ldots + |y_n|}{2},

che equivale a

|y_1 + \ldots + y_n| \leq |y_1| + \ldots + |y_n|,

che è sempre vera!

Quest’ultima equazione è infatti una generalizzazione della disuguaglianza triangolare. Se immaginiamo di avere un poligono di n+1 lati, e di individuare un lato principale, il suo vettore è determinato dalla somma dei vettori di tutti gli altri lati, quindi la sua lunghezza è |y_1 + \ldots + y_n|. Tutti gli altri lati, insieme, determinano una spezzata che connette i due vertici toccati dal lato principale, e che ha lunghezza |y_1| + \ldots + |y_n|. Per definizione il primo segmento, essendo rettilineo, deve connettere i due vertici percorrendo la strada più breve, il che giustifica l’equazione.

Nel nostro caso abbiamo scalari invece di vettori, ma il ragionamento sta in piedi comunque immaginando che siano proiezioni di vettori sulla retta reale. Una dimostrazione rigorosa può ad esempio partire dalla disuguaglianza triangolare base,

|y_1 + y_2| \leq |y_1| + |y_2|,

ed estendere poi il numero di dimensioni tramite ricorrenza. Poiché questa disuguaglianza è vera, diciamo che la funzione valore assoluto è sub-additiva.

In conclusione, il processo di astrazione mi è stato utile sia per apprendere maggiori informazioni sul lavoro che stavo facendo grazie alla sua matematizzazione, sia per validare teoricamente l’intuizione costruita per via empirica che il totale diminuiva con l’aumentare del grado di raggruppamento. Come effetto collaterale, che personalmente non riesco a considerare meno importante, la possibilità di essere coinvolto in un’attività delle più umane: usare il cervello.

Un quesito di maturità scientifica

15 settembre 2015

Per avere un blog di successo ci sono poche e semplici regole, che Conlemele rispetta con precisione scientifica per garantirsi una popolarità da prima serata televisiva: linguaggio chiaro e accessibile, immagini accattivanti, pubblicazioni regolari, temi di attualità concreti che interessano alla gente, commenti e link ad altri blog e una pioggia di gettoni d’oro zecchino come gran premio finale.

E’ per questo che parliamo, a metà settembre, della prova di matematica della maturità scientifica. Yeah. Personalmente non mi è dispiaciuta, ma è anche vero che io non ho dovuto sostenere l’esame. Sono solo un onesto cittadino che paga le tasse e che si scarica i testi della matura e prova a vedere se è capace di risolvere i quesiti.

Tra le dieci domande ne segnalo per gradevolezza due, e ne risolvo una terza. Un primo quesito molto carino chiede di dimostrare la formula per il volume del tronco di cono. Credo che la strada ufficiale sia di interpretarlo come solido di rotazione e calcolare l’integrale, ma non è male dare per nota la formula del volume del cono e vedere il tronco come differenza di due coni con parametri opportuni. E i conti tornano con facili e appaganti calcoli.

Altra segnalazione è per il quesito che dichiara che un triangolo ha lati lunghi 6, 6 e 5, e chiede la probabilità che un punto casuale uniformemente scelto all’interno del triangolo disti più di 2 da uno dei tre vertici. Il triangolo risulta diviso in 4 aree, tre di queste sono “fette di torta” centrate nei vertici del triangolo e di raggio 2. Pensare di calcolare queste tre aree potrebbe impedire completamente la risoluzione del problema, fino a che non si arriva all’illuminazione: non ci servono le tre aree separatamente, ma l’area della torta completa, che guarda caso si trova molto facilmente. (“Torta”, “pie”, \pi, area del cerchio, … adesso tutto torna).

In questo post risolvo invece questo quesito: trova il minimo di

f(x) = (x-1)^2 + (x-2)^2 + \ldots + (x-5)^2.

Non so precisamente di quali strumenti dispone lo studente, una volta finita la quinta, ma per fortuna non riceverò nessun voto.

Approccio algebrico

La funzione ha una discreta simmetria, caratteristica da sfruttare al volo. Per rendere questa simmetria esplicita, definiamo una nuova variabile y=x-3, in modo da scrivere il polinomio equivalente

g(y) = (y-2)^2 + (y-1)^2 + y^2 + (y+1)^2 + (y+2)^2.

La trasformazione è una traslazione orizzontale che non cambia il valore del minimo.

Sviluppando i quadrati si elidono tutti i doppi prodotti, e quindi

g(y) = 5y^2 + 2(2^2+1) = 5y^2 + 10.

La funzione è sempre positiva, quindi il minimo si ha per y=0=x-3, cioè per \hat{x}=3, dove il cappello sopra la x indica che per quel valore la funzione è minima. E vale f(\hat{x}) = 10.

Ottimizzazione

Forse la strada che un bravo studente avrebbe dovuto seguire è quella dell’ottimizzazione, ponendo a zero la derivata prima:

f' = \sum 2(x-i) = 2\cdot 5\cdot x - 2 \sum i = 10x - 30 = 0.

I calcoli sono semplicissimi, e il risultato è lo stesso di prima.

Perturbazione

Confesso di essermi scervellato per trovare il minimo in modo alternativo. Dopo un po’ di tentativi andati a buca, ecco che ho completato il metodo che segue, che ad un’analisi più attenta risulta non essere altro che l’azzeramento della derivata prima ma con un approccio meno generale e un po’ rétro.

Consideriamo la generalizzazione della funzione:

f(x) = \sum_{i=1}^n (x-i)^2,

che ha minimo \hat{y} = f(\hat{x}) che ci riproponiamo di trovare.

Con semplici passaggi posso calcolare la funzione in corrispondenza della somma o della differenza di due valori:

f(a \pm b) = \sum (a \pm b - i)^2 = \sum(a-i)^2 + \sum b^2 \pm 2b\sum(a-i).

E qua il punto fondamentale è che la nostra funzione si comporta molto bene, perché nel primo addendo a destra ritroviamo f(a). Gli altri due addendi sono rispettivamente nb^2 e 2b\left(na - n\frac{n+1}{2}\right), quindi per riassumere

f(a\pm b) = f(a) + nb \left(b \pm \left( 2a - (n+1)\right)\right).

Armati di questo calcolo, possiamo pensare di calcolare la funzione un po’ a destra e un po’ a sinistra di \hat{x}, scrivendo

f(\hat{x} \pm \epsilon) = f(\hat{x}) + n \epsilon(\epsilon \pm (2\hat{x} - (n+1))) \geq f(\hat{x}),

dove per definizione di minimo, allo spostarci di un qualsiasi \epsilon \geq 0 da \hat{x} otteniamo un valore non inferiore a f(\hat{x}). Da questa disuguaglianza, e siccome anche n\epsilon è non negativo, deduciamo che la parte tra le parentesi più esterne deve essere non negativa:

\epsilon \pm (2\hat{x} - (n+1)) \geq 0,

il che, separando i due casi contenuti in \pm, ci porta a dire

\frac{n+1}{2} - \frac{\epsilon}{2} \leq \hat{x} \leq \frac{\epsilon}{2} + \frac{n+1}{2}.

Questo vale per ogni \epsilon quindi abbiamo rinchiuso \hat{x} in un intervallo piccolo a piacere. Per \epsilon = 0 troviamo

\hat{x} = \frac{n+1}{2},

che concorda con i calcoli precedenti per n=5 e che, a giudicare dalla simmetria della funzione, si poteva giudicare ovvio. In matematica, con gli “ovvio” ci riempono le fosse.

Intersezioni di cerchi, e poi di ipersfere

8 settembre 2015

Questo è il seguito di qualcosa iniziato molti mesi fa. A gennaio di quest’anno ho ricevuto da un lettore di questo blog, come dono inatteso, un problemino simpatico che ho pensato bene di generalizzare. Dopo un periodo passato a menare il can per l’aia, a guardare l’erba crescere e l’acqua evaporare, ecco che mi decido a riprenderlo in mano. Se continuo a non oliarli, certi ingranaggi continueranno a girare molto lentamente.

Per cominciare, ecco come si presentava il problema originario. Ho un quadrato di lato unitario. Ho un cerchio di raggio unitario centrato in un vertice, e un cerchio di raggio un mezzo centrato in uno dei segmenti non contenti il vertice. Si tratta di trovare le coordinate del punto di intersezione dei due cerchi.

Non ci sono trucchetti: il punto di intersezione richiesto è quello interno al quadrato, non quello coincidente con un suo vertice.

Il problema è piacevole da risolvere, sia perché si fanno i calcoli e si trova la soluzione, sia perché questa soluzione, cioè le coordinate del punto, è espressa da numeri “piacevoli”. Non che i numeri irrazionali siano “spiacevoli” o cose del genere, ma insomma uno può anche avere delle preferenze. E comunque no, la soluzione non la scrivo in chiaro, anche perché chi vuole può risolvere questo ed evitare l’orrore multidimensionale che segue.

La costruzione geometrica può essere interpretata in un altro modo, e qui serve un po’ di attenzione e di immaginazione. Siamo all’origine del sistema di riferimento. Ci spostiamo lungo l’asse delle x e disegniamo una circonferenza di raggio 1. Poi ci spostiamo lungo l’asse delle y e disegniamo una circonferenza di raggio \frac{1}{2}.

Con questa idea siamo pronti a generalizzare ad uno spazio euclideo ad n dimensioni. Partendo dall’origine, ci muoviamo lungo il primo asse e disegniamo una sfera di raggio 1 che dista 1 dall’origine. Muovendoci lungo il secondo asse di \frac{1}{2} dall’origine disegniamo una sfera di raggio \frac{1}{2}. Sul terzo asse, raggio e distanza sono \frac{1}{4} e così via. Ogni raggio è la metà del precedente ed è pari alla distanza del centro, di modo che tutte le sfere passano per l’origine. In simboli, l’i-esima ipersfera ha raggio 2^{i-1}.

In n dimensioni, le ipersfere si incontrano tutte in un altro punto con n coordinate positive. La somma di queste coordinate diminuisce con il crescere del numero delle dimensioni. Se questa somma scende al di sotto di uno su 171, quanto vale n?

Intersezioni di cerchi, e poi di ipersfere


Ci sono n ipersfere in \mathbb{R}^n, l’i-esima ha raggio r_i=2^{i-1} e centro sull’i-esimo asse, ad una distanza di +r_i dall’origine. La somma delle coordinate del punto di intersezione delle ipersfere nell’ortante positivo è inferiore a \frac{1}{171}. Quanto vale al minimo n?

Un gioco da poppanti

1 settembre 2015

La piccola Chiara ha 8 mesi (11, ma tanto è solo presente storico), e uno dei suoi giocattoli preferiti sono le scodelline colorate. Nella scatola c’erano 10 scodelline e una pallina, e sul contenitore era stampata la foto di un bambino seduto che impila ordinatamente gli oggetti dal più grande al più piccolo, per poi appoggiarci in cima la pallina come la ciliegina su una torta a 10 piani.

La realtà del Laboratorio Errante, dove Chiara passa le sue giornate, è ben diversa. Le ciotole sono sparse in ogni dove sul pavimento, tranne le poche sfortunate che sono cadute tra le grinfie del poppante in fase di dentizione, che le rosicchia sbavando.

La fattura degli oggetti non è improvvisata, tanto è vero che è facile incastrare la ciotola n sopra quella n+1. Immaginiamo di assegnare ad ogni coppetta una quantità. Se le coppette sono separate, si può anche immaginare che queste quantità siano crescenti, e ad esempio potremmo scrivere
a_1 < a_2 < \ldots < a_{10}.

Possiamo decidere che incastrare due ciotole significa prevedere l’eventualità che le relative quantità siano uguali, e quindi trasformare un segno < in un \leq.

Abbiamo dunque due problemi isomorfi: in quanti modi possiamo incastrare alcune ciotole di dimensioni consecutive? O in alternativa: in quanti modi possiamo mettere tra i numeri a_1, \ldots, a_{10} simboli di < oppure \leq?

La ciotola 1 può essere incastrata sulla ciotola 2 oppure no. Sono due casi completamente indipendenti da quello che succede tra le altre ciotole. La quantità a_2 può essere < oppure \leq di a_3, e anche qua ho due casi indipendenti.

Il numero totale dei modi è il prodotto di tutte queste possibilità, cioè 2\cdot 2\cdot \ldots \cdot 2 = 2^9. Fin troppo facile.

Non vorrei lodare troppo questa colata di plastica, ma devo dire che piacciono molto anche a me, e non intendo da leccare. Le ciotole hanno la forma di mezza sfera, e non solo possono essere incastrate l’una dentro l’altra come suggerito prima, ma si può anche farne combaciare due consecutive per formare una specie di sfera dall’aspetto un po’ asimmetrico.

Si possono formare al massimo 5 sfere con le 10 ciotole. La numero 2 può essere usata per far coppia sia con la numero 1 che con la numero 3, ma non si possono fare entrambe gli incastri contemporaneamente. O meglio, in realtà si potrebbero anche formare due sfere una dentro l’altra e con una metà in comune, ma per questo problema lasciamo stare.

E non dimentichiamoci che con le dieci coppette è inclusa anche una pallina gialla, che è abbastanza piccola per entrare dentro qualsiasi coppia di coppette chiuse a sfera. Consideriamo allora tutte le combinazioni delle coppette che formano almeno una sfera che contenga la pallina gialla. Se le sfere sono più d’una contiamo come diverse le configurazioni a seconda di dove mettiamo la pallina.

Fatto? Quante sono in tutto le configurazioni possibili?

Un gioco da poppanti


Dai numeri da 1 a 10 inclusi sono scelte alcune coppie di numeri consecutivi. Le coppie sono almeno una ed esattamente una coppia è evidenziata. In quanti modi si può compiere l’operazione?

Una diagonale a posto e una sfasata

12 maggio 2015

C’era una volta un rettangolo diviso in due da una diagonale.

Due segmenti un po’ pigri proiettavano i vertici liberi sulla diagonale, ripartendo così il rettangolo in quattro triangoli.

A guardar bene, i triangoli erano di due tipi. C’erano i triangoli grandi, che si tenevano per mano, e i due triangoli piccoli, che si guardavano da lontano.

Quando un alligatore lasciava cadere una lacrima sul rettangolo, se questa centrava uno dei triangoli piccoli, un allibratore dava cinque sterline per ogni sterlina puntata. Poi, a sua volta, piangeva.

Una lacrimuccia è caduta sulla diagonale, e lì è cresciuto un fiorellino giallo. Con una certa probabilità (quale?) questo fiorellino è spuntato sul confine tra i due triangoli grandi, per poi vivere probabilmente felice e contento.

Una diagonale a posto e una sfasata


Un rettangolo è diviso da una diagonale e dalle proiezioni dei vertici sulla diagonale in 4 triangoli. Le aree dei triangoli piccoli sono insieme \frac{1}{5} di quella del rettangolo. Qual è la probabilità che, preso a caso un punto sulla diagonale, questo appartenga al perimetro di entrambi i triangoli grandi?

Il piccolo di Fermat, googol divisibili per 7 e 360 palline colorate

15 febbraio 2015

Non sempre per lavoro finisco a Madrid. Questa è la volta di Macerata, e poi di una sosta forzata di un’ora causa neve, e poi Arezzo, e poi si torna a Torino in un lungo viaggio in auto. Un po’ guardo dal finestrino e dialogo col compagno di viaggio, ma il tragitto è comunque lungo e finisco per osservare pigramente e lo scorrere dei pensieri.

Piccolo teorema di Fermat

Ho da poco letto una deliziosa dimostrazione combinatoria del Piccolo teorema di Fermat. O meglio, riletto. Perché faccio fatica a digerire i concetti di teoria elementare dei numeri, che trovo affascinanti ma difficili da visualizzare.

Il Piccolo teorema dice che, se prendo un intero n e un numero primo p, allora n^p - n è un multiplo di p. Questo fatto non è evidente, anche perché altrimenti non sarebbe così curioso. Certo, se prendo come intero n un multiplo di p allora il risultato diventa una banalità, ma siccome è vero per qualsiasi valore di n la cosa si fa molto interessante.

Golomb, quello che ha anche inventato i pentamini, propone una dimostrazione combinatoria del teorema. Supponiamo di avere una classe di p bambini. Ogni bambino ha un portapenne contenente pennarelli di n colori diversi, sempre gli stessi per ogni bambino. E’ evidentemente il primo giorno di scuola, e non ci sono pennarelli dispersi.

La maestra chiama tutti i bambini attorno alla cattedra, domandando loro di prendere un pennarello ciascuno e di mettersi in circolo in un certo ordine fisso e stabilito a priori. Il primo bambino può scegliere tra n colori, il secondo pure, il terzo idem. In totale i bambini possono presentarsi alla maestra in n^p modi diversi. In alcuni casi particolarmente sfortunati, tutti i bambini hanno lo stesso colore. Questi casi, che sono esattamente n, vengono ignorati, e tutti i bambini tornano al posto e ripetono la scelta.

L’impostazione così descritta porta ad un numero totale di n^p - n diversi coloramenti del circolo di bambini. Adesso viene il punto focale dell’argomentazione. Ogni bimbo passa il proprio colore al compagno alla sua sinistra, con l’effetto di ruotare il coloramento di un posto. Il nuovo coloramento è necessariamente diverso dal precedente, per il semplice fatto che almeno un bambino riceverà un colore diverso da quello che ha passato. Abbiamo infatti esplicitamente escluso le situazioni aventi un solo colore.

Ma la cosa più sottile è che ad ogni passaggio di colori otteniamo sempre un coloramento diverso, fino a che non saremo ritornati al punto di partenza. Perché non prima? Se l’esatto ordine iniziale dovesse ripetersi prima di un giro completo, vorrebbe dire che la sequenza di colori sarebbe composta di due parti indistinguibili, dando così luogo ad un coloramento di periodo due. In alternativa, la sequenza dei colori potrebbe essere composta da tre o più parti indistinguibili, ritornando così identica a sé stessa dopo un terzo di giro o ancora più frequentemente. Ciò però è in contrasto con l’ipotesi iniziale, cioè che il numero dei bambini è primo, e quindi non divisibile!

Ne concludiamo che ognuno degli n^p - n coloramenti può, per rotazione, essere trasformato in altri p-1. Tutti i coloramenti sono così ripartibili in gruppi di p elementi che sono identici a meno di una rotazione. Che è un altro modo di dire p è un multiplo di n^p - n.

Un esempio concreto

Abbiamo ancora molte ore per arrivare a casa, e il teorema è dimostrato. Dimostrazione molto bella, peraltro, ma sembra di guardare un oggetto in una vetrina fino a che non lo si prende in mano. Cosa può voler dire in un caso concreto? Devo fare i calcoli a mente, quindi per limiti personali mi accontento di un caso piccolo ma non troppo. Dato che posso raccogliere n per avere n(n^{p-1}-1), mi stuzzica l’idea di avere n=p-1. Ad esempio prendo p=7 bambini, o nanetti, e quindi n=6 colori.

Il teorema mi dice che 6(6^6-1) è divisibile per 7. Davvero? Non direi proprio che sia intuibile. Certamente 7 non divide 6, quindi il teorema mi assicura che 6^6-1 è divisibile per 7. Siamo già arrivati? No, e allora continuo oziosamente i calcoli. Il primo passo, tralasciando un secondo il -1, è di scrivere 6^6=36^3.

Il senno di poi è solitamente sottovalutato, pensando che sia troppo comune e di poco valore. In realtà è esperienza preziosa che ci può aiutare per il futuro, è pur sempre senno. Per vedere che 36^3-1 è divisibile per 7 si potrebbe togliere da 36^3 tutti i multipli di 7 possibili, riducendo così il problema ad uno più facile. Nello specifico, 36^3 = (35 + 1)^3 \equiv_7 1^3 \equiv_7 1, cioè dividendo il cubo per 7 il resto è di 1, e allora 36^3-1 è multiplo esatto. Il passaggio (35 + 1)^3 \equiv_7 1^3 scende comodamente espandendo il cubo e osservando che tutti i termini, tranne 1^3, sono multipli di 7 perché contengono almeno il fattore 35 che lo è.

Ma il senno di poi per definizione non è disponibile prima, quindi continuo ostinatamente con i calcoli. Posso fare 36^3 a mente? Ecco, 36^2 è più facile, lo si fa velocemente per confermare il risultato già memorizzato, che è 1296. E adesso ci sarebbe da fare 1296\cdot 36. Uhm.

A pensarci, moltiplicare per 3 sembra facile e moltiplicare per 6 è facile come raddoppiare un numero, quasi quasi ci provo. Allora, 1296\cdot 3 = 3888. Carino, e siccome sto facendo tutto a mente è anche comodo da conservare un attimo in memoria. Il suo doppio è 7776, quindi voglio vedere se 38880 + 7776 - 1 è un multiplo di 7. Solo che sto raggiungendo il limite della memoria mentale e mi sa che fare la somma è troppo difficile. Semplifico perché facilmente 7775 diviso 7 dà resto 5, e mi rimane 38885.

Ecco che arriva la sorpresa, dividere a mente 38885 per 7. Riproduco lentamente i passaggi per condividerne la semplicità: il 7 nel 38 ci sta cinque volte con il resto di 3. Riporto il 3 e abbasso il secondo 8. E siamo punto a capo! Il 7 nel 38\ldots come prima! Riporto il 3 e abbasso il terzo 8. Riporto ancora il 3 e abbasso il 5, e finalmente il 7 nel 35 ci sta un numero intero di volte e la verifica è conclusa.

Prima di farci distrarre completamente dalla divisione particolarmente agevole, volevo completare il discorso sul Piccolo guardando che 3^4-3=81-3=78 non è un multiplo di 4. Una delle ipotesi è che la potenza sia un numero primo, e l’aver preso il 4 impedisce di applicare il teorema. Se cadono le premesse, non necessariamente troviamo un multiplo intero della potenza, proprio come è appena successo.

Dividendo e riportando

Carinamente abbiamo visto che 38885 è un multiplo di 7. Eseguendo il comune algoritmo di divisione, capiamo subito che il numero di 8 inseriti tra il 3 e il 5 è ininfluente: sono multipli di 7 il 385, il 3885, e anche il

3 8888 8888 8888 8888 8888 8888 8888 8888 8888 8888 8888 8888 88\_

88 8888 8888 8888 8888 8888 8888 8888 8888 8888 8888 8888 8888 5,

che è quasi 39 googol.

E certamente non è l’unico caso. Ad esempio sono divisibili per 8 i numeri 24, 264, 2664, 26664, ecc, e sono divisibili per 6 i numeri 12, 132, 1332, 13332, ecc.

Stiamo dividendo un numero per un altro creando una sequenza di riporti costante, rendendo particolarmente semplice la divisione. Vi invito a cercare altri casi.

In generale, al posto di riportare sempre uno stesso numero, si possono costruire divisioni in cui riportiamo una qualsiasi sequenza di cifre. Ad esempio, dividendo per 9 il numero 10111111111 ottengo in sequenza come riporti tutti i numeri da 1 a 8. Al penultimo passaggio mi avanzano 8, abbasso l’1 e 81 è multiplo di 9, terminando l’operazione.

Altro esempio, dividendo per 9 il numero 17888888888 ottengo in sequenza i riporti dall’8 all’1.

Prendo un numerone e lo divido per 9, in modo che la sequenza dei resti contenga in un qualche ordine tutte le cifre da 1 a 8, ma in modo che due cifre consecutive non appaiano immediatamente l’una dopo l’altra. Tra le varie possibilità, prendo il più piccolo numero di questo tipo. Il risultato della divisione è un altro numero che contiene tutte le cifre positive tranne una. Quale?

Il piccolo di Fermat, googol divisibili per 7 e 360 palline colorate


Quale cifra positiva non compare nell’intero \frac{n}{9} se n è il più piccolo possibile e nell’algoritmo di divisione lunga a mano la sequenza di resti contiene le cifre da 1 a 8 in modo che due cifre consecutive non siano generate in passi consecutivi dell’algoritmo?

Alcuni problemi risolti e commentati della Festa della Matematica 2014

2 febbraio 2015

Nel marzo 2014 si è tenuta a Torino, al Lingotto, la Festa della Matematica. Ho partecipato alla gara a squadre aperta al pubblico, che prevede la soluzione di 20 problemi ora disponibili in rete. In questo documento riporto mie soluzioni per alcuni di questi problemi e aggiungo commenti personali di vario tipo, ad esempio su come poter approcciare le domande, in che tipologie ricadono, quali possibili strade di risoluzione alternative o generalizzazioni, ecc. Non garantisco l’assenza di errori neanche nei risultati numerici (non trovo su internet le soluzioni ufficiali). Qualsiasi suggerimento o segnalazione di errore è ben accetto.

In concreto ci sono le soluzioni dei problemi dal 10 al 19, tralasciando l’ultimo la cui soluzione  richiede troppa euristica e non porterebbe valore aggiunto dettagliarne qui i passi. I testi dei problemi sono stati da me riformulati, sia per matematizzarli parzialmente sia perché non sono fan dei copia-incolla. In caso di dubbio, rimando ai testi originali.

Leggi il documento.