Rudi Mathematici

Rivista fondata nell’altro millennio

Numero 215 – Dicembre 2016 – Anno Diciottesimo

Tra i redattori (ossia, tra gli unici costretti a leggerlo), qualcuno si è chiesto come mai non avessimo inserito altre spirolatere nel PM del mese scorso. Semplicemente, ci parevano molto più adatte al Natale.

1.    Il giro del mondo nei nostri giorni

Miei cari ascoltatori, a stare a sentire certi cervelli limitati (mai aggettivo è stato più adatto), l’umanità sarebbe rinchiusa in un cerchio di Popilio che mai essa riuscirebbe a superare, essendo condannata a vegetare su questo globo senza alcuna speranza di slanciarsi un giorno negli spazi planetari! Sciocchezze! Si andrà sulla Luna e poi sui pianeti e sulle stelle come oggi si va da Liverpool a New York, facilmente, rapidamente, sicuramente, e l’oceano atmosferico sarà tra breve attraversato come gli oceani terrestri. La distanza non è che una parola relativa, e finirà per essere ridotta a zero.

 (da Dalla Terra alla Luna, Giulio Verne)

Il viaggio non finisce mai. Solo i viaggiatori finiscono. E anche loro possono prolungarsi in memoria, in ricordo, in narrazione. Quando il viaggiatore si è seduto sulla sabbia della spiaggia e ha detto: “Non c’è altro da vedere”, sapeva che non era vero. La fine di un viaggio è solo l’inizio di un altro.

 (José Saramago)

Avete mai notato quanti articoli passati per questa rubrica parlano di geografia[1]?

Spesso parliamo di posti che hanno cambiato nome e nazione molte volte e generato casi strani, altrimenti di fiumi che attraversano interi continenti e trasportano notizie e cultura, o ancora montagne che separano mondi e dimensioni. Una passione, quella della geografia, che ha a che fare con la topologia, la cartografia e tanti altri nostri tormentoni, ma soprattutto è un po’ un indizio della nostra curiosità, perché esisteranno sempre posti che non potremo vedere con i nostri occhi, ma attraverso queste pagine ci è permesso visitare.

Il giro del mondo in 80 giorni nella giusta prospettiva.

E chi non ha mai pensato di infilarsi nel taschino di Passepartout e seguire il signor Fogg intorno al mondo, cavalcando elefanti, volando in mongolfiera, attraversando giungle e salvando principesse? Persino il grande Giulio Verne descrisse le più incredibili avventure senza muoversi di casa e chi siamo noi per non approfittare delle possibilità di questi mirabili tempi moderni, quando tutto il mondo gira al click del nostro mouse, un giretto della rondellina permette di avvicinarsi ed allontanarsi, e continuare ad attraversare oceani e visitare ogni angolo del mondo.

Dalla Terra alla Luna

Le nuove tecnologie permettono un nuovo modo di viaggiare, ma non sono esattamente quello che si può fare entrando un universo immaginario in cui ogni attraversamento è un’avventura, inattesi colpi di scena ci aspettano ad ogni incontro. Però le nostre pagine parlano di matematica, e così tante sorprese non sono da aspettarsi… ma è poi vero? Non c’è un solo matematico di cui abbiamo parlato che non ci abbia sorpreso a modo suo, che non abbia mostrato aspetti inattesi e fuori luogo, non c’è uomo o donna che non sia stato, prima di tutto, uomo o donna, e poi scienziato.

La Prestigiosa Rivista di Matematica Ricreativa che state sfogliando ha un fiore all’occhiello: la voglia e la capacità di stupirsi ogni volta che scopriamo qualcosa di nuovo. E così, come ogni mese, ci siamo avventurati alla ricerca di un protagonista opportuno per il compleanno di dicembre, che ancora una volta – purtroppo per i nostri lettori – è nelle mani di Alice. La prima selezione è facile: un personaggio nato a dicembre, matematico, possibilmente poco noto (altrimenti chiunque ne sa più della sottoscritta), ma dalla vita interessante e che possa in qualche modo permetterci di parlare d’altro. Per questo parliamo di un rappresentante di un’impresa di zucchero in Russia, nei primi anni del millenovecento.

Da Samara a Harbin.

Il posto da cui abbiamo deciso di partire si chiamava Samara. Una di quelle città che hanno cambiato nome più di una volta, caso non particolarmente straordinario nella Russia del periodo: nel 1935 e fino al 1991 si è chiamata Kuybyshev, ma nel momento in cui la lasciamo per la prima tappa del nostro viaggio non aveva ancora perso il nome che gli deriva certamente dalla sua posizione alla confluenza del Volga con il fiume Samara. Era una città già a suo tempo molto grande e sede di molte industrie, ma il nostro Motvey Trotsky, con la moglie Nadejda e la quattrenne Emma non esita a trasferirsi ad Harbin, in Manciuria. È il 1910, e Harbin, che una decina di anni prima quasi non esisteva sulla carta geografica, è il centro delle intense relazioni tra Russia Cina e Giappone: il governo russo aveva ottenuto di usarla come stazione cruciale della ferrovia transiberiana, e commercianti ed industriali giungevano da ogni angolo della Russia per cercare il successo. Fiorivano i consolati e da ogni nazione[2] accorrevano imprenditori e – con i cambiamenti che si succedevano dopo la rivoluzione russa del ‘17 e l’indebolimento del potere russo sulla zona, sempre più immigrati da tutto il mondo.

Non si può immaginare un posto migliore e più internazionale per crescere una figlia, dove è possibile ottenere già un’ottima educazione. E la figlia di cui stiamo parlando era particolarmente brillante, e le fu presto chiaro che per considerare un futuro per i suoi studi, la direzione migliore a quel punto sarebbero stati gli Stati Uniti.

Mentre un viaggio del genere viene indicato oggi come abbastanza semplice (per quanto un volo da più di 15 ore non è esattamente una passeggiata), a suo tempo (siamo ormai nel 1924) un posto all’università di Berkeley non assicurava il passaggio: la nostra eroina cominciò con il passare in Giappone (Harbin era sotto controllo giapponese a questo punto), poi in Canada, e dal Canada dovette aspettare parecchi mesi per ottenere il visto di ingresso.

Da Harbin a Berkeley.

Emma è però molto in gamba, e si era iscritta ad ingegneria: malgrado arrivi a sessioni iniziate si riporta presto in corsa, anche se – cosa che non dovrebbe stupire il lettore di una Prestigiosa Rivista – si rende presto conto che l’ingegneria non le è particolarmente congeniale[3] e decide di passare alla facoltà di matematica.

Derrick Norman Lehmer

Qui il professore che più sviluppò il suo interesse era Derrick Norman Lehmer (27 luglio 1867, Somerset, Indiana – 8 settembre 1938, Berkeley, California), con il quale collaborò anche per diversi progetti di ricerca. Era un professore che adorava insegnare, affascinato dalla teoria dei numeri e dalle possibilità di computare tavole di calcolo. Ma era anche un poeta e un letterato, e l’elenco delle sue onorificenze contiene allori in entrambe le discipline.

Veniva da una famiglia che discendeva da pionieri della Pennsylvania, e cominciando la sua carriera in Nebrasca, era infine approdato a Berkeley, dove aveva scoperto le gioie dell’insegnamento ed aveva fondato una bella famiglia: dei suoi cinque bambini, uno divenne a sua volta un prominente matematico.

Derrick Henry Lehmer

Derrick Henry Lehmer (23 febbraio 1905 – 22 maggio 1991, Berkeley, California), il matematico figlio, era chiamato da tutti Dick, cosa che probabilmente aiutava a distinguerlo dal padre (detto DNL), con il quale collaborava volentieri, e grazie al quale probabilmente conobbe Emma.

L’interesse che lo accomunava al padre era la costruzione di macchine che permettessero di effettuare calcoli complessi, e subito dopo la propria laurea (a Berkeley nel ‘27) si era trasferito a Chicago per ottenere il dottorato, ma non era felicissimo, e probabilmente conoscere Emma spostò il suo asse dei desideri: non appena lei ottenne la laurea nel ‘28 si sposarono e si misero in viaggio.

A parte visitare il parco di Redwood (in California, non troppo distante), finirono con arrivare in Giappone, a conoscere i genitori di Emma.

Emma Markovna Trotskaia Lehmer.

Emma Markovna Trotskaia Lehmer, nata il 6 novembre[4] 1906 a Samara, in Russia, aveva a questo punto già girato mezzo mondo, ma non era ancora arrivata.

Sì, perché malgrado le ottime pubblicazioni già uscite e la laurea nella prestigiosa università californiana, né lei né suo marito potevano ancora ambire ad una cattedra, senza aver ottenuto un dottorato.

Entrambi fanno quindi domanda per un dottorato all’università Brown, in Massachusetts, dove cercarono insieme di contribuire alle finanze di famiglia e allo stesso tempo scrivere le rispettive tesi, Emma dando lezioni e scrivendo note per Dick, che nel frattempo completava la sua dissertazione con Tamarkin.

Purtroppo erano i tempi della depressione, e non era affatto facile, non solo sbarcare il lunario, ma anche trovare posizioni decenti per brillanti matematici, in tempi in cui i matematici arrivavano da tutte le parti.

Da Berkeley al Massachusetts.

I nostri eroi cominciano così a girare da un posto all’altro.

Prima il California Institute of Technology poi Stanford, poi Institute for Advanced Study a Princeton, poi Lehigh University in Pennsylvania, dove finalmente Dick ebbe una posizione permanente.

Coast to coast.

Per tutto questo tempo ad Emma non fu mai permesso di insegnare, perché le regole del tempo impedivano a marito e moglie di insegnare nello stesso istituto. Così lei si limitò a lavorare a quello che più le interessava e a scrivere articoli e ricerche in collaborazione con il marito. E ovviamente a costruire la famiglia: i figli Laura e Donald nacquero in due posti diversi, e questa la dice tutta delle peregrinazioni della famiglia Lehmer.

Dagli Stati Uniti all’Inghilterra.

Lehigh fu un punto fermo per la famiglia per qualche anno, anche se nel frattempo i due fecero un lungo viaggio in Inghilterra per visitare le università di Cambridge e Manchester. Nella patria di Albione incontrarono, tra gli altri Hardy, Littlewood, Davenport, Mahler, Mordell e Erdős.

Emma continuava a non poter insegnare, ma ciò non significava che non fosse attivissima nella ricerca matematica.

Ad Aberdeen c’è il computer.

Nel 1945 i Lehmer sono al Aberdeen Proving Ground, dove l’ENIAC veniva sviluppato ed utilizzato per risolvere complessi problemi balistici, ma di notte e nei momenti in cui non serviva alla guerra, veniva usato dai nostri eroi per risolvere problemi. Secondo gli amici i due si procuravano una babysitter e andavano a passare la notte con il grande computer a provare uno dei loro crivelli, per tornare a casa all’alba soddisfatti.

Emma era quasi contenta di non poter insegnare, perché così poteva dedicare più tempo alla ricerca: negli anni produsse più di 60 pubblicazioni di rilievo, di cui una ventina in collaborazione con il marito ed il suocero.

Alla fine i nostri riuscirono a tornare a Berkeley. Era il posto in cui Dick e NHL avevano fatto le loro prime scoperte con il calcolatore, dove Dick ed Emma si erano conosciuti.

Dick e DNL.

L’avventura non era finita, ma il viaggio aveva raggiunto una conclusione, una destinazione. Malgrado gli anni difficili non mancarono (durante la caccia alle streghe di McCarty Dick perse temporaneamente la posizione a Berkeley), la coppia di matematici trovò alla fine una base e continuò ad operare per molti anni e scoprire sempre più proprietà sulla teoria dei numeri, la loro passione dal primo momento.

La loro più grande creazione, alla fine, fu il convegno di teoria dei numeri più amato dagli specialisti del settore: il West Coast Number Theory Meeting si tiene ogni anno a dicembre[5], e raccoglie tutti i possibili teorici dei numeri da tutto il mondo sulla West Coast. La prima volta fu organizzata in modo informale nel 1967 da Dick ed Emma, e dal 1969 è un appuntamento annuale fisso, dove i giovani matematici possono presentare le nuove idee anche in modo informale. Più di sessant’anni di vita insieme e di amore per i numeri hanno prodotto un’eredità straordinaria, la possibilità di creare ancora più matematica, ancora più amanti dei numeri.

Dick e Emma Trotskaia Lehmer, primavera 1991.

2.    Problemi

2.1    Elezioni!

Nel senso che abbiamo deciso di eleggere aristocraticamente (v. dopo) un Responsabile di Redazione di RM.

All’uopo, abbiamo scelto (il “dopo” di cui sopra è qui) 20 tra i lettori di RM, noti per la loro preclara saggezza e ponderata maturità, e abbiamo inviato loro la scheda per votare[6]; Rudy si è particolarmente impuntato sul pretendere una votazione alla Borda, sotto la giustificazione che ai ballottaggi non si vota a favore, ma contro e, oltretutto, rispondono in pochi; quindi, si trattava di mettere i tre nomi nell’ordine di preferenza e reinviare la scheda: avremmo poi verificato noi eventuali fasi di ballottaggio attraverso l’ordine di preferenza.

Comunque, abbiamo i risultati.

Tanto per cominciare, ogni possibile combinazione di Rudy, Alice e Doc è presente tra le schede ricevute. Il che mostra che le posizioni sono variegate e che rispettiamo tutte le opinioni, almeno fin quando Rudy non ritrova la katana.

Inoltre, si è visto che 11 votanti preferiscono Alice a Doc (e quindi, 9 preferiscono Doc a Alice), mentre 12 persone preferiscono Rudy ad Alice: a quanto pare, Doc ha poche speranze, ma testardamete si mette contare le schede, e scopre velocemente che 14 persone preferiscono Doc a Rudy! Insomma, siamo caduti in pieno Paradosso di Condorcet.

Adesso, siccome qui trattiamo di matematica, non vi diciamo quante prime scelte ha ricevuto ognuno, ma ci limitiamo a dirvi che avete abbastanza dati per scoprirlo da soli.

2.2    “Quasi primavera”

Questo numero uscirà talmente in ritardo che c’è il rischio le giornate si stiano già di nuovo allungando. Quindi, ci pare adatto un problema di giardinaggio, nella speranza che a breve si ricominci a tirare con l’arco (visto che l’estate passata le nostre frecce non hanno mai visto il sole: no, non tiravamo in notturna), dato che i nostri problemi non si realizzano mai e quindi, ponendo un problema che occupa lo spazio di tiro, ci sono notevoli probabilità che lo spazio di tiro non venga occupato e quindi lo si occupi noi con tutti i parafernalia arcieristici e quindi....

No, basta. OK, stavamo cercando di tirare in lungo, ma solo perché il problema è brevissimo ma, a nostro giudizio, molto grazioso.

L’idea delle signore è di dividere l’appezzamento in una serie di quadrilateri convessi ABCD (si chiamano tutti uguale perché è il cognome), tutti diversi tra loro: successivamente, a due Baldi Matematici verrà dato l’incarico di trovare, per ogni quadrilatero, un punto P al suo interno tale che i triangoli ABP, BCP, CDP e DAP siano tutti di area uguale.

Quello che ci chiedevamo era se esisteva un modo per eliminare alla svelta quelli per cui questo non era possibile: insomma, esiste una condizione necessaria e sufficiente per l’esistenza del punto P?

Per ora le giardiniere stanno quadrangolando sulla carta, ma appena gela cominceranno ad avere fretta di (farci) scavare (aspettare il disgelo, a quanto pare, non è divertente): avete qualche idea, in merito?

3.    Bungee Jumpers

Sia Sn = {1, n, n², n³, ...}, con n intero strettamente maggiore di 1. Trovate il minimo valore di k = k(n) per cui esiste un numero che possa essere espresso come somma di k (eventualmente ripetuti) elementi di Sn in più di un modo, considerando le permutazioni come equivalenti.

La soluzione, a “Pagina 46”

4.    Soluzioni e Note

Dicembre, tardissimo.

Anche se non abbiamo avuto tempo di combinare niente noi, Adam ci ha mandato come da tradizione le foto delle torte presentate al MathJam. Ci ha anche promesso un resoconto, che pubblicheremo appena arriva, anche se non siamo nemmeno più sicuri di aver risposto alle sue belle mail.

Il Calendario non è ancora pronto, questa edizione di RM è così in ritardo che tra un po’ arriva nell’anno sbagliato. Ma vi vogliamo bene e vi facciamo tanti auguri, e procediamo.

4.1    [208]

4.1.1    Un problema di quelli “belli” [2]

È passato parecchio tempo da quando il problema è stato presentato:

Un poligono è iscritto in un cerchio ed è triangolato da un insieme di sue diagonali non intersecantesi. In ognuno dei triangoli risultanti è tracciato il cerchio inscritto. Mostrate che la somma dei raggi dei cerchi inscritti è indipendente dalla triangolazione.

Per la nostra tristezza, malgrado la bellezza del problema, avevamo pubblicato in RM209 solo la soluzione di Valter. Con nostra grande sorpresa e piacere ci ha scritto trentatre, che ha trovato un po’ di tempo per mettere in bella copia la sua soluzione.

Una triangolazione di un poligono di N vertici inscritto in un cerchio comprende N–3 diagonali che non si intersecano e N–2 triangoli, ognuno definito da tre vertici del poligono; tutti i triangoli sono quindi inscritti nello stesso cerchio.

Per un triangolo qualsiasi vale la seguente proprietà.

I). la somma dei raggi inscritto e circoscritto è uguale alla somma delle distanze del circocentro O dai lati.

Cioè in fig. 1

[1]

(nb. se il triangolo è ottuso in un vertice, cioè non contiene O, la distanza dal lato opposto va presa negativa).

Applichiamo questa proprietà al problema (fig, 2)

Indicando con 1,2, … N i vertici del poligono, con la distanza di O dal lato (o diagonale) pq, con (pqr) il triangolo di vertici pqr, con  il raggio del cerchio inscritto, si ha

- triangolo (123) :

- triangolo (134) :  e sommando alla precedente

  (notare che sparisce)

- triangolo (146) :  e sommando

  (sparisce) e così via.

Quindi per il poligono (123…N) la somma dei raggi inscritti negli N-2 triangoli, aumentata di N-2 volte il raggio circoscritto R, è uguale alla somma delle distanze di O dai lati del poligono. Nella somma delle distanze può comparire un termine negativo se O è esterno al poligono, ma la somma dei raggi è sempre indipendente dalle diagonali e quindi indipendente dalla particolare triangolazione.

In formula, se sono i raggi inscritti e sono le distanze di O dai lati del poligono

[2]

che è una estensione della [1].

La proprietà I.) è notevole e poco nota; l’ho trovata solo in un vecchio testo che la attribuisce a Carnot (1801). La si può ricavare in modo puramente geometrico, ma ne riporto una dimostrazione algebrica, più compatta.

Con i lati e gli angoli indicati nel solito modo, l’area S del triangolo e il raggio r inscritto sono (fig. 3)

,

- in funzione degli angoli i lati e le loro distanze da O sono

- da cui

- per valgono per prostaferesi le identità

a)  

b)  

dalla a) e per la formula di duplicazione

e per la b)

 , cioè la [1]

(nb. se il triangolo è ottuso, uno dei coseni e la relativa distanza sono negativi).

Incredibile, vero? Ci eravamo quasi dimenticati di un problema così bello. Grazie ancora al nostro trentatre e a lui anche tanti auguri sperando che tutti gli accidenti sanitari si siano riassorbiti.

4.2    [213]

Abbiamo salutato trentatre troppo presto, si è dato veramente da fare a controllare e risolvere i problemi dei mesi passati.

4.2.1    Un problema da trecento birre

Anche di questo problema avevamo solo la soluzione di Valter pubblicata il mese scorso:

Alberto, traccia otto rette, in modo tale che nessuna sia parallela ad una qualsiasi altra; vince tre birre per ogni triangolo equilatero e una birra per ogni triangolo isoscele; quante birre servono se riesce a massimizzare il numero di birre? Togliendo la limitazione delle otto linee, esiste una soluzione da 300 birre, ottima: quante linee occorrono?

Vediamo che cosa ci scrive trentatre:

Il problema ha ricevuto una unica soluzione da Valter che dice di “non essere riuscito a fare molto”, ma lo schema trovato è corretto, anche se valutato in modo impreciso.

Tre rette non parallele individuano un triangolo. Se spostiamo le rette parallelamente a se stesse, cambia la dimensione del triangolo, ma non la sua forma e il suo tipo. Conta quindi solo l’orientamento della retta, e gli schemi che si trasformano fra di loro in questo modo sono di fatto una unica soluzione. Un triangolo può essere “nascosto” se le tre rette passano per un punto; per evidenziare tutti i triangoli le rette vanno spostate in modo da avere solo incroci semplici.

In fig. 1 la soluzione originale di Valter con la numerazione delle 8 rette, in fig. 2 una trasformazione della stessa senza incroci multipli e triangoli nascosti.

I triangoli si possono leggere in fig. 2, ma è più semplice far passare tutte le rette per un unico punto come in fig. 3. Qui i triangoli sono tutti nascosti, ma il loro numero e tipo si ricava facilmente. Indichiamo con equ e iso i triangoli equilateri e isosceli. Gli equ sono dati da tre rette ruotate fra di loro di 60°, e sono quindi 147(rosso) e 358(blu). Un iso è dato da tre rette di cui una (la base) è bisettrice delle altre due; tutti gli iso si ottengono cercando, per ogni retta, le coppie simmetriche (escludendo naturalmente gli equ, anch’essi isosceli); l’elenco degli iso è pertanto, con la base come prima cifra, 138, 213, 248, 257, 314, 435, 426, 547, 758, 657, 648, 613, 817, 826, per un totale di 14 iso. Di questi sono presenti in fig. 1 ma non contati da Valter 613, 213 e 257; sono invece nascosti negli incroci multipli 314, 435, 758, 426. Il numero totale di triangoli di tutti i tipi è e quindi i triangoli scaleni sono . Questi sono tutti i triangoli per le 8 rette di Valter. Le birre sono.

Da fig. 3 si può ottenere, togliendo le 2 rette verdi, un gruppo completo di 6 rette equidistanti di 60°/2, oppure aggiungendo 4 rette un gruppo di 12 rette equidistanti di 60°/4. Definendo i gruppi completi, per ogni n, come composti da tutte le rette ad equidistanza angolare di 60°/n, possiamo estendere il problema a un numero illimitato di birre. In tabella i valori per i primi 9 gruppi.

I valori in tabella si calcolano da n e  con

 .

Per i gruppi completi la soluzione è massima (le birre sono il massimo possibile per il numero di rette); ogni retta è lato di un equ e di  iso diversi.

In tabella ho aggiunto, per 8 rette, le righe A e B; la prima è la soluzione già trovata, la seconda si ottiene dal gruppo n=3 togliendo una retta qualsiasi, cioè dallo schema di fig. 4, e migliora la precedente portando gli iso a 18; le birre sono 24, che ritengo il massimo per 8 rette.

Forse si possono trovare soluzioni da 300 birre nello stesso modo, aggiungendo o togliendo rette ai gruppi completi n=8, 9; ma non ho provato.

E adesso veniamo ai problemi del mese scorso, o almeno ad uno.

4.3     [214]

4.3.1    “Animatoreee!”

Gioco d’azzardo con soldi da monopoli? Ma sarà accettabile? Vediamo come funziona:

Abbiamo tre volontari, Anna, Bruno e Carla, cinque dadi e abbiamo distribuito soldi del Monopoli ad A, B e C, i quali ne possono puntare dieci ciascuno per ogni partita. Lanciamo i dadi e facciamo il prodotto dei valori dei dadi:

1.            Se il valore è divisibile per 10 ma non per 24, Anna prende il piatto.

2.            Se il valore è divisibile per 24 ma non per 10, Bruno prende il piatto.

3.            Se il valore è divisibile sia per 24 che per 10, Carla prende il piatto.

4.            Se il valore non è divisibile né per 10 né per 24, il piatto resta sul piatto.

Che cosa succede giocando dieci, venti o anche cinquanta partite? Come finisce?

La prima soluzione è di Alberto R., che andiamo a presentare senza porre tempo in mezzo:

La prob che il prodotto della quintupla ottenuta lanciando cinque dadi sia divisibile per 10 può essere ottenuta con questa formulaccia

dove la prima parte sotto sommatoria è la formula di Bernoulli che dà la prob che il “5” esca esattamente k volte su 5 lanci e la parte dentro l’ultima parentesi esprime la prob che almeno uno dei restanti 5-k elementi della quintupla sia pari; in essa la prob che l’evento “pari” non si verifichi è espressa dalla frazione 2/5 e non 3/6 perché avendo imposto la condizione che il “5” sia uscito esattamente k volte, esso non può figurare tra i restanti 5-k numeri.

Quanto alla divisibilità per 24 la situazione è molto più complicata. 24 può essere ottenuto come 4*6, 2*3*4, 2*2*6 e 2*2*2*3. Anche calcolando, con metodo analogo a quello innanzi descritto, le prob di ciascuno di questi casi, esse non potrebbero essere semplicemente sommate riferendosi ad eventi non incompatibili perché, ad esempio, l’insieme delle quintuple contenenti un “4” e un “6” e l’insieme delle quintuple contenenti un “2”, un “3” e un “4” non sono evidentemente insiemi disgiunti. Il problema, poi, si complica ulteriormente nei casi misti tipo divisibile per 10 e non per 24. Occorrerebbe un’idea “rivoluzionaria”, ma non mi è venuta, e spero vivamente che qualche lettore la trovi, dato che i Rudi non ci daranno la soluzione neanche se li preghiamo in ginocchio.

Osservo infine che la soluzione “forza bruta” è facilissima. Basta scrivere una decina di righe di codice per scoprire che dei 6^5 = 7776 prodotti ottenuti moltiplicando le possibili quintuple ordinate (solo quelle ordinate sono equiprobabili) ce ne sono:

·         4440 divisibili per 10

·         4486 divisibili per 24

·         2175 divisibili sia per 10 che per 24

·         2265 divisibili per 10 e non per 24

·         2311 divisibili per 24 e non per 10

·         1025 non divisibili né per 10 né per 24

Quindi, ad esempio, la prob che un prodotto sia divisibile per 10 è 4440/7776=0,570988 a conferma della formulaccia di cui sopra.

Inoltre risulta, come deve essere,

4440 + 4486 – 2175 + 1025 = 7776

2265 + 2175 = 4440

2311 + 2175 = 4486

a riprova del fatto che il computer non ha sbagliato.

Purtroppo non abbiamo visto altre soluzioni… malgrado l’enorme ritardo. Chiudiamo quindi con una torta di Venn:

Grazie a tutti e alla prossima!

5.    Quick & Dirty

Qualcuno di voi ricorda Creature della Luce e delle Tenebre, di Roger Zelazny[7]? Uno dei personaggi era il Generale di Ferro, che aveva un cavallo in grado di fare il primo passo di un metro, il secondo di due metri, il terzo di quattro metri e avanti raddoppiando.

In qualità di Stallieri del Cavallo del Generale di Ferro, vi viene chiesto di “portarlo a fare un giretto, ma di riportarlo esattamente qui.”. Riuscite, con un’oculata scelta di passi avanti e indietro, a tornare “esattamente qui”?

6.    Pagina 46

Sono possibili almeno due soluzioni:

Soluzione 1: Supponiamo di avere a₁, a₂, a₃, … ak e b₁, b₂, b₃, … bk in Sn tali che:

dove ai ≤ ai₊₁, bi ≤ bi₊₁ e, per qualche i, ai ≠ bi. Se k è il minimo intero per cui esistono le somme indicate, allora possiamo supporre che ∀i, j, ai ≠ bj, in quanto in caso contrario potremmo eliminare i termini uguali e ottenere un valore di k minore. Sia, quindi, a₁ < b₁: dividendo entrambe le espressioni per a₁, possiamo ulteriormente assumere a₁ = 1 .

Essendo ogni bn divisibile per n, avremo almeno n “1” sul lato sinistro dell’equazione: se fosse k = n, allora il lato destro sarebbe strettamente maggiore del lato sinistro, quindi deve essere k ≥ n + 1. A questo punto, l’espressione

mostra che k = n + 1.

Soluzione 2: La soluzione si articola in tre punti.

Primo, deve essere k(n) ≤ n + 1, in quanto:

.

Secondo, deve essere k(n) ≥ n, in quanto ogni intero positivo N ha una rappresentazione unica in base n ossia, posto in altri termini:

.

Questo significa che se N ha una seconda rappresentazione come somma di elementi di Sn, allora almeno uno degli elementi di questo insieme deve ricorrere almeno n volte; quindi, k(n) ≥ n .

Terzo, deve essere k(n) ≠ n , in quanto se supponiamo che k(n) = n e che M sia un intero con due diverse rappresentazioni:

, con si, ti ∈Sn,

allora per l’unicità della rappresentazione almeno una di queste due espressioni (supponiamo, il primo membro) non è una rappresentazione di M in base n. Come dedotto nel precedente paragrafo, tutti gli si devono essere uguali, poniamo a ns: quindi, M = ns⁺¹.

Ma questo significa che neppure il secondo membro è una rappresentazione di M in base n, e quindi (come sopra) tutti i ti devono essere uguali, poniamo a nt. Segue che M = ns⁺¹ = nt⁺¹, e quindi s = t, s₁ = … = sn = t₁ = tn, il che contraddice l’assunto che le due rappresentazioni debbano essere differenti.

Conclusione: n < k(n) ≤ n + 1 => k(n) = n + 1.

7.    Paraphernalia Mathematica

Molto probabilmente ve ne sarete accorti da soli, ma sul terzo pianeta sembra sia tornato di moda discutere di sistemi elettorali.

All’avanguardia come sempre, vi ricordiamo che di tutto questo ne abbiamo già parlato[8], ma alcune parti erano state trattate secondo noi con eccessiva leggerezza. Avendo di recente recuperato un interessante articolo di Eric Maskin sul Teorema di Arrow applicato ai sistemi elettorali[9]: gli esempi, come sempre, sono tratti dalle elezioni americane, e neanche le ultime, ma aggiornare il tutto alle ultime è “elementare” (e una volta tanto, non stiamo scherzando).

7.1    I Sistemi Elettorali [6] – Qui non funziona nulla... ma siamo tanto simpatici.

Il titolo è un omaggio allo zinale preferito da mio suocero, che portava questa frase in grandi caratteri sul davanti.

Cominciamo con il richiamare qualche concetto: nel momento stesso nel quale c’è un ruolo politico da ricoprire (aka una poltrona libera, per fare un po’ di populismo), allora il sistema elettorale è un metodo per scegliere all’interno di un insieme di candidati sulla base della quantità di voti ricevuti dal candidato (e la votazione, per gli americani, è il ballot: sorgente di infinita confusione per il suo false friend).

Il metodo più utilizzato nel mondo è quello a maggioranza (che gli americani chiamano plurality rule, per loro la majority è un’altra cosa): si chiede a tutti gli elettori che candidato (uno solo!) preferiscono e quello che prende più voti vince. Come esempio, prendiamo gli stessi candidati dei nostri precedenti esempi e supponiamo i risultati siano stati:

Secondo la regola a maggioranza, Alice vince tranquillamente la competizione elettorale, anche se non ha la maggioranza assoluta (la overall majority americana è questa) dei voti.

Un altro metodo utilizzato è quello della maggioranza semplice (sempre per gli americani: la simple majority): viene eletto il candidato che è preferito dalla maggioranza rispetto a qualsiasi altro candidato. Qui la cosa si fa un po’ più complessa, in quanto si chiede agli elettori di ordinare i candidati (tutti), per riuscire a fare i conti, ma siccome stiamo usando un piccolo numero di candidati, possiamo ancora farcela[10]. Risultati dell’elezione:

Notate che, se prendete la prima colonna, avete gli stessi valori del caso precedente, quindi i due casi sono perfettamente compatibili con lo stesso elettorato.

Come finiscono elezioni di questo genere? Semplice: il 60% (=35%+25%) preferisce Doc a Alice; e il 75% (=40%+35%) preferisce Doc a Rudy, da cui, Doc vince contro qualsiasi altro candidato.

E sin qui, se all’epoca vi foste lanciati in qualche calcolo elementare, ve ne sareste accorti da soli: cambiando il metodo di voto, possiamo cambiare il risultato elettorale.

Il fatto che il risultato cambi in questo modo, spinge a farsi una domanda politicamente (e matematicamente) scorretta: “Va bene, ma qual è il risultato ‘giusto’?” La risposta, come al solito, è “dipende”. A parte il fatto che potremmo tranquillamente inventarci altri metodi di voto e far vincere un po’ chi ci pare.

Quello che ha fatto Arrow è definire un contesto per rispondere a questa domanda. Per prima cosa, si è chiesto che cosa vogliamo da un sistema elettorale, ossia quali proprietà (o assiomi) deve soddisfare: il miglior sistema sarà (o saranno, non è detto che sia uno solo) quello che soddisfa tutti gli assiomi[11].

Il primo assioma è il cosiddetto Assioma della Decisione: qualunque sia il risultato dell’elezione, deve esserci uno e un solo vincitore. La formulazione originale di Arrow in realtà è più stretta, in quanto richiede anche la transitività: se Alice vince contro Doc e Doc vince contro Rudy, allora Alice deve vincere contro Rudy; se Rudy vince contro Alice e tutti e tre concorrevano all’elezione, allora nessuno dei tre viene eletto, quindi il metodo utilizzato non è decisivo.

Il secondo assioma ha due nomi, visto che quando viene applicato alle regole del welfare assume un nome diverso rispetto a quando viene applicato alle elezioni: visto però che abbiamo trattato anche l’altra parte, non dovreste aver problemi a riconoscere nel Principio del Consenso il Principio di Pareto. Se tutti gli elettori valutano Alice migliore di Doc, allora non deve essere possibile eleggere Doc. Ossia, passando all’economia, se esiste una situazione di equilibro (il consenso su Alice), lo spostarsi da questa situazione (eleggere Doc) non è vantaggioso (e quindi non si fa). Anche se un po’ tirata per i capelli, la situazione è esattamente la stessa: raggiunto un consenso (situazione ottimale per tutti), si resta lì (e non si elegge un altro).

Il terzo assioma è complicato dal fatto che utilizza un termine cui non siamo abituati a dare un significato tecnico: è il Principio dell’Impossibilità della Dittatura, e il “termine tecnico” è “dittatore”. Per ora accontentiamoci di una definizione secondo senso comune: si definisce “dittatore” qualsiasi elettore che vede sempre realizzata la propria scelta, indipendentemente da quale sia il risultato delle elezioni. In pratica, se il dittatore preferisce Rudy, viene eletto Rudy, qualunque sia l’opinione della parte restante del corpo elettorale.

Il quarto assioma è noto come Principio delle Alternative Irrilevanti (o “Indipendenza dai Candidati Irrilevanti”): supponiamo, in questo nostro universo, che con il sistema di voto utilizzato Alice sia la vincitrice delle elezioni, e Rudy prenda una quantità di voti infima; spostiamoci ora in un altro universo, nel quale (a parità di elettori, nel senso che gli elettori hanno le stese opinioni) Rudy non è candidato: siccome non ha vinto le elezioni in questo universo, il risultato deve essere lo stesso nell’altro, e Alice deve, come successo da questa parte dello Stargate, vincere le elezioni.

Come si comportano i nostri sistemi elettorali nei confronti di questi quattro assiomi? Mica tanto bene.

Il Principio delle Alternative Irrilevanti dovrebbe servire ad eliminare appunto le alternative irrilevanti o, come si dice in gergo, gli spoiler, ma in vari sistemi elettorali non riesce: in praticamente tutta la letteratura viene citato il caso delle elezioni presidenziali americane del Duemila, dove la Florida ha giocato un ruolo cardine e George (Dabliu) Bush ha vinto contro Al Gore per 700 voti. Qui, lo spoiler era Ralph Nader, che aveva raggranellato 100.000 voti; se non si fosse presentato, la stragrande maggioranza di questi voti sarebbero andati a Gore trasformandolo in Presidente degli Stati Uniti d’America. Una pletora di casi più recenti (e più vicini) li potete trovare in buona parte delle elezioni amministrative italiane che prevedano il ballottaggio: maggioranza al primo turno di un candidato, al ballottaggio vince un altro candidato (visto che gli elettori del terzo hanno deciso che “meglio il secondo che il primo”).

Va detto che anche l’elezione “secca” (al primo turno, per maggioranza semplice) non funziona. Se il risultato dell’elezione è, ad esempio, quello mostrato qui di seguito:

Qui, Doc batte Rudy (se Alice non si presenta) 35%+33%=68% a 32%, mentre Alice batte Doc (se Rudy non si presenta) 35%+32%=67%% a 33%. Ma Rudy batte Alice (se Doc non si presenta) 33%+32%=65% a 35%, e nessuno dei candidati batte separatamente ciascuno degli altri.

“...e perché non l’hai chiamato ‘Paradosso di Condorcet’?” Per il semplice motivo che Arrow, quando ci lavorava, non lo conosceva: lo ha riscoperto nel tentativo di spiegare (vi ricordate, che il lavoro era in origine una teoria economica?) come i consigli di amministrazione effettuano le scelte.

Va detto che per alcuni metodi le eccezioni sono abbastanza improbabili: il maggior numero infatti si presenta quando si tengono in considerazione tutte le alternative di ordinamento possibili: ma (per fare un esempio politico) è piuttosto difficile che esistano degli elettori che ordinano i candidati come “estrema sinistra – estrema destra – centro” (o inversione di due primi fattori), e non considerare queste ipotesi, anche se scorretto dal punto di vista matematico, lo è dal punto di vista della realtà: ridurre le alternative di ordinamento riduce drasticamente le incompatibilità tra i cinque assiomi.

A questo punto, sorge spontanea una domanda: visto che nessun sistema rispetta tutti e cinque gli assiomi contemporaneamente, qual è quello che li rispetta più spesso? O, visto che abbiamo parlato di escludere più ordinamenti, quale richiede l’eliminazione del minor numero possibile di ordinamenti per soddisfare i cinque assiomi?

La risposta è data dal Teorema della Dominazione: sia data una regola diversa da quella della maggioranza che funziona per una data classe di ordinamenti; allora la regola di maggioranza funzionerà per quella classe.

Quindi, la regola della maggioranza funziona in tutti i casi in cui funziona il nostro caso e, se in qualche caso funziona anche quando non funziona il nostro metodo, allora la classe di ordinamenti per cui funziona è più estesa, e quindi è un metodo “migliore” (o, come dice il nome del teorema, “Domina” qualsiasi altro metodo).

Quello che lascia sempre perplessi, è la faccenda del dittatore. Prendiamola matematicamente.

Supponiamo che, per una data tabella di preferenza (o profilo) P, tutti i voti rimangano distribuiti come sono con l’eccezione di un determinato votante X e che, comunque voti X relativamente a due candidati A e B, il risultato finale dell’elezione per quanto riguarda A e B sia comunque quello votato da X: in questo caso, X viene detto cardine per A e B nel profilo P; se sono presenti altri candidati e il voto di X è cardine per A nel confronto con qualsiasi altro candidato, allora X viene detto cardine estremo per A.

Se il voto di un elettore X è cardine per A e B, allora X viene detto dittatore della coppia A, B nel profilo P; se X è dittatore di qualsiasi coppia che si possa formare in un dato profilo P, X viene detto dittatore locale in P; se, infine, X è dittatore locale per qualsiasi profilo, allora viene semplicemente detto dittatore.

Dai, che questo era semplice.

Per dimostrare la correttezza del Teorema di Arrow, dobbiamo prima dimostrare quello che è chiamato il Lemma Estremale: se in un sistema soddisfacente l’efficienza secondo Pareto e indipendente dalle alternative irrilevanti esiste un candidato C tale che ogni elettore pone C o come primo o come ultimo nella propria lista di preferenze, allora o C viene eletto o l’elettorato preferisce ogni altro candidato a C.

Per assurdo, supponiamo il lemma non sia vero: in questo caso, deve esistere un profilo in cui ogni elettore posiziona C come primo o come ultimo tra le proprie preferenze, ma il risultato finale posiziona C altrove; con tre candidati, ad esempio, la situazione finale potrebbe essere A>C>B. Se gli elettori che preferivano comunque A a B scambiano queste loro preferenze, ponendo B al di sopra di A, per la regola dell’indipendenza delle alternative irrilevanti questo non deve influenzare la posizione relativa di A e C e di B e C in qualsiasi risultato elettorale. Ma ora ogni elettore preferisce B ad A, e quindi essendo efficiente secondo Pareto il sistema deve dare B>A; ma il risultato è, per definizione, A>B>C, quindi A>B, che è una contraddizione e quindi il lemma estremale è valido.

Per provare il Teorema di Arrow, dimostreremo che se il sistema soddisfa l’indipendenza dalle alternative irrilevanti ed è efficiente secondo Pareto, allora esiste un dittatore.

Supponiamo ci siano n votanti X₁, X₂, ..., Xn, il cui ordine sia completamente arbitrario, e esaminiamo un profilo P₀ nel quale tutti i votanti hanno posto C come scelta peggiore. Quindi, costruiamo una successione di profili P₁, P₂, ... Pn in modo tale che nel profilo P₁ tutto è invariato tranne lo spostare la preferenza su C di X₁ dal fondo all’inizio: in genere, nel profilo Pj abbiamo la stessa situazione del profilo Pj₋₁ tranne per il fatto che la preferenza per C dell’elettore Xj viene spostata dalla fine all’inizio, lasciando tutto il resto invariato.

Dal Lemma Estremale sappiamo che in ognuno di questi profili C è posizionato primo o ultimo; dalla regola dell’Efficienza secondo Pareto sappiamo che C è valutato ultimo nel profilo P₁ e primo, o vincitore, nel profilo Pn.

Se Pk è il primo profilo nel quale C risulta vincitore, allora C è sempre ultimo in tutti i profili P₁, P₂,..., Pk₋₁, ma è primo in Pk: quindi, Xk è un cardine estremo per C in Pk₋₁ e Pk.

Mostriamo ora che Xj è dittatore della coppia per ogni coppia che non coinvolga C.

Supponiamo A e B siano due altri candidati; scelto uno di loro (A, ad esempio), costruiamo un nuovo profilo Q: Xj sposta la preferenza per A al di sopra di quella di C, e quindi Xj ha una valutazione A>C>B: supponiamo anche che tutti gli altri votanti siano liberi di cambiare i loro voti in modo tale che C resti nella stessa posizione estremale (primo o ultimo) che aveva in Pk. Per l’Indipendenza delle Alternative Irrilevanti, l’elettorato valuterà A sopra C (visto che tutti i votanti valutano A al di sopra di C (visto che tutti valutano A e C come nel profilo Pk₋₁, dove C era il meno preferito), e valuteranno C sopra B (visto che tutti valutano A C nello stesso ordine nel quale erano valutati nel profilo Pk, dove C era primo nella classifica). Quindi, l’intero corpus elettorale valuta A migliore di B ogni volta che Xj valuta A migliore di B; ma esattamente lo stesso ragionamento può essere fatto sostituendo A con B, e quindi Xj è dittatore della coppia tra A e B, e quindi lo è per ogni coppia che non coinvolga C.

Lo stesso ragionamento però può essere applicato utilizzando al posto di C un qualsiasi altro candidato D; quindi esisterà sempre un qualche elettore Xh che è dittatore per qualsiasi coppia che non coinvolga D e, se D è diverso da C, Xh è dittatore di coppia per ogni coppia che coinvolga C. In particolare, possiamo assumere che D non sia né A né C, e quindi che Xh sia dittatore di coppia rispetta ad A e C. Se Xh e Xk sono elettori diversi, allora Xj non può forzare un cambio nelle valutazioni elettorali di A e C. Ma abbiamo appena visto che lo può fare nel passaggio dal profilo Pj₋₁ al profilo Pj, e quindi Xh e Xk devono essere lo stesso elettore, che è quindi un dittatore.

Proviamo più Terra-Terra? Con qualche esempio, ad esempio? Nel sistema di ballottaggio, consideriamo il profilo:

Al primo turno, A conquista 4 voti (seconda colonna), B ne riceve 2 (terza colonna) e C ha unicamente la maggioranza relativa con 2+3=5 voti; avendo 11 votanti, nessuno dei candidati raggiunge la maggioranza assoluta e quindi viene eliminato B. Al ballottaggio C vince con 2+2+3=7 voti (prima, terza – per eliminazione di B – e quarta colonna) contro i 4 di A (seconda colonna).

Supponiamo però che due votanti della quarta colonna cambino la loro lista di preferenze da C>B>A a B>C>A, spostandosi quindi nella terza colonna: questa è una Alternativa Irrilevante, in quanto l’ordine relativo di A e C, i due finalisti nel caso precedente, non cambia: i due elettori continuano a preferire C ad A.

Ma cosa succede nella tabella delle preferenze? La tabella si modifica in questo modo:

In questo modo al primo turno viene eliminato C, che ha solo 3 voti (prima e quarta colonna), mentre accedono al secondo turno sia A che B con 4 voti a testa (rispettivamente, seconda e terza colonna); al ballottaggio, A conquista 6 voti mentre B si ferma a 5.

In entrambi i casi, nessun elettore ha modificato la propria valutazione relativa per i due vincitori A o C, ma lo spostamento di B ha permesso di cambiare il risultato delle elezioni.

Anche la monotonicità, che sembra un presupposto ovvio di qualsiasi sistema di voto, può essere violata con il metodo del ballottaggio: ad esempio, partendo dal profilo:

Si vede che nessun candidato raggiunge la maggioranza assoluta, ed è quindi necessario un ballottaggio tra A (che riceve al primo turno 11 voti) e B (che riceve 2+7=9 voti dalla seconda e terza colonna), con l’eliminazione di C (8 voti, quarta e quinta colonna); al ballottaggio A vincerà per 11+4=15 voti (prima e quarta colonna) contro i 2+7+4=13 voti di B seconda, terza e quinta colonna).

Ma se i due votanti della seconda colonna cambiano il loro voto portando A al primo posto nelle loro scelte, il profilo risultante sarà:

In questo modo si avrebbe B eliminato e, al ballottaggio, A riceverebbe 13 voti (prima colonna), mentre C ne riceverebbe 7+4+4=15, vincendo le elezioni: il fatto che due votanti ben precisi abbiano spostato al primo posto quello che senza movimento sarebbe stato il vincitore, ha fatto sì che il primo vincitore diventasse perdente, e questa è una violazione della monotonicità.

Insomma, marca male.

[1] No, non abbiamo intenzione di autorisponderci. L’elenco dei compleanni si trova sul sito, nell’Index Mundi. Molti anni fa un caro lettore ha provato a fare un indice analitico dei compleanni, missione impossibile oggi…

[2] Siccome questo compleanno sta già degenerando per diversi motivi, ne approfittiamo per farvi parte di un’altra scoperta di un personaggio famoso vissuto ad Harbin in quel periodo: Pietro Gibello-Socco (Callabiana, 1886 – Shanghai, 1943) – Ingegnere e imprenditore. All’inizio del XX secolo partecipò alla costruzione della rete ferroviaria siberiana accumulando una enorme fortuna. Dopo la rivoluzione russa si ritirò a Harbin in una lussuosa residenza e qui fu soprannominato il nababbo biellese. Morì a Shanghai nel 1943.[Wikipedia, alla voce di Harbin, per la felicità del Capo]

[3] A quanto pare non era particolarmente portata per le attività manuali, mentre le lezioni di matematica, fisica, chimica, inglese non erano un problema!

[4] Ebbene sì, doveva essere lei la protagonista del compleanno, ma l’estensore di queste righe si è semplicemente sbagliato. Con il ritardo accumulato, facciamo finta di niente e andiamo avanti.

[5] Finalmente. Buon compleanno al congresso, che quest’anno celebra la quarantasettesima sessione ufficiale, o dal ritmo con cui scriviamo queste righe, probabilmente ha già finito le sessioni.

[6] Quelli di voi che stanno per dire “...ma io non ho ricevuto nulla!”, si facciano delle domande. E si diano delle risposte.

[7] Edizione integrale, non il bignamino pubblicato da Urania.

[8] I numeri precedenti della serie “I sistemi elettorali” sono comparsi sui numeri 031, 033, 035 e 112. Che sicuramente portate con voi anche sotto la doccia.

[9] Vi ricordiamo che il Teorema di Arrow è estremamente generale: tant’è che, associato all’articolo di Maskin, ne abbiamo trovato uno di Amartya Sen relativo alla sua applicazione al sistema del welfare.

[10] Notizia colta al volo alla radio qualche giorno fa: alle elezioni nella Repubblica Centrafricana si erano presentati ottantasette partiti. Se avessero dovuto metterli in ordine, il primo finiva di votare che era già scaduto il mandato.

[11] Nel caso vi capitasse tra le mani l’articolo originale di Arrow, li troverete diversi. Il lavoro di Maskin è stato di adattarli ai sistemi elettorali.