Rudi Mathematici

Rivista fondata nell’altro millennio

Numero 183 – Aprile 2014 – Anno Sedicesimo

Uno scarsamente noto corollario della Legge di Murpy dice che ogni volta che dovete mettere qualcosa in una scatola, questa o è troppo grossa o è troppo piccola. Patrick Sung sostiene di aver risolto il problema con il sistema di piegatura di un foglio di cartone denominato Universal Packaging System. Ora, se andate a cercare come vengono stabilite negli USA le tariffe per l’invio dei pacchi, possiamo far partire un’epidemia di mal di testa in tutti gli uffici postali.

1.    Peste e corna

“When fair April with his showers sweet,

Has pierced the drought of March to the root’s feet

And bathed each vein in liquid of such power,

Its strength creates the newly springing flower”

(Geoffrey Chaucer,

“The Canterbury Tales”

The Preamble)

“Un buon indovinello dovrebbe richiedere la messa in atto del nostro migliore ingegno e sagacia; e sebbene la conoscenza della matematica e della logica siano spesso di grande aiuto nella soluzione di queste cose, accade invero di frequente che una sorta di naturale astuzia e predisposizione siano di valore considerevole.”

Di lui si sa che si chiamava Tisè, che era cinese, e che nel 1895 aveva appena diciott’anni. Si sa anche che abitava a Canton, e che era uno dei pochi cinesi convertiti al cristianesimo: fatto questo che aveva la sua importanza, nell’economia della sua avventura. La Cina della fine dell’Ottocento era un fermento di resistenza contro gli occidentali, che erano visti, e probabilmente neanche a torto, come diavoli stranieri che avevano l’intenzione di colonizzare o quantomeno sfruttare il paese[1].

In quel periodo, comunque, i cantonesi avevano anche ben altre emergenze da fronteggiare: un’epidemia di peste stava flagellando la regione, e a Canton i morti erano già più di centocinquantamila. La peste era una tragedia antica, che aveva tormentato Asia e Europa per secoli, ad ondate cicliche e terribili; ma finalmente la scienza stava cominciando a farsi seriamente un’idea di quali fossero le cause e la dinamica della malattia. Uno studioso giapponese, Shibasaburō Kitasato, aveva eseguito diverse autopsie sui cadaveri degli appestati e, seppur in maniera non completa né ordinata, aveva chiaramente iniziato a determinare le cause della malattia. Un altro scienziato, svizzero di nascita e francese di formazione, era invece giunto a Canton proprio per mettere alla prova un suo siero che egli riteneva potesse guarire dalla peste, e aveva preso contatto con l’ambasciatore francese lì residente per poter avere la possibilità di provarlo su qualche malato.

È qui che entra in scena Tisè: presentava i primi sintomi della peste già da alcuni giorni, e da qualche ora la malattia era diventata manifesta. Non si prevedeva che potesse sopravvivere ancora a lungo. Essendo un convertito alla religione degli europei, era uno dei pochi che poteva accettare di essere curato dai diavoli stranieri, e – non si sa se con esplicito consenso o solo per assenza di obiezioni – venne sottoposto alla cura. Il siero gli venne inoculato in dosi da 10 cc, e in meno di 24 ore i miglioramenti furono tali che un medico non avrebbe neppure riconosciuto in lui un appestato, a meno di non averlo visto nei giorni precedenti. Tisè diventa così la prima persona a sopravvivere alla peste per mezzo di una cura inventata dall’uomo.

Alexander Yersin

L’uomo in questione si chiama Alexander Yersin. Nel 1895 ha poco più di trent’anni, essendo nato ad Aubonne nel 1863. Dopo il primo successo, continua la sperimentazione con altri malati, e il suo siero dimostra un’efficacia di guarigione superiore al 90%. Continuerà ad operare in Asia, nell’Indocina francese, dove coltiverà molti diversi interessi oltre alla medicina; e infine morirà ottantenne a Nha Trang, nell’attuale Vietnam. Il bacillo della peste che tormentò la regione di Canton alla fine dell’Ottocento sarà poi battezzato Yersinia Pestis in suo onore.

Nel 2010, un team internazionale di scienziati ha eseguito una serie di studi su antiche sepolture in Inghilterra, Francia e in Olanda, confrontando antichi DNA proteici, e giungendo alla conclusione che la Morte Nera, la terribile pandemia che imperverso nel XIV secolo in Europa, altro non era che una forma di Yersinia Pestis. Ma nel 1347 non esisteva alcun siero.

La “morte nera” non veniva chiamata così dalle sue vittime: il nome si fissa dopo, nelle cronache[2]. Per coloro che morirono o videro morire gli altri, la malattia non aveva ragione, scopo, causa, e quindi neanche nome. Era la grande morte, era la malattia totale, la devastazione inarrestabile, e basta. L’epidemia di peste che stravolse l’Europa del XIV secolo, e che con ogni probabilità era solo parte di una più vasta pandemia globale, è forse l’evento che ha causato il maggior numero di morti dell’intera storia. È ovviamente difficile dare dei dati precisi, vista la distanza temporale e la incompletezza delle fonti, ma anche solo la forbice compresa tra la stima più ottimistica e quella più ottimistica è in grado di dare un quadro terrificante:

Numero di morti totali: tra i 70 e i 200 milioni

Numero di morti in Europa: tra i 20 e i 30 milioni

Riduzione della popolazione europea: tra il 30% e il 60%

Numeri che sono tanto più impressionanti se si considera che l’intera popolazione mondiale, a quel tempo, era stimata attorno al mezzo miliardo di persone.

La Morte Nera devastò tutta l’Europa, o quasi, ma in modi diversi. Se la zona polacca di Cracovia e della Russia Bianca ne risultarono quasi immuni, ci furono regioni che rimasero virtualmente senza sopravvissuti, borghi e villaggi desertificati.

Il contagio arrivò dalla Crimea: le navi genovesi mantenevano contatti attraverso il Mar Nero con quelle regioni attraverso floride rotte commerciali, e i ratti trasportati nelle stive sbarcarono a Genova, Marsiglia e negli altri porti mediterranei d’Europa diffondendo il contagio. Tra il 1347, quando le isole e i porti italiani cominciano a ricevere il contagio, e il 1353, quando la peste ha ormai seminato morte e distruzione fin oltre Mosca e tutta la Scandinavia, il vecchio continente subisce la più grande tragedia della sua storia.

La diffusione della peste nera

Naturalmente, non è solo l’Europa ad essere colpita, e non è la Crimea il focolaio iniziale dell’infezione. Il bacillo della Yersina Pestis è con ogni probabilità endemico dell’Asia Centrale, e arrivò in Crimea attraverso i commerci terrestri che univano l’Asia e l’Europa, per mezzo della celebre Via della Seta. È probabile che le prime regioni in cui il bacillo della peste attaccò l’uomo fossero le zone del Pamir a dell’Altaj, e che la causa ultima del nascere della malattia sia stata non tanto la diffusione dei ratti e dei roditori, quanto piuttosto il suo esatto contrario, ovvero la grande moria di questi animali nel secondo quarto del Trecento. Secondo logiche naturali, per quanto spietate, ciò che accadde è rapidamente comprensibile: il bacillo della peste è trasportato da pulci che normalmente infettavano solo i roditori. In quel periodo, i ratti e gli altri roditori asiatici scarseggiarono al punto che le pulci si adattarono ad attaccare l’uomo, e il bacillo della peste si trasmise all’umanità. Nel gioco della ricerca della causa ultima, ci si deve quindi fermare quando si scopre che la grande moria dei roditori asiatici fu causata da cause meteorologiche: l’inizio del XIV secolo vide in tutto il globo uno straordinario raffreddamento del clima, noto oggi come “piccola era glaciale[3]”, che provocò una generale scarsezza di cibo.

L’indagine storica degli eventi meteorologici è complicata e difficile: l’estensione temporale e la natura globale stessa della piccola era glaciale è ancora controversa, così come non sono del tutto chiare le cause e gli effetti che ha provocato. Sembra comunque assodato che, dopo un periodo medievale relativamente caldo, dal IX al XIII secolo, un raffreddamento generale[4] del pianeta sia cominciato appunto verso il 1300 per terminare meno di due secoli fa. Verso il 1850 la tendenza è cambiata, e quello in cui viviamo è un periodo globalmente più caldo: una delle ragioni per cui è così difficile convincere tutti gli addetti ai lavori del pernicioso contributo umano al riscaldamento globale dei nostri tempi – peraltro ormai dimostrato oltre ogni ragionevole dubbio – sta proprio in questa osservazione che la temperatura media del pianeta subisce oscillazioni anche per cause naturali.

Quel che è certo è che il periodo storico europeo che va da Carlo Magno a Dante Alighieri fu ragionevolmente ricco e pacifico, in cui la popolazione del continente crebbe in modo sensibile e la qualità della vita (naturalmente considerandola in media, e su scala generale) crebbe in maniera sensibile. Viceversa, il Trecento inizia e procede sotto segno del tutto diverso: una drammatica carestia – causata appunto da un repentino e perdurante cambiamento climatico – colpisce ferocemente la popolazione europea, rendendo la vita drammaticamente più difficile di quanto fosse stata nei secoli immediatamente precedenti; la peste che arriva dall’Asia verso la fine della quinta decade è, per gli esseri umani di quel periodo, una drammatica e virulenta tragedia che conclude un periodo già drammatico di suo.

Un medico ai tempi della peste. Il becco della maschera serviva a contenere delle essenze profumate, per combattere gli odori dei malati

Se le teorie sulla grande carestia e sull’insorgere della peste sono corrette, alla fin fine la causa delle due grandi sterminatrici del secolo è la stessa; ma, quel che più conta, è che per la gente del tempo questa causa era del tutto ignota, inspiegabile: e, senza dubbio, era vissuta soprattutto come una crudele opera del diavolo o, peggio ancora, come una terribilissima punizione divina. E questo rende le conseguenze della Morte Nera ancora più misteriose e difficili da riconoscere di quanto lo siano le cause.

Il punto centrale è che il Medioevo, almeno per quanto riguarda l’Europa, è il periodo in cui è più stretto e completo il rapporto tra l’Uomo e Dio. Non soltanto gli aspetti sociali, politici e rituali, ma anche ogni dettaglio della vita privata è virtualmente regolamentato da un intenso rapportarsi al divino. Quali che siano state le cause storiche che hanno condotto l’occidente ad una tale dedizione, certo è la religiosità diffusa a scandire, nei secoli precedenti e successivi all’anno Mille, il ritmo della vita quotidiana.

L’avvento della carestia prolungata prima e l’insorgere della feroce epidemia di peste, secondo molti studiosi, è stata la causa principale, se non proprio l’unica, della rottura del patto tra umano e divino. In una ardita semplificazione, si può riassumere la sequenza logica facilmente: se un mondo che ha dedicato ogni sua azione a compiacere la divinità si ritrova improvvisamente ridotto e morire di fame e di pestilenza, e in misura così grande, allora o la divinità adorata non è potente come la si credeva, perché ha lasciato i suoi figli preda del Maligno; o addirittura non è buona come la si credeva, perché punisce i suoi figli in maniera così atroce e diffusa, senza che essi siano in grado neanche di capire quali siano le colpe di cui si sarebbero macchiati.

Con questa chiave di lettura, la Morte Nera avrebbe gettato i semi del mondo nuovo che sarebbe germogliato da lì a poco: il riposizionamento dell’Uomo al centro degli interessi degli uomini, con l’Umanesimo; una maggiore predisposizione ai piaceri e una più decisa avversione alle penitenze e alle rinunce, cantata dal Rinascimento, fino alla creazioni di poteri temporali più decisi e indipendenti dalla dipendenza del volere divino e imperiale, con la creazione degli stati nazione; il tutto, coronato infine, qualche decennio più tardi, con la decisione di ribellarsi direttamente alla Chiesa tramite la Riforma Protestante.

Se le conseguenze di largo respiro e di lungo periodo sono ancora (e probabilmente lo saranno ancora per molto tempo, se non sempre) oggetto di discussione, ce ne sono molte dirette e semplici da constatare. È impossibile uscire da una scuola superiore senza aver incontrato, tra le grandi opere della letteratura italiana e mondiale, il Decameron di Giovanni Boccaccio. La raccolta di novelle ha come fulcro narrativo proprio il tentativo di salvarsi dall’infuriare della peste del Trecento, con dieci ragazzi che decidono di abbandonare momentaneamente Firenze e trasferirsi in campagna. Nei dieci giorni[5] che ispirano il titolo dell’opera, il tempo trascorrerà nel raccontarsi cento novelle, che di fatto costituiscono la struttura narrativa del Decameron.

Il “Decameron” secondo il pittore inglese WaterHouse (trovare qualcosa di pubblicabile con una “ricerca per immagini” con chiave “Decameron” è impresa di tutto rispetto.

Il tema delle cento novelle è davvero molto vario, anche se le avventure amorose – o l’Amore tout-court – sono certo l’elemento che risalta con maggior rilievo, al punto che i dizionari italiani devono annoverare tra i loro lemmi l’aggettivo “boccaccesco” con un significato[6] probabilmente troppo poco generoso verso il grande poeta e scrittore. Anche perché l’opera generata dalla Peste Nera segna davvero una rivoluzione letteraria, genera entusiasmi e, come sempre, degli emulatori. Il più grande tra gli emulatori di Boccaccio è certamente Geoffrey Chaucer, che costruisce la sua opera più famosa, “The Canterbury Tales”, sotto l’evidente e riconosciuta influenza del fiorentino. Si ipotizza che Chaucer potesse aver incontrato direttamente lo stesso Boccaccio (anche se altri sostengono che invece incontrò Petrarca) durante il suo viaggio in Italia nel 1373: è comunque certo che lo stile poetico e narrativo italiano entusiasmò il pellegrino d’oltremanica, ed è con le opera scritte seguendo questi dettami stilistici che assunse alla gloria di “padre della lingua inglese”.

Forse attribuire alla Black Death la nascita della Letteratura Inglese è davvero un passo esagerato e illegittimo, ma nella ricerca di pretesti per arrivare a parlare di matematica il percorso è ormai quasi completo: dalla peste a Boccaccio, da Boccaccio a Chaucer, resta solo un passo quasi immediato. L’opera più famosa di Chaucer è infatti talmente importante per gli inglesi che è impossibile non pensare che la prima grande opera britannica di matematica ricreativa non abbia volutamente citarla e ricordarla fin dal nome: è infatti con il titolo “The Canterbury Puzzles” che Dudeney pubblica, nel 1907, la sua più famosa raccolta di problemi di matematica e logica.

Henry Dudeney

Henry Ernest Dudeney nasce il 10 Aprile 1857 a Mayfeld, nel Sussex, da una famiglia non particolarmente ricca o prestigiosa, ma dove abbondavano i maestri di scuola e l’interesse per la matematica: da questo punto di vista, l’elemento più rappresentativo della famiglia è forse il nonno paterno, che passa gran parte della vita a fare il pastore ma studia da autodidatta astronomia e matematica, fino a diventare in tarda età maestro a Lewes. Il primo amore di Henry sono comunque gli scacchi, con i quali familiarizza fin da piccolo, dilettandosi non solo nel gioco ma anche nella creazione di problemi.

Ed quasi certamente per la sua passione nel creare indovinelli che si avvicina alla matematica. Dudeney non riceve un’educazione matematica continua e tradizionale: a tredici anni comincia a lavorare come cameriere, anche se continua a coltivare il suo interesse collaborando con riviste specializzate e inventando quesiti con lo pseudonimo di “Sfinge”, prima dei trent’anni si sposa con una scrittrice, e conduce una vita tranquilla e nient’affatto accademica.

Con il senno di poi, è facile qualificare Dudeney come il più grande creatore di indovinelli d’Inghilterra; ed era forse inevitabile che si stabilisse una corrispondenza e una collaborazione con il più grande creatore di puzzle d’oltre Atlantico, Sam Loyd. I due prendono contatti nel 1893, e cominciano a scambiarsi idee. Purtroppo, cominciano presto anche le liti: Loyd ha quattrodici anni più di Dudeney, e forse per questa sua maggiore anzianità si sente autorizzato (almeno, a quanto dice lo stesso Dudeney), a pubblicare a proprio nome puzzle creati dall’inglese. Quel che è certo che Dudeney e Loyd diventano presto acerrimi nemici, e soprattutto Dudeney continuerà a vedere Loyd come il fumo negli occhi.

Ma sono davvero molte le cose che li accomunano, ai nostri occhi: il periodo storico, la strana e rarissima professione di creatori di quesiti di matematica ricreativa, il modo stesso di porre i problemi. Da un punto di vista più tecnico, è quanto mai singolare che, tra le centinaia di problemi creati, quelli dedicati agli scacchi siano tutti originalmente non-standard, spesso infarciti di narrazioni e ambientazioni complesse per giustificare posizioni davvero bizzarre sulla scacchiera.

Da modesti scimmiottatori (e soprattutto ladri) delle loro idee, non sappiamo bene se sia stato un bene o un male vederli litigare e separarsi. Capita spesso, ormai, che lo stesso quesito compaia in rete talvolta attribuito all’uno, talvolta all’altro[7]; forse il loro ego ne risentirà, ma se tutto ciò ha contribuito ad innalzare la loro produzione, noi non possiamo che esserne egoisticamente contenti.

2. Problemi

2.1 Si riparte con il tiro con l’arco!

Prima un disclaimer: il titolo di questo problema è stato vergato il sedici marzo, di ritorno, giustappunto, dalla cerimonia di apertura dell’archery season della Compagnia degli Arcieri del Chinotto (non cominciate a pensare a cose strane: una birra e un chinotto a testa, anche se il chinotto era di dimensioni notevoli).

Il testo del problema, invece, esce dalle nostre penne elettroniche il trenta di marzo, e dalla sunnominata giornata del sedici i nostri gagliardi flettenti non hanno più rivisto la luce del sole (e anche su sabato prossimo si stanno addensando fosche e metaforiche nubi, quantomeno dalla parte di Fred).

Comunque, ce la faremo. L’unica cosa che supera il nostro ottimismo è l’incapacità nel tiro. Ma prima, una piccola nota matematica, giusto per definire i termini.

Si definisce diametro di una parte del piano E il limite superiore delle distanze ottenibili considerando due punti qualsiasi di E.

Che allo scrivente [Rudy speaking] lascia qualche dubbio, visto che vorrebbe un maggiore stress sul fatto che dovete prendere in considerazione tutti i punti del “cosagono”, e scegliere il massimo. Ma questi sono dettagli. Torniamo alla logistica arcieristica.

L’idea è di utilizzare un appezzamento di terreno opportunamente circondato da fermafreccia che ha l’interessante caratteristica di essere un triangolo rettangolo pitagorico di lati [3,4,5] (unità arbitrarie); l’usare i lati per tirare, però, ci fa sentire un po’ “rinchiusi”, e Rudy sta preparando ottime scuse per la sua inettitudine nell’arte basate sul fatto che “il muro è dalla parte sbagliata” (è una scusa in quanto Rudy tira di destro, esattamente come Doc e Fred). I Nostri hanno intenzione di sezionare il suddetto triangolo in quattro parti disgiunte[8] in modo tale da rendere minimo il maggiore dei quattro diametri [Visto, che il concetto serviva? RdA]. Evidentemente, questo diventerà la linea di tiro (e, se proprio siete curiosi, potreste dedurre le “unità arbitrarie”, considerato che tiriamo sui 18 metri), e le zone libere verranno piantumate ad essenze opportune. Quindi, quello che vi chiediamo è di trovare le quattro partizioni.

Oh, come al solito non fermatevi alla domanda “facile”: per un generico triangolo pitagorico [p,q,r], con p²+q²=r², riuscite a progettare la linea di tiro? E se considerassimo come linee di tiro tutti i diametri delle quattro partizioni fissate come sopra, quanto verrebbero le distanze?

Insomma, rischia di diventare una via di mezzo tra il tiro con l’arco e il golf. Almeno, questa volta, non perdiamo le frecce.

A titolo di divagazione strettamente personale (nel senso che se l’è inventata lui), Rudy sta cercando di calcolare una cosa: considerato che le distanze di tiro FITA outdoor sono 9, 7, 5 e 3 decametri (36 frecce da ogni postazione, in quest’ordine: alla fine, avete bisogno di qualcuno che vi raccolga le braccia da terra), volendo utilizzare i diametri delle quattro partizioni di un “qualcosagono” di area minima, come conviene organizzare il tutto? Attenti che abbiamo detto “diametri delle partizioni”: troppo facile, piazzarli che si incrocino tutti a metà distanza (sicuri? Mah... Ecco, potreste calcolare anche questa. Senza elastici, solo con la biro).

2.2 Le Rouge et le Noir: omaggio ad Henry

Nel senso che parliamo di rosso, di nero e di Henry Beyle (detto Stendhal). Comunque, il problema è di un paio di anni fa, ma non ci preoccupiamo se generalizzate la cosa.

Abbiamo due poligoni (tranquilli: convessi) P₁ e P₂ su due diversi piani nello spazio, per i quali ciascuno degli n lati (sì, stesso numero per tutti e due i poligoni) è etichettato con un numero 1, 2, 3, ...n; consideriamo l’insieme E dei segmenti che uniscono ciascuno dei vertici di P₁ ai vertici di P₂: tutti questi segmenti, così come i lati dei poligoni, sono tracciati con l’inchiostro rouge o noir in modo tale che non esiste nessun triangolo monocromatico tra tutti quelli che sono formati da un lato di un poligono e da due elementi di E .

Visto che siamo bravi, vi lasciamo tracciare in rosso il lato 1 di P₁: adesso, supponiamo i due casi “dell’anno scorso”: nel primo caso, n=2012, nel secondo n=2013 (ma se generalizzate, siamo tutti contenti, anche Stendhal).

Quello che vorremmo sapere, è di che colore sono il lato 1783 di P₁ e il lato 1842 di P₂.

“Oh, Rudy, dove li hai presi ‘sti due numeri?” Facile. Stendhal è nato il 23 gennaio del 1783 ed è morto il 23 marzo del 1842. E oggi è il 23 marzo[9].

O lo risolvete, o vi leggete entro il mese prossimo l’opera completa in francese. Niente scuse che non la trovate, ve la passo io (legale) in elettronico.

2.3 Un altro tre per due

Non vorremmo sbagliarci ma, essendo questo il sesto “tre per due”, una volta tanto il nome è corretto. Comunque, il motivo è sempre il solito. E, stavolta, secondo noi ha l’interessante caratteristica di essere un problema dall’aspetto carino in un campo che, per manifesta incompetenza, non ci piace. Inoltre, abbiamo finalmente un problema “sull’anno” che non arriva per la notte di San Silvestro, e che quindi potrebbe rivelarsi utile per tenere impegnati i parenti antipatici verso Pasqua.

Ma andiamo al problema: non de-matematizzato, chiaramente.

Una curva C è espressa nell’intervallo [0,2014] [ve l’avevo detto, che c’entrava l’anno! (RdA)] dalla funzione:

.

dove la coppia di barre verticali indica, come d’uso, la funzione di valore assoluto, ed è ripetuta 2014 volte.

Dimostrate chi il massimo e il minimo assoluti (di ordinata rispettivamente h e b) sono unici nell’intervallo.

Una formica parte dal punto e, camminando sempre sulla curva data, arriva sino al punto di massimo assoluto, che marca con una croce; procede quindi sino al punto di minimo assoluto, che viene anch’esso marcato con una croce; quindi si reca nel punto di massimo assoluto non marcato nell’intervallo, e lo marca, per procedere quindi al punto di minimo assoluto non marcato, che viene anch’esso marcato, e avanti in questo modo sin quando non restano punti da marcare nell’intervallo: nel caso (posto che si presenti) di uguali coordinate, la formica marca il più vicino al punto dal quale sta partendo.

In che punto si ferma la formica, e dopo aver percorso quanta strada?

Una seconda formica parte dal punto (ricordate che b è l’ordinata del minimo assoluto) sulla retta e procede sino al punto di minimo assoluto della curva: a questo punto, la formica torna al punto di partenza lungo la curva C, il punto e la parte necessaria dell’asse y.

Qual è l’area delimitata dal percorso di questa seconda formica?

Secondo noi aveva ragione Jordan. Non quello che ha definito il concetto di “curva”, l’altro: quello che diceva che i matematici sono tutti matti [L’avrà detto, prima o poi, qualcuno di nome Jordan, no?]. Liberi di generalizzare agli anni passati, presenti e futuri, evidentemente.

3. Bungee Jumpers

In questa rubrica, abbiamo affrontato svariati problemi che ci hanno portato pericolosamente vicini all’Ultimo Teorema di Fermat: questo, anche se piuttosto semplice (secondo noi, avete risolto cose più complicate), ci pare appartenente a questa serie.

Trovare le coppie (p, n), con p primo e intero per cui pn è la somma di due cubi.

La soluzione, a “Pagina 46”

4. Soluzioni e Note

Aprile.

Avanzato, tanto per cambiare. Non tanto da dire, solo che vogliamo a tutti i costi uscire, e allora ci proviamo: queste S&N sono velocissime.

Però non senza un grande grazie a tutti quelli che mi hanno mandato gli auguri e a cui non ho ancora risposto: perdonatemi.

4.1 [180]

4.1.1 Presa di posizione

Continua a tormentare Camillo il problema dell’Italo, rivediamo il testo:

Lo Stato emette una nuova moneta, l’Italo, che compare in dodici valori facciali distinti tali che qualsiasi importo intero da 1 a N Italo possa essere sempre composto con un insieme di otto monete o meno (non necessariamente distinte): N viene fissato per decreto all’inizio.

Supponiamo sia stato fissato N=6543: che insieme di Italo stampate?

Causa svalutazione ritirate tutto il vecchio conquibus e emettete una nuova serie sempre da 12 pezzi, ma questa volta con gli otto pezzi sempre non necessariamente distinti dovete riuscire a pagare sino a N=13000: trovate la serie.

Prevedendo ulteriori svalutazioni nel futuro, cominciate a porvi il problema di quale sia il massimo N per cui con la solita serie da dodici e impegnando al più otto pezzi non necessariamente distinti, potete continuare a fare questo giochino.

In RM181 scorso avevamo pubblicato la soluzione di trentatré, e in RM182 quella di Camillo, che torna alla carica:

Presa di posizione, e tre. Ho provato ad usare solo numeri primi, delusione, si raggiunge il 13000 ma usando anche gli altri numeri si arriva più in alto.

Ho raggiunto il 17467 con questa serie: 6940, 4525, 2898, 1693, 1174, 882, 311, 128, 81, 23, 7, 1 e poi sono passato ai soli numeri primi.

Questa volta per raggiungere il nostro 6543 ci sono voluti 11 valori: 6101, 2371, 1669, 769, 389, 251, 103, 41, 13, 2, 1 che raggiunge il 9862.

Il meglio che sono riuscito a fare è stato 15652 con questa serie: 6581, 3967, 3329, 1933, 773, 509, 241, 89, 53, 11, 2, 1.

Curioso è che ho trovato anche 7 serie che raggiungono esattamente il 13000, una delle quali è questa: 4591, 4261, 3329, 1933, 773, 509, 241, 89, 53, 11, 2, 1 qui mi fermo ed abbandono il programma a meno che qualcuno non desideri delucidazioni.

E se usassi obbligatoriamente il mio anno di nascita che è primo fin dove potrei arrivare?

A proposito; una giovane coppia di maggiorenni ha avuto una figlia, tutti e tre sono nati in “anni primi” di fila; indovinate i 3 anni primi.

No, noi no, abbiamo da far uscire questo numero che tra poco è metà mese, fate un po’ voi.

4.2 [182]

4.2.1 Diciotto!

Per i festeggiamenti del diciottesimo del più giovane Assistente di Laboratorio di RM, la birra scorreva a fiumi ed il Capo si è divertito a far giocare il festeggiato per scegliere i regali. Ecco i problemi proposti:

1. “Fred, qui ci sono tre regali: R_1 è bellissimo, R_2 passabile, R_3 è una fregatura. Sei autorizzato a fare un’affermazione: se questa sarà vera, io ti darò o R_1 o R_2, mentre se sarà falsa ti becchi R_3. Cosa mi dici?” Quale espressione garantisce a Fred di ricevere R_1?

2. “Fred, adesso abbiamo quattro regali: R_1 bellissimo, R_2 sempre passabile, ma questa volta R_3 e R_4 sono tutte e due bruttini; io mi comporto come prima, nel senso che se l’affermazione è esatta ti consegno R_1 o R_2, se invece è sbagliata ti consegno R_3 o R_4; cosa mi dici?” In questo caso Fred è interessato ad R_3, che cosa dice?

3. Fred si è stufato di rispondere a quesiti del tipo 1 e cerca di rendere il compito impossibile al rompiscatole di turno, che cosa dice?

Bellissima e divertentissima la soluzione di Alberto R., eccola:

Primo caso: Affermazione vera implica (R1 xor R2) and not R3. Affermazione falsa implica R3 and not(R1 or R2). Fred desidera R1. Fred pronuncerà la frase: "Io riceverò R1 oppure R3". L’autoreferenza ha colpito ancora!

Secondo caso: Stesse condizioni del primo caso, ma Fred desidera R3. Fred raggiungerà il suo scopo semplicemente pronunciando una qualunque frase falsa, ad esempio "2 + 2 = 5" oppure, meno banalmente, "Il nostro affezionato lettore Alberto R è stato felicissimo di mettere alla prova la sua abilità informatica cimentandosi, senza neanche tirare un moccolo, nell’apertura di RM in formato .EPUB in luogo del consueto noioso vecchio scontato .PDF"

Terzo caso: Affermazione vera implica (R1 xor R2) and not(R3 or R4). Affermazione falsa implica (R3 xor R4) and not(R1 or R2). Fred desidera R1. Fred pronuncerà la frase "Io riceverò R1 oppure R3 oppure R4"

Quarto caso: Stesse condizioni del terzo caso, ma Fred, ormai scocciato, non è interessato al alcun regalo; vuole solo mettere in difficoltà il rompiscatole proponente. Fred pronuncerà la frase "riceverò R3 oppure R4"

Il solito pignolo piantagrane osserverà che le soluzioni del primo, terzo e quarto caso sono inaccettabili perché le affermazioni ivi citate si riferiscono al futuro, quindi al momento in cui si deve decidere quale regalo consegnare esse non sono né vere né false, ma ancora indeterminate. In altre parole la scelta del regalo da consegnare, che dovrebbe essere l’effetto della verità/falsità dell’affermazione di Fred, ne diventa (illecitamente) la causa.

Non mi sembra un’obiezione da poco. Cosa gli rispondiamo?

Non saprei, cosa rispondere. Però l’obiezione è più che lecita e potrebbe stimolare qualche altro lettore. Del resto la soluzione di Franco57 ottiene gli stessi risultati:

Mettiamo che i regali belli, quelli che vengono dati se l’affermazione di Fred è vera, siano nell’insieme verde V in figura, mentre i regali brutti, quelli che vengono dati se l’affermazione di Fred è falsa, siano nell’insieme rosso F. Mettiamo che Fred voglia un regalo qualsiasi dell’insieme ellittico Y che a priori potrebbe intersecare sia V che F.

Si vede facilmente che per ottenere il suo scopo basta che Fred affermi “riceverò un regalo fra quelli dell’insieme X tratteggiato” - cioè , se non riusciamo a rinunciare alle formule.

Infatti non gli può essere regalato un verde non tratteggiato perché la sua affermazione sarebbe falsa e neanche un rosso tratteggiato, ma questa volta perché l’affermazione sarebbe vera. Di contro gli si può regalare un qualsiasi verde tratteggiato perché la sua affermazione sarebbe vera ed anche un qualsiasi rosso non tratteggiato perché l’affermazione sarebbe falsa. In conclusione Y è esattamente l’insieme dei regali che può ricevere.

Questa generalizzazione comprende tutti e tre i casi del problema e vale per insiemi finiti, infiniti ed anche vuoti. Nel primo caso abbiamo e di conseguenza Fred afferma che riceverà o ; nel secondo caso abbiamo e di conseguenza Fred afferma che riceverà ; nel terzo caso, più raffinato, abbiamo e di conseguenza Fred afferma che riceverà o .

Ecco. Stessi risultati dichiarati da GaS, che non ci aveva dato giustificazioni. Bene, siamo tutti d’accordo, procediamo con il secondo problema.

4.2.2 Agosto, grazie a Carlo

Il titolo, qui, si riferisce al fatto che il Capo, nel mese del suo compleanno, ha battuto la fiacca e ha scritto un problema solo, l’altro l’ha copiato da un’idea di Carlo, detto anche Carlo il Grande, grande frequentatore del nostro blog di LeScienze. Eccolo qui:

In quanti modi diversi si può riempire una borsa con N frutti rispettando i seguenti vincoli?

· Il numero delle mele deve essere pari.

· Il numero delle banane deve essere multiplo di cinque.

· Ci devono essere non più di quattro arance.

· Ci deve essere almeno una pera.

Beh, cominciamo con GaS:

Assolutamente non facile, almeno per me, affrontare il problema con un metodo “finito”, mi appoggio allora ad un po’ di brute force per capire cosa ne viene fuori.

Prima di tutto due condizioni che do per scontate ma che non sono espressamente dette:

- la frutta può essere solo dei 4 tipi indicati (Mela-Banana-Arancia-Pera)

- 0 è un multiplo di qualsiasi numero... (sì, che ci volete fare, sono decisamente pignolo)

Butto giù uno scriptino e mi ricavo i seguenti risultati per N da 1 a 40, che messi in un grafico danno qualcosa di decisamente “pulito”:

Sono quindi abbastanza sicuro che esista una formula chiusa per la soluzione del problema ma non saprei proprio da dove partire. Quindi baro e mi affido ad OEIS che mi sputa fuori la sequenza A087811 (parente strettissima della A002620) che è la serie che rappresenta “Numbers n such that ceil(sqrt(n)) divides n”[10]. Sono quindi sicuro che non riuscirei mai a tirare fuori una formula del genere e quindi, vigliaccamente, desisto.

La cosa che mi piace della formula è che tutti i numeri quadrati fanno parte della sequenza e sono intervallati da un singolo numero che non è un quadrato. Chissà cosa diavolo c’entra con la frutta...

Eh, a saperlo! Volendo basta chiedere a trentatre, la sua soluzione pare non lasciare punti aperti:

Siano P, A, M, B i numeri di pere, arance, mele, banane, e il numero di soluzioni di con i vincoli esposti nel problema. Si suggerisce di "esplorare i dintorni"; provo a fornire diversi punti di vista.

1) Dato N il problema si può visualizzare con un grafo. In figura il caso .

Il grafo è costruito nell’ordine B, M, A, P. I numeri nei nodi indicano i frutti assegnati del tipo corrispondente.

Si tiene conto dei vincoli: riga B solo multipli di 5, riga M solo numeri pari, riga A massimo 4, riga P almeno 1 frutto. Non sono disegnati i percorsi impossibili (p.es. quelli che arrivano in A senza lasciare almeno un frutto per P).

I nodi in riga P sono terminali (le foglie del grafo). Ogni percorso dalla radice O a una foglia corrisponde a N (cioè 7) frutti assegnati.

Ogni foglia corrisponde a una soluzione, perciò .

Le 16 soluzioni sono date dai percorsi da O alle foglie

2) si può calcolare in modo ricorsivo; introducendo successivamente P, A, M, B si ha

- solo P: : una sola soluzione tutta di pere, questa soluzione esiste sempre per

- solo P, A: deve essere per ogni A esiste la soluzione se

cioè 1 soluz. se , 2 soluz. se , ... fino a 5 soluz. se - solo P, A, M : con le soluzioni sono con

- tutti i frutti P, A, M, B: con le soluzioni sono con

Combinando il tutto

[1]

Si ha p.es. .

3) Al problema si può dare una veste geometrica.

Se i valori P, A, M, B sono le coordinate di un 4-spazio cartesiano, ogni punto a coordinate intere non negative rappresenta una diversa combinazione. Per ogni N la condizione individua un 3-spazio, e il conteggio dei punti interni – tolti quelli proibiti dai vincoli sui vari tipi - è il numero S(N).

Eseguendo il conteggio ricorsivamente si ritrovano le formule precedenti. In fig. 2 - I. il caso dei soli frutti P, A con i vincoli ; i punti sulla riga sono . In II. il caso P, A, M ; i punti sul piano , con : pari, sono . Non disegno il caso completo dove il conteggio va fatto su un tetraedro.

Lo spazio 3) e il grafo 1) sono equivalenti; le coordinate di un punto sono i valori nei nodi del corrispondente percorso dalla radice alla foglia.

Nei casi 1), 2), 3) è ottenuta introducendo i frutti in un certo ordine ma il problema è simmetrico; usando un altro ordine si ottengono grafi e funzioni diverse ma equivalenti.

4) si può ricavare con un metodo simmetrico, diretto e generale (di fatto una applicazione di analisi combinatoria). Costruiamo le funzioni

.

In ogni funzione gli esponenti di X sono i numeri di frutti possibili dati i vincoli; i coefficienti dei terminidanno il numero di soluzioni per quel frutto. P.es. in gli esponenti sono i valori di M possibili e si ha una unica soluzione (tutta di mele) solo se ; si può scrivere

che è la funzione generatrice delle soluzioni con solo M. Il prodotto delle quattro funzioni è la funzione generatrice delle cioè

[2]

Infatti in il termine può essere generato solo dai prodotti con ed m misura il numero di combinazioni diverse. Separando in frazioni semplici

ed espandendo le frazioni in potenze di X si ottiene l’espressione non ricorsiva

[3]

che equivale alla [1]; lo stesso metodo fornisce espressioni equivalenti alle già trovate. Il metodo si può applicare al caso generale di m tipi di oggetti in cui ogni tipo può assumere solo un insieme, finito o no, di valori. Nel caso in esame, in cui i vincoli sono del tipo , , il numero di soluzioni è sempre, salvo i primi termini, un polinomio in N. Per m tipi senza vincoli si ha , e infatti è il numero di combinazioni di N oggetti scelti con ripetizione fra m tipi diversi.

Chi liquida il problema in quattro e quattr’otto è Alberto R.:

Abbiamo M mele, B banane, A arance, P pere, e sia N la loro somma.

I vincoli sono: M=2m; B=5b; A=0...4; P>0 (con m, b interi ≥ 0)

La scorciatoia che conduce alla soluzione è la costatazione che la somma M+P (anche senza conoscere i singoli addendi) determina univocamente i valori di B e di A, poiché, dati i vincoli imposti, B non può che essere il quoziente di [N-(M+P)]/5 e A il resto delle stessa divisione.

Dobbiamo quindi contare in quanti modi il numero X = M+P può essere ripartito nei due addendi M e P con M pari e P>0.

Ciò è possibile in X/2 modi diversi se X è pari e in (X+1)/2 modi diversi se X è dispari, ovvero in (X+Xmod2)/2 modi diversi per qualunque parità di X.

Eseguendo la sommatoria di quest’ultima espressione per X da 1 a N si ottiene la formula risolutiva: (N^2 + 2N + Nmod2)/4

La soluzione di Gnugnu è più complessa e passa per le critiche ai metodi del Capo (inevitabili, se lo conoscete) all’ammirazione per il grande Carlo, alle possibili soluzioni alternative:

Le condizioni cui devono sottostare le arance e le banane si completano a vicenda: le banane, multiple di 5, e le arance, in numero uguale ad uno dei possibili resti della divisione per 5, si possono considerare come un ibrido, la banancia, che può essere presente nella borsa in quantità qualsiasi, ma in una sola maniera.

Se aggiungiamo le pere, anche loro si possono stipare in qualsivoglia quantità (tranne 0) e in un solo modo, per qualsiasi h abbiamo esattamente h diverse possibilità di mettere in borsa h pere-banance (d’ora in poi pab): 1 pera e h – 1 banance, 2 pere e h – 2 banance…. fino a h pere e 0 banance.

Mancano solo le mele che devono essere pari, perciò le pab dovranno avere la stessa parità di N; distinguiamo i due casi.

N pari, N=2M. Le pab potranno essere 2, 4 , 6 ... N a cui si abbinano N – 2, N – 4, N – 6, … 0 mele. Il numero delle diverse maniere QN per riempire la borsa sarà:

N dispari, N=2M+1. Le pab potranno essere 1, 3, 5 … N e le mele N – 1, N – 3, N – 5, … 0. Da cui:

La successione QN è una zip ottenuta intercalando alla successione del doppio dei numeri triangolari quella dei quadrati. Le formule si possono fondere ottenendo, mediante troncamento o correzione puntuale, espressioni valide per ogni N, senza badare alla parità. Queste dovrebbero essere fra le più semplici:

I termini sono mutuamente legati da molte relazioni. Ne riporto alcune, omettendone la dimostrazione, sempre molto semplice.

Ogni termine di posto dispari è la media aritmetica di quelli contigui: 2Q2M+1=Q2M+Q2M+2

Ogni termine di posto pari è la media geometrica di quelli contigui: Q²2M=Q2M−1Q2M+1

QN=QN₋₂+N

QN ₊₂=2QN−QN₋₂+2

QN=2QN₋₁−QN₋₂+N mod 2

Mi sarei fermato qui, ma nel problema vengono proposte altre considerazioni. Se l’avesse chiesto il GC avrei svicolato, perché mi bistratta rispondendomi, quando si degna di farlo, a prezzemolate, fingendo di non capire che cerco di dargli una mano. Siccome è invece una proposta Carlo, con cui intrattengo una copiosa corrispondenza, dimentico la soluzione precedente e valuto come si potesse affrontare il problema seguendo pedissequamente l’ordine con cui i frutti vengono presentati.

Si potrebbe iniziare costruendo una tabella delle possibili combinazioni per piccoli valori di N. Rappresentando ciascuna borsa possibile con un vettore [p,a,m,b] le cui quattro componenti corrispondono rispettivamente alla quantità di: pere, arance, mele e banane contenute.

L’altezza delle pile di borse possibili al variare di N ha un apparente andamento parabolico, se continuerà in questo modo si attenderebbe un risultato di secondo grado; e, osservazione più

importante, l’incremento di ciascuna colonna rispetto alla precedente è costituito da tutte e sole borse che contengono esattamente una pera.

Questa proprietà si dimostra immediatamente. Aggiungendo una pera ad una qualsiasi “borsa

valida” (d’ora in poi bv) contenente N frutti si ottiene una bv contenente più di una pera e N+1 frutti, e viceversa, togliendo una pera da una bv con N+1 frutti e più di una pera, si ottiene una bv con N frutti.

Indicando con QN il numero di bv con N frutti, con TN il numero di borse con sole arance, mele e banane che rispettano le relative regole e con DN la quantità di borse che si possono formare con N fra mele (in numero pari) e banane (il cui numero sia multiplo di 5); il numero delle Qi₊₁ che contengono una sola mela sarà uguale a Ti e avremo:

Qi₊₁=₊Qi₊₁+ Q1 i+1=Qi+Ti → Qi₊₁−Qi =Ti [1]

Ma sarà anche, visto che le arance possono essere solo 0, 1, 2, 3 o 4:

Ti=Di+Di₋₁+Di₋₂+Di₋₃+Di₋₄ ed analogamente

Ti₋₁=Di₋₁+Di₋₂+Di₋₃+Di₋₄+Di₋₅ che sottratte membro a membro danno

Ti−Ti₋₁=Di−Di₋₅ [2]

Formula che risulta corretta anche quando i è minore di 5 ponendo le D con indice negativo uguali a zero.

Per calcolare la differenza a secondo membro si può usare l’orologio disegnato a fianco, dove i numeri interni (da 0 a 9) sono i valori di i, nei cerchietti sono inserite le quantità di mele e banane che possiamo mettere in borsa e all’esterno viene indicata la differenza Di – Di₋₅ relativa.

I valori di Di non sono stati scritti, ma basta contare quante coppie sono presenti nei cerchietti, e non sono tante! Tenendo conto che aumentando i di 10 si aggiunge una nuova coppia valida: per i=11 [6,5] e per i=13 [8,5], mentre per le altre basta aggiungere 10 mele alle coppie già presenti e ancora 10 banane a quella che ne contiene di più, sarà:

Sorprendentemente semplice risulta il valore della differenza Di – Di₋₅ , per trovarlo basta eseguire la sottrazione (sull’orologio i punti occupano posizioni diametralmente opposte) ricordando, però, di aggiungere uno se nell’andare da i-5 ad i si passi, come nel monopoli dal via. La differenza vale sempre 1 quando i è pari e 0 quando è dispari. La [2] si semplifica in:

Ti−Ti₋₁ = (i+1)mod 2 [2’]

Grazie alle [1] e [2’], che possono essere lette, sia come relazioni ricorsive, sia come differenze finite, il calcolo di QN diventa un gioco a partire da T₀=1 ( [0,0,0] ) e Q₀=0 (ogni borsa deve contenere almeno una pera)

Dove i termini della seconda e terza riga sono ottenuti sommando al valore precedente la differenza posta nella riga sopra. E immediato notare che nella seconda riga compare la successione dei naturali (tranne lo 0) ripetuti due volte.

Dimostrazione formale (a mio avviso non necessaria).

Dalla [2’] con T₀=1 abbiamo:

Si arriva poi al risultato della terza riga con le medesime dimostrazioni della prima soluzione.

Confronto fra i due procedimenti.

Beh! Sicuramente il secondo, come gli altri che si possono pensare abbinando diversamente i frutti, è sicuramente più oneroso e, per me, difficile da spiegare con chiarezza. Non è però privo di pregi: vogliamo mettere la meraviglia di arrivare ad un risultato così semplice, dopo un percorso tormentato?

Limitare il valore di N.

Direi risulti impossibile limitare il valore di N, se non specificando la capienza della borsa o limitando superiormente la quantità di ciascun tipo di frutta. Anche una sola specie non limitata porterebbe ad un insieme numerabile di valori di N.

Si potrebbe addirittura abbinare la quantità di un tipo di frutta a qualche insieme numerico la cui potenza finita sia ad oggi solo una congettura.

Complicare il problema non è difficile, la semplicità dei risultati è sostanzialmente legata al completamento dei valori fra arance e banane, qui è stato usato il 5, ma qualsiasi altro numero maggiore di 1 porterebbe al medesimo risultato.

Una piccolissima semplificazione dei risultati (eliminazione di molti +1 che compaiono nelle formule) si otterrebbe chiedendo alle pere di essere almeno due. Questo eviterebbe anche la decapitazione dei quadrati, che inizierebbero da 0 e non da 1.

E qui ci fermiamo, complimenti a tutti. Alla prossima!

5. Quick & Dirty

Trovato “al volo”, passato al volo, nella più pura tradizione dei Q&D. Facile, ma molto bello.

La somma delle circonferenze della serie infinita di cerchi in figura è finita o infinita?

6. Pagina 46

Se , si ricava immediatamente la soluzione

.

Di converso, se p divide uno dei due numeri x o y, allora divide anche l’altro e ci si può ricondurre ad una soluzione in cui p non ne divide nessuno dei due; inoltre, in questo caso x e y vengono ad essere primi tra loro, in quanto il loro fattore comune dovrebbe dividere pn.

La fattorizzazione:

,

apre due possibilità.

Se , allora si ha , , .

Se, invece, è una potenza di p come , allora si ha:

,

ossia p divide e . Le uniche soluzioni per cui p non divide x e y devono quindi essere cercate per , con potenza di 3.

Se , visto che 9 non divide , non dividerà neppure , che deve allora valere 3.

contraddice , e la sola soluzione in questo caso è , o e .

Da queste due soluzioni con x e y non multipli di p:

, ,

si deducono le altre due famiglie di soluzioni:

e .

Quindi, le richieste coppie sono unicamente e .

7. Paraphernalia Mathematica

Tranquilli, la serie “Oltre Platone” continuerà. Ma di recente ho (Rudy speaking) avuto modo di ripensare ad un aneddoto relativo allo scorso millennio, precedente la nascita di RM. E il trovare, tre giorni dopo, una serie di interessanti notizie vagamente correlate, ha dato la stura ai ricordi. Se dell’aneddoto non ve ne importa niente (pienamente giustificati, nel caso), saltate al titolo.

Stiamo parlando del 1996: il Vostro Eroe lavorava in una startup circondato da americani espatriati (costretti a sopportare il suo pessimo inglese) che, nella previsione di restare in Italia un paio d’anni, avevano acquistato una serie di generi (elettrici & elettronici) di prima necessità. E ora era il momento di andarsene, e tutti gli elettrodomestici diventavano inutili.

I più attaccati alla vile pecunia organizzavano delle aste; i più generosi li regalavano, chiedendo “a chi interessa...”: il che suscitava di solito una sequenza di “Io, io!”, con successivi litigi tra colleghi.

Mike, il mio boss (‘miricano, quindi “boss”) dell’epoca era convinto di aver trovato un modo più “onesto” per organizzare il saccheggio di casa sua: visto che sua moglie (negli U.S.A.) lavorava all’ufficio immigrazione, si era procurato uno di quei questionari sulla “cultura generale americana” ed era passato a interrogare gli astanti: ad ogni risposta corretta, si aveva il diritto di mettere un proprio biglietto da visita (le famigerate business card) in un sacchetto[11].

Indi, con tutti gli oggetti esposti, si procedeva all’estrazione di un biglietto, e l’estratto poteva scegliere un oggetto tra quelli esposti, e avanti così; ma dal secondo estratto in avanti, questo poteva “rubare” un oggetto ad un collega (a meno che il collega lo avesse appena “rubato” al secondo estratto), e il derubato poteva scegliere un oggetto tra quelli non ancora assegnati (no, non poteva “rubare”, neanche ad un altro dal “suo ladro”): avanti così sino ad esaurimento dei biglietti.

Risultato: un ferro da stiro con asse, una macchina per il caffè americano, un rasoio elettrico, un radioriproduttore CD&cassetta formato ghetto blaster e otto CD di musica country. Praticamente tutto il bottino, grazie ad alcuni Presidenti assolutamente sconosciuti.

Divertente, e anche ragionevolmente “onesto”. Ma di recente sono nate alcune idee che fanno pensare a metodi che rovinano meno amicizie.

7.1 Libera nos a malo

Dove il “malus”, qui è l’invidia per la scelta fatta dal vostro vicino di scrivania, che quello lo volevate voi. E non è sbagliato tirare in ballo il latino, anzi dovremmo andare ancora più indietro: infatti, il metodo “io taglio, tu scegli” (che è molto onesto e che da anni attribuiamo erroneamente a Newton) lo trovate in Genesi, 13:5-13, quando Abramo e Lot si dividono la terra.

Supponiamo però di essere in una situazione del tipo di quella della “lotteria” dell’introduzione, ossia di avere un insieme di beni, ciascuno dei quali indivisibile (non fate i pignoli: i CD erano in cofanetto) e diversi tra loro da dividere tra due persone, riducendo l’invidia al minimo: se volete un esempio sensato diverso da quello della lotteria di Mike, sono rimasti un certo numero di pasticcini tutti diversi dalla vostra festa di compleanno [Auguri, Treccia! NdR], e adesso, rimasti soli con il gatto[12] e la casa da pulire, dovete dividervi i resti della festa. E, siccome i gatti mordono (soprattutto mentre dormite), meglio fare una divisione “senza invidia”, che altrimenti Micione si arrabbia e l’alluce sporgente dal piumone potrebbe soffrirne.

Per mettere la cosa in un ambito più formale, supponiamo di avere due giocatori, A e B, che devono dividersi un insieme di oggetti, ciascuno dei quali indivisibile, in modo tale che ogni giocatore riceva lo stesso numero di oggetti e che alla fine ciascuno sia soddisfatto: inoltre, supponiamo che i due giocatori siano in grado di ordinare strettamente gli oggetti in palio; quello che ci chiediamo, in prima istanza, è se sia possibile ottenere un’allocazione libera da invidia degli oggetti.

Restando molto poco sul formale, possiamo trovare facilmente dei casi nei quali la cosa è possibile: se abbiamo gli oggetti {1,2,3,4,5,6} e i due ordinamenti {1,2,3,6,5,4} e {4,5,6,3,2,1} è evidente che il primo giocatore se ne andrà con {1,2,3} e il secondo con {4,5,6}, entrambi saranno contentissimi e nessuno sarà invidioso dell’altro. Ma se volessimo essere più formali, potremmo caratterizzare in modo più generale la caratteristica di una partizione di essere libera da invidia?

(S)Fortunatamente, la cosa è possibile, anche se a prima vista la cosa sembra complicata. Infatti, per non perdere in generalità, come sempre ci si abbandona ad ampi voli pindarici. Diamo la definizione in rientrato, poi cerchiamo di spiegarla.

Siano e i due insiemi di oggetti ricevuti rispettivamente da A e B, con . Un’allocazione è definita libera da invidia se esistono due omomorfismi iniettivi e tali che per qualsiasi elemento x ricevuto da A, A preferisca x a e per qualsiasi elemento y ricevuto da B, B preferisca y a .

Adesso cerchiamo di chiarirci le idee: in pratica, stiamo dicendo che le “funzioni di scelta” devono spaziare univocamente su tutto l’insieme ed essere a valore unico (“omomorfismo iniettivo”); non solo, ma tutta la parte finale serve solo a dire che i due giocatori parimenti preferiscono quanto ricevono in un’allocazione rispetto a quanto riceve l’altro.

Poco chiaro? Forse possiamo salvarci con un esempio.

Supponiamo, dall’insieme dato, le scelte ordinate dei due giocatori siano:

Le due allocazioni {1, 3, 5} per A e {2, 4, 6} per B sono libere da invidia, come si dimostra mappando uno a uno l’ordinamento secondo A sull’ordinamento di B e viceversa: infatti, abbiamo:

Di solito, si semplifica questa notazione indicandola come:

Va enfatizzato il fatto che ogni giocatore parimenti preferisce il proprio oggetto a quello corrispondente dell’altro giocatore: ad esempio, A riceve l’oggetto 3, che preferisce rispetto a , ma A non preferisce l’oggetto 3 all’oggetto 2, che è un oggetto ricevuto da B. Rispetto a 2, però, A preferisce 1, e lo riceve, quindi 2 può andare a B[13].

Per restare nello stesso esempio, le allocazioni {1, 2, 3} per A e {4, 5, 6} per B non sono libere da invidia: la cosa si verifica esaustivamente verificando tutte le possibili mappature da {1, 2, 3} a {4, 5, 6} e viceversa, mostrando che nessuna di esse ha la proprietà richiesta.

Quando leggiamo “verifica esaustiva”, a molti di noi tende a spegnersi il neurone, visto che ci rimane sempre il dubbio di averne dimenticata una per strada: fortunatamente, ci viene in aiuto un simpatico lemma (dimostrabile, ma sorvoliamo):

Un’allocazione è libera da invidia se e solo se per ogni oggetto x ricevuto da A, il numero degli oggetti ricevuti da B che A preferisce a x è non maggiore del numero degli oggetti ricevuti da A che A preferisce a x[14].

E viceversa (nel senso che sostituite A a B e B ad A), chiaro.

Esiste anche una formulazione molto più sbrigativa:

Se un’allocazione è libera da invidia, allora ogni volta un giocatore riceve un oggetto x, deve anche ricevere almeno la metà degli oggetti che lui preferisce strettamente a x.

Quindi, se tutti gli oggetti sono stati allocati, se un giocatore ha ricevuto l’oggetto x che lui valuta al k-esimo posto, allora dovrà aver ricevuto anche almeno oggetti che lui preferisce a x.

Proviamo ad applicarla, esaminando l’allocazione {1, 2, 3} per A e {4, 5, 6} per B vista sopra, con le preferenze indicate: per A la distribuzione è sicuramente libera da invidia, visto che riceve i tre oggetti che valuta di più, e quindi non può preferire nessun oggetto ricevuto da B; ma per B?

Qui la situazione è ben diversa, come si vede applicando il lemma visto sopra: infatti riceve 5, che valuta al sesto posto, e preferisce solo due (il 4 e il 6) degli oggetti che riceve al 5. La divisione quindi non può essere libera da invidia per B in quanto preferisce più oggetti nel sottoinsieme di A (tre: 1, 2, 3) all’oggetto 5 rispetto a quelli che preferisce (sempre rispetto al 5) nel proprio sottoinsieme (due: 4, 6). Come “regola a spanne”, possiamo dire che in ogni divisione libera da invidia ognuno dei due deve ricevere l’oggetto preferito e nessuno deve ricevere l’oggetto meno apprezzato[15].

Trovare una divisione ibera da invidia non sembra semplicissimo, ma almeno un punto fermo esiste: siccome dividiamo tra due persone, il numero totale degli oggetti dovrà essere pari.

Ci pare importante sottolineare che la teoria che si sta sviluppando cerca di lavorare non solo sulla totalità dell’insieme di scelta, ma anche sui sottoinsiemi (ordinati) di un certo numero di preferenze: prendiamo ad esempio quella che è nota come condizione C(k): si dice che le valutazioni di A e B soddisfano la condizione C(k) se e solo se l’insieme dei k oggetti preferiti da A è uguale all’insieme dei k oggetti preferiti da B.

E qui, diventa importante il concetto di insieme: infatti, non stiamo dicendo che le valutazioni debbano essere uguali, ma che debbano essere uguali i due insiemi (ad esempio, {1, 2, 3} e {2, 3, 1}, pur essendo diverse, soddisfano la condizione).

Senza stare a fare troppi ragionamenti, viene fuori un concetto piuttosto interessante: risulta critico, infatti, il riuscire a determinare se la C(k) è vera quando k è dispari: se guardate all’esempio precedente, vi accorgete che non è mai soddisfatta:

Da questo, si ricava un’ulteriore condizione, la cosiddetta condizione D: la condizione C(k) è falsa per ogni valore dispari di k, .

Può avervi lasciati perplessi il fatto che abbiamo definito, qui sopra, delle allocazioni libere da invidia che sono dei sottoinsiemi dell’insieme totale: ci si chiede a cosa possa servire una allocazione che rende tutti felici solo sin quando non si distribuiscono gli ultimi pezzi, ma in questo modo si riesce a fare i conti: per distinguere i casi, si introduce una definizione:

Un’allocazione libera da invidia si dice completa (o completamente libera da invidia) se e solo se alloca tutti gli oggetti.

E capite che se non vogliamo litigare alla fine, a noi interessano queste. Per fortuna esiste un teorema in merito:

Sia n pari. Un’allocazione è completamente libera da invidia se e solo se soddisfa la condizione D.

Forniti di questo armamentario, possiamo provare a costruire qualche algoritmo di allocazione completamente libero da invidia.

Il primo, noto come algoritmo BT, prende il nome da Steven Brahms e Alan Taylor, che lo hanno proposto per primi: è di una semplicità disarmante:

Ognuno dei due giocatori sceglie il suo oggetto preferito tra quelli non ancora allocati.

Se gli oggetti nominati sono diversi, ciascuno riceve l’oggetto che ha scelto, se hanno scelto lo stesso oggetto questo va nella pila delle contestazioni.

Se tutti gli oggetti sono stati allocati o sono stati contestati, ferma. Altrimenti, torna al passo 1.

Leggiamo nei vostri occhi una profonda delusione: “Ma come, restano degli oggetti non allocati?” Certo. Sono quelli che suscitano invidia.

Ammettiamo che il metodo non è esattamente una meraviglia: proviamo con un altro? Questo è noto come algoritmo AL, ma non siamo riusciti a scoprire di chi siano le iniziali:

Se non è ancora stato assegnato nessun oggetto e entrambi i giocatori preferiscono lo stesso oggetto non ancora allocato, questo viene posto nella pila delle contestazioni e si ricomincia da (1).

Quando è stata effettuata la prima allocazione, si passa alle allocazioni successive se:

i due giocatori preferiscono oggetti diversi, oppure:

i due giocatori preferiscono lo stesso oggetto, ma l’assegnazione (dell’oggetto preferito a un giocatore e di un oggetto meno preferito all’altro) non causa invidia ed è quindi fattibile.

Quindi ogni volta che l’oggetto preferito è comune si verifica se è fattibile, senza invidia, l’allocazione dell’oggetto ad uno dei due giocatori: solo se questo non è possibile l’oggetto va nella pila delle contestazioni.

Forse, una volta tanto, la formalità aiuta.

Fase 0: Confrontate gli oggetti preferiti non allocati: se sono uguali, metteteli nella pila delle contestazioni e ripetete la Fase 0. Se sono diversi, assegnate ad ogni giocatore l’oggetto preferito e passate alla fase t=1.

Fase t: Effettuate nell’ordine i seguenti passi:

Se resta un solo oggetto non allocato, mettetelo nella pila delle contestazioni e fermatevi. Se non restano oggetti non allocati, fermatevi. In caso contrario, confrontate gli oggetti preferiti da A e B:

Se sono uguali, andate al passo 2.

Se sono diversi, assegnate ad ogni giocatore l’oggetto preferito e passate alla fase t=t+1.

Determinate se l’oggetto preferito sia da A che da B (sia i, che chiameremo oggetto conteso) può essere attribuito come segue. Sia la sequenza degli oggetti non allocati che A ritiene meno preferibili di i, e la sequenza degli oggetti non allocati che B ritiene meno preferibili a i.

Considerate tutti i possibili assegnamenti di i a B e di in prima istanza, in seconda istanza, eccetera, ad A: definiamo questa allocazione come fattibile sin quando il numero degli oggetti (assegnati a B o non assegnati) incluso i che A preferisce come oggetto di compensazione o eccetera, è al più t. Questa fase t+1 deve essere implementata per ogni assegnamento fattibile di i a B. Se il numero degli oggetti assegnati a B o non assegnati che A preferisce a i è maggiore di t, allora nessun assegnamento di i a B è fattibile.

Considerate tutti i possibili assegnamenti di i ad A e di in prima istanza, in seconda istanza, eccetera, a B: questa allocazione è fattibile sin quando il numero degli oggetti (assegnati a A o non assegnati) incluso i che B preferisce come oggetto di compensazione o eccetera, è al più t. Questa fase t+1 deve essere implementata per ogni assegnamento fattibile di i ad A. Se il numero degli oggetti assegnati ad A o non assegnati che B preferisce a i è maggiore di t, allora nessun assegnamento di i ad A è fattibile.

Se l’assegnamento di i ad A non è fattibile e l’assegnamento di i a B non è fattibile, allora i va nella pila di contestazione e si ripete la fase t per gli oggetti non allocati restanti.

Si noti che mentre BT fornisce una sola allocazione libera da invidia, AL ne fornisce diverse, ma la fatica è tutta dell’arbitro: A e B devono limitarsi a fornire la loro graduatoria degli oggetti.

Meglio provare con qualche esempio, sì?

Supponiamo una scala di preferenza di questo tipo:

E proviamo con BT: al primo giro, A prende 1 e B prende 2, e siamo ancora liberi da invidia: al secondo giro, però, sia A che B scelgono 3 (A non può scegliere 2 in quanto già preso da B: attenzione che non c’è invidia, visto che A si è accaparrato 1), e quindi finisce nella pila di contestazione. Al terzo giro, succede la stessa cosa, in quanto entrambi vorrebbero 4, che finisce anche lui in pila di contestazione e non viene diviso. Quindi il risultato finale è:

Proviamo adesso con l’algoritmo AL: in fase 0, attribuiamo 1 ad A e 2 a B; quindi, passiamo alla fase . Degli oggetti non allocati, entrambi i giocatori preferiscono , che diventa quindi l’oggetto conteso. Per A esiste un oggetto meno allettante di 3, quindi : potremmo consegnare i a B e ad A, ma in questo caso avremmo assegnato a B due oggetti (2 e 3) che A preferisce a 4, mentre al massimo potremmo assegnargliene : quindi così non è fattibile.

Vediamo la cosa dall’altra parte: se allochiamo ad A, abbiamo che andrebbe assegnato a B: e questo assegnamento è fattibile, in quanto siamo nel caso e B preferisce solamente un oggetto a 3 tra quelli allocati ad A (trattasi di 1). In fin della fiera:

Morale della favola: se siete l’arbitro scegliete BT (poco lavoro e grosso ricavo), se siete parte in causa scegliete AL.

Vediamo se avete capito: provate entrambi i metodi con:

Se avete fatto i conti giusti, con BT dovreste ottenere:

Mentre, con l’algoritmo AL ottenete:

Insomma, tutto diverso! Ma la cosa si conclude senza invidia (mah, dipende... l’arbitro preferiva il 4 o il 3?).

Come al solito, visto che viviamo in una valle di lacrime, il metodo migliore è il più complicato: esistono un paio di teoremi, infatti, piuttosto tranchant:

Il numero degli oggetti allocati secondo AL non è mai minore e può essere maggiore di quelli allocati secondo BT. Se il numero degli oggetti allocati dai due algoritmi è uguale, allora l’allocazione secondo AL è Pareto-dominante[16] rispetto all’allocazione secondo BT.

E, per mettere l’ultimo cerchio alla botte:

L’allocazione AL massimizza l’assenza di invidia.

Per chiudere con lo stesso aneddoto dell’inizio, spiegheremmo volentieri l’intero metodo a Mike, ma l’ultimo giorno ha lasciato sulla scrivania un biglietto con scritto “Gone Fishing”.

Il biglietto è ancora lì.

[1] Si era conclusa da pochi anni la “seconda guerra dell’oppio”, che ebbe proprio a Canton il suo epicentro. La florida e civile Gran Bretagna aveva scatenato un conflitto per poter continuare ad importare in Cina l’oppio coltivato in India.

[2] Cronache danesi e tedesche. Nei paesi latini, già il termine “pestis” era sinonimo di “morte” e quindi i termini “peste” e “morte” erano di fatto sovrapponibili. Nel 1832, il termine fu ripreso da Justus Friedrich Karl Hecker in un suo articolo che ebbe molta risonanza, e l’espressione tedesca “Schwarzer Tod” e quella corrispondente inglese “Black Death” presero piede. In latino e in volgare, “pestis atra”, che era uno dei modi con i quali ci si riferiva alla pandemia, è più o meno lecitamente traducibile come “peste nera”, “peste atroce” o anche direttamente come “morte atroce”.

[3] Detta anche LIA, dall’acronimo inglese Little Ice Age.

[4] Anche sulla dimensione “globale” del raffreddamento esistono opinioni diverse da parte degli studiosi.

[5] “Decameron” significa proprio “dieci giorni”, in greco. In realtà, l’estensione narrativa ne copre però quattrodici, anche se quattro di questi non sono dedicati al racconto delle novelle.

[6] “Boccaccesco”=1. Proprio dello scrittore fiorentino Giovanni Boccaccio. 2. Salace, licenzioso. (sia il Sabatini-Coletti che il Dizionario Hoepli concordano alla lettera). È quasi inevitabile notare che il titolo di quest’articolo (che ricalca l’espressione “dire peste e corna di qualcuno”, della quale non siamo riusciti a risalire le origini) potrebbe funzionare come una “crittografia mnemonica” che abbia per soluzione proprio “Decameron”.

[7] Tanto per fare un esempio a caso: non ci è ancora chiaro se lo splendido sezionamento di un quadrato in un triangolo equilatero in 4 pezzi (quello che ha generato il fantastico tavolo di RM costruito da Sawdust, per intenderci) sia da attribuire a Loyd, come credevamo, o a Dudeney, come riportano molte fonti (tra cui Wikipedia inglese) con il nome di “the Haberdasher’s Puzzle”.

[8] Questa parola è presente unicamente per evitare traumi alle piante. “Quali piante?” “Quelle della frase dopo”.

[9] No, non li so a memoria. Mi hanno detto che era l’anniversario e sono andato a cercare le altre date.

[10] Ovviamente non ho neanche la certezza che la formula sia quella giusta e che non ci siano differenze per N>40, però una nota su OEIS mi fa propendere perché la formula sia quella cercata da Carlo: si dice che “This also counts the number of ways to make change for "c" cents using only pennies, nickels and dimes. You must first set n=floor(c/5), to account for the 5-repetitive nature of the task”. Non riesco a vedere il nesso diretto ma i pennies sono le monete da 1c, i nickel da 5c e i dime da 10c, i due problemi quindi si somigliano moltissimo (ma chi sono le arance?).

[11] Con alcune eccezioni, ad esempio la domanda “nomina cinque Presidenti degli Stati Uniti”: alla fine degli interrogatori, oltre al biglietto che vi spettava se ne avevate nominati cinque, potevate mettere tanti biglietti quanti erano stati i “vostri” Presidenti non nominati da altri. VanBuren, McKinley, Garfield, Monroe, Jefferson: secondo voi, quanti biglietti ho messo, alla fine?

[12] Niente auguri a Virgilio: lui, è un “gat ‘d San Gioan” (fine giugno – San Giovanni Battista è il 24 –, nato dal secondo estro della gatta. Dovrebbero essere piccoli, ma ormai è il classico caso di “...per semplicità, consideriamo un gatto perfettamente sferico...”. NdRdA

[13] Si noti che qui le due funzioni sono una l’inverso dell’altra, ma la cosa non è necessaria.

[14] Se questo aggeggio vi ricorda il Torema di Hall (o “del matrimonio”), avete perfettamente ragione. Sono alcuni anni che dobbiamo scrivere il PM relativo, non è che volete farlo voi?

[15] Notiamo anche che nel caso particolare B riceve 4, che è il secondo oggetto più quotato da lui, ma non ne riceve nessuno che preferisca al 4 (in quanto il 2, che lui valuta come primo, è dato ad A).

[16] ...e se non sapete cosa vuol dire, compratevi un libro!