Archivi categoria: Algoritmi e paradossi

achille e la tartaruga

Il paradosso di Achille e la tartaruga

A Zenone di Elea (450 a.C.) viene attribuita la creazione di numerosi paradossi famosi e forse il più noto è il paradosso di Achille e la tartaruga (Achille era il grande eroe greco dell’Iliade di Omero). Ha ispirato molti scrittori e pensatori nel corso dei secoli, in particolare Lewis Carroll (vedi Paradox di Carroll) e Douglas Hofstadter, entrambi i quali hanno scritto dialoghi espositivi che coinvolgono la Achille e la tartaruga.

Varie formulazioni del Paradosso di Achille e la tartaruga

La traduzione della versione originale di questo paradosso di Zeonone è più o meno come scritto qui sotto:


La tartaruga ha sfidato Achille ad una gara, sostenendo che avrebbe vinto a patto che Achille gli avesse dato un piccolo vantaggio. Achille rise di questo, perché ovviamente era un potente guerriero ed era rapido, mentre la tartaruga era pesante e lenta.

“Di che grande vantaggio hai bisogno?” Chiese sorridendo alla tartaruga.

“Dieci metri”, rispose quest’ultimo.

Achille rise più forte che mai, “Perderai sicuramente, amico mio”, disse alla Tartaruga, “ma facciamola pure questa gara, se lo desideri.”

“Al contrario”, disse la tartaruga, “vincerò e posso dimostrartelo con una semplice discussione”.

“Continua allora”, rispose Achille, con meno sicurezza di prima. Sapeva di essere un’atleta superiore, ma sapeva anche che la Tartaruga era più furba e acuta, e aveva perso molte discussioni al limite dell’assurdo con lei in passato.

“Supponiamo” iniziò la Tartaruga, “che mi dai un vantaggio di 10 metri. Pensi che saresti in grado di percorrere questi 10 metri di svantaggio iniziale rapidamente?”

“Molto rapidamente” affermò Achille.

“E quando avrai percorso quei 10 metri, fino a dove pensi che sarò arrivata?”

“Forse avrai fatto un metro, non di più”, disse Achille dopo un momento di riflessione.

“Molto bene”, rispose la tartaruga, “quindi ora c’è un metro tra di noi. E pensi di colmare quella distanza molto velocemente? ”

“Molto rapidamente, davvero!”

“Eppure, in quel momento sarò andata ancora un po’ più avanti, saresti ancora in grado di recuperare quella distanza, giusto?”

“Sì”, disse Achille lentamente.

“E mentre lo fai, sarò andata ancora un po’ più lontano, in modo che tu debba poi recuperare ancora la nuova distanza”, continuò la Tartaruga senza intoppi.

Achille non disse nulla.

“Ecco quindi che inizi a realizzare che, in ogni momento, devi recuperare una distanza tra noi, inoltre io – nel tempo a te richiesto per recuperarmi – percorrerò ancora nuova strada, per quanto piccola, così che dopo tu debba recuperare di nuovo.”

“In effetti, deve essere così”, disse stancamente Achille.

“E così non potresti mai raggiungermi” concluse la Tartaruga con simpatia.

“Hai ragione, come sempre”, disse tristemente Achille – e concesse la corsa.


Il paradosso di Zenone può essere riformulato in maniera “più moderna” come segue. Supponiamo che io voglia attraversare la stanza. Innanzitutto, ovviamente, devo percorrere metà della distanza. Quindi, dopo, devo coprire metà della distanza rimanente. E dopo devo coprire metà della distanza rimanente. E poi devo coprire metà della distanza rimanente… e così via per sempre. La conseguenza è che non riesco mai ad arrivare dall’altra parte della stanza.

Quest’immagine, seppur in inglese penso ti chiarirà il concetto:

Trovata su Reddit

Nell’immagine qui sopra si può vedere un criceto che vuole rasarsi il pelo, va quindi in un negozio dove ad ogni sessione gli radono metà del pelo che ha attualmente…esattamente come Achille non prende mai la tartaruga, anche in questo caso il criceto non potra mai essere completamente rasato, dato che:

$\Big(\frac{1}{2}\Big)^n>0\;\;\;\forall n\in\mathbb{N}.$

Una delle descrizioni più famose del paradosso è dello scrittore argentino Jorge Luis Borges:

«Achille, simbolo di rapidità, deve raggiungere la tartaruga, simbolo di lentezza. Achille corre dieci volte più svelto della tartaruga e le concede dieci metri di vantaggio. Achille corre quei dieci metri e la tartaruga percorre un metro; Achille percorre quel metro, la tartaruga percorre un decimetro; Achille percorre quel decimetro, la tartaruga percorre un centimetro; Achille percorre quel centimetro, la tartaruga percorre un millimetro; Achille percorre quel millimetro, la tartaruga percorre un decimo di millimetro, e così via all’infinito; di modo che Achille può correre per sempre senza raggiungerla».

Jorge Luis Borges

Ovviamente questo è un paradosso perchè porta a risultati parecchio controintuitivi. Se ti interessa sapere qualcosa di più approfondito sulla nozione di Paradosso e su altri esempi avevo scritto questi articoli a riguardo:

Vediamo però ora i problemi che si incontrano quando si vuole “verificare” questo paradosso nel mondo reale.

Il paradosso di Achille e la tartaruga nel mondo reale

Quando si parla di matematica del continuo e di numeri reali, tutto quanto detto nelle varie formulazioni del paradosso torna. Infatti i numeri reali godono di una proprietà davvero importante, riassunta nel cosiddetto Assioma di completezza.

Data una qualunque coppia $A,B\subset\mathbb{R}$, entrambi non vuoti e tali che $a\leq b$ $\forall (a,b)\in A\times B$, allora esiste un numero reale $c$ tale che $a\leq c \leq b,\;\;\forall (a,b)\in A\times B.$ Questo $c$ è detto separatore degli insiemi $A$ e $B$

Assioma di Completezza numeri reali

Questo implica che ogni insieme limitato superiormente ammetta estremo superiore e se limitato inferiormente ammetta estremo inferiore e, in parole povere, dice che la retta reale è senza buchi.

Come può questo aiutarci a costruire il paradosso di Achille e la tartaruga?

Beh, semplicemente perché in questo modo sappiamo che di ogni distanza possiamo calcolarne una frazione e quindi dire che Achille non raggiungerà mai, lungo la retta reale, la tartaruga.

Cosa succede invece nel mondo reale? Facciamola molto semplice, supponiamo che i piedi di Achille sia di 20cm per semplicità. Bene, supponiamo in oltre che il vantaggio iniziale sia di 10 metri e che Achille sia 2 volte più veloce della tartaruga. Ottimo, vediamo cosa succede nella gara:

  1. Quando Achille percorre i 10 metri iniziali di vantaggio, la tartaruga ne ha fatti altri 5 (“nuovo svantaggio”)
  2. Quando recupera anche questi 5, la tartaruga ne ha fatti altri 2.50m
  3. In seguito, nel tempo che Achille recupera questi 2.5m la Tartaruga ne fa 1.25m
  4. Poi percorrono rispettivamente 2.5m e 0.625m
  5. Quindi 0.625m e 0.3125m (Anche se sarebbero difficili da misurare, supponiamo però di riuscire senza errori)
  6. Eccoci al punto critico: ora Achille ne fa 0.3125 e la tartaruga 0.15625‬m

Ottimo, il distacco tra i due a questo punto è quindi di 0.15625m, che è meno della lunghezza del piede di Achille. Supponiamo che tutte le misurazioni delle distanze sono state prese dal tallone di Achille, ciò vuol dire che la punta dei suoi piedi ha ormai raggiunto la tartaruga.

Ora, sono consapevole che è un po’ buttato lì questo ragionamento, ma con i numeri volevo farti vedere come nella realtà questo sia davvero impossibile, dato che gli esseri viventi non sono puntiformi e non siamo nemmeno in grado di dividere infinitamente bene una distanza. Quindi nel mondo reale prima o dopo i due sarebbero allo stesso livello.

Si può dimostrare anche matematicamente che nella vita reale Achille avrebbe raggiunto la tartaruga in tempo finito, come vedremo qui di seguito (il ragionamento è preso da Wikipedia ma è molto naturale procedere in questo modo).

Il tutto sarà basato sullo studio di una serie geometrica. Definiamo con $T$ il tempo necessario ad Achille per raggiungere la tartaruga, come possiamo scrivere questo tempo?

$T=t_0+t_1+t_2+….$

dove $t_i$, $i\in\mathbb{N}$ sono i tempi necessari ad Achille per colmare l’$i-$simo divario con la tartaruga. Quindi a priori sono infiniti contributi da sommare. Andremo però a mostrare, grazie a qualche semplice legge fisica, che nel concreto questa somma è in realtà finita. Definiamo però ora un sistema di riferimento in cui lavorare:

  • Fissiamo l’origine dell’asse $x$ alla posizione iniziale di Achille, mentre quella iniziale della tartaruga la diciamo $L_0$.

  • Definiamo con $L_1,L_2,…$ le successive distanze, quelle colmate in $t_1,t_2,…$ dall’eroe.

  • La velocità di Achille è definita $v_A$ mentre quella della tartaruga $v_T$, dove chiaramente $v_A>v_T$ altrimenti possiamo già concludere che l’eroe non raggiungerà mai l’avversaria.

  • Nel paradosso è supposta l’esistenza di una costante $d$ tale che $\frac{v_T}{v_A}=d$, ad esempio $d=1/10$ se Achille va 10 volte più veloce della tartaruga.

La legge del moto rettilineo uniforme afferma che $x_A(t)=s_0 + v_At = v_At$ visto che fissiamo la posizione iniziale di Achille a 0. Per la tartaruga vale invece $x_T(t) = L_0 + v_Tt$. Il tempo $t_0=\frac{L_0}{v_A}$ è quello richiesto ad Achille per percorrere il distacco iniziale di $L_0$.

Quanto spazio ha percorso la tartaruga in questo tempo $t_0$? Beh, basta usare la legge oraria:

$L_1 = x(t_0)-x(0) = L_0+v_Tt_0-L_0=v_Tt_0=v_T\frac{L_0}{v_A}.$ A questo punto si può procedere calcolando $t_1$, ovvero il tempo necessario ad Achille per percorrere $L_1$, vedendo che ancora si ha $t_1=\frac{L_1}{v_A}$, tempo durante il quale la tartaruga si muoverà di $L_2 = v_Tt_1$ e così via per gli spostamenti futuri…

Quindi

$t_n=\frac{L_n}{v_A} = \frac{v_Tt_{n-1}}{v_A} =t_{n-1}\frac{v_T}{v_A} = dt_{n-1},$ da cui segue per ragionamento induttivo, che $t_n=d^nt_0$.

Eccoci quindi quasi alla conclusione, riassembliamo i pezzi per ricavare

$T = t_0+t_1+t_2+…=t_0+dt_0+d^2t_0+…+d^nt_0+… = \sum_{n=0}^{+\infty} d^nt_0 = t_0 \sum_{n=0}^{+\infty} d^n $

che è effettivamente una serie geometrica. Siccome $d<1$, si ha che essa converge e il valore a cui converge sarà:

$T=t_0\frac{1}{1-d}=t_0\frac{1}{1-v_T/v_A} = \frac{v_At_0}{v_A-v_T}=\frac{L_0}{v_A-v_T}<+\infty.$

Eccoci a concludere quindi che nel mondo reale, i due si incontreranno dopo un tempo $T$ che è finito e, chiaramente, dopo questo istante Achille supererà la tartaruga. Una cosa che ci tengo a farti notare, più $v_A-v_T$ è piccola, ovvero le due velocità sono simili, più il tempo necessario a pareggiare le posizioni cresce.

Un’altra cosa interessante è che se, per assurdo $v_A<v_T$ otterremmo un tempo $T<0$, che può essere interpretato nel senso che nel passato la tartaruga era dietro ad Achille ma l’ha superato.

Questa è una dimostrazione del perché questo è considerabile un paradosso. Infatti abbiamo che il risultato matematico è controintuitivo rispetto a quello che ci aspettiamo accada (e accade realmente).

La dimostrazione si basa unicamente sullo studio delle serie geometriche convergenti. Ah, se non conosci questi oggetti, puoi studiarli qui: Serie Geometrica – Youmath.

Però il ragionamento fatto dalla tartaruga fila nel momento in cui ci si pensa, giusto?

Paradossi matematici: Dalla moltiplicazione della sfera al paradosso del mentitore

Stavo bazzicando un po’ di tempo fa su Quora (ehm, si in effetti ci sto passando più tempo di quanto dovrei ultimamamente…) quando mi sono imbattuto nella domanda “Quali sono alcuni Paradossi matematici?” e senza pensarci due volte ho deciso di rispondere. Ho colto l’occasione al volo e mi sono documentato; nella risposta originale non mi sono dilungato troppo, ma qui possiamo scavare un po’ di più.

Prima di inziare però avviso chiunque abbia voglia di continuare, che a volte l’argomento sarà, per così dire, indigesto e abbastanza paradossale, appunto. Non posso non citare a questo punto quello che il mio professore di Analisi II mi ha detto una delle prime volte che è entrato in classe:

Chiedi quello che non devi e otterrai quello che non vuoi. ~AM

Ebbene preparatevi, perché si è giunti al punto di non ritorno. Di seguito ne elenco solo due (quelli che di più mi hanno colpito durante il mio percorso), ma una lista abbastanza esaustiva sui paradossi più famosi si può trovare qui.

Il paradosso di Banach-Tarski

Esso risale a due tra i più famosi matematici del ‘900, dicasi Stefan Banach e Alfred Tarski. Ma prima di enunciare il paradosso facciamo un passo indietro. Probabilmente nella vita di un matematico ci si imbatte prima o poi nell’assioma della scelta. Ebbene cosa dice? Immaginate di avere un certo insieme (di oggetti, di numeri, di calzini, di monete… poco importa). Ebbene nulla ci vieta in questo insieme di poterne scegliere un elemento… Ecco. L’assioma della scelta dice proprio questo:

Esiste una funzione che ad un insieme non vuoto fa corrispondere un suo elemento.

A dire il vero la definizione matematichese è un po’ più sottile, ma per quello che ci interessa ci possiamo fermare qui.1

Nulla di irragionevole a quanto pare… Appunto. Pare. Ebbene riporto qui una delle conseguenze più sconcertanti di questo assioma (attenzione: assioma significa che lo si può accettare come no! Se non lo si accetta, la matematica continua ad avere senso, ma si passerebbe allora ad un punto di vista cosiddetto costruttivista e questa diventa una storia moooolto lunga).

Prendiamo dunque una sfera in senso classico, cioè in . Suddividiamola in un insieme finito di pezzi non misurabili (detto in soldoni: dobbiamo suddividerlo in un modo sufficientemente complicato) . Utilizzando solo rotazioni e traslazioni è possibile riassemblare i pezzi in modo da ottenere due sfere dello stesso raggio dell’originale. È abbastanza controintuitivo riuscire a creare due sfere al posto di uno solo usando rotazioni e traslazioni senza usare allungamenti, stiramenti o aggiungendo punti. Ebbene però è così, perchè se i pezzi sono scelti in modo abbastanza strano, non si può definire una nozione di volume ben definita e quindi non è irragionevole aspettarsi che non si conservi.

[Gentile concessione di Wikipedia.org]

Confusi: ebbene non è finita qui! Questo “smantellamento” e “riassemblamento” può essere fatto anche con soli 5 pezzi! Niente dice che questi pezzi debbano essere infiniti! Beh non rimane che provarci a casa! Dividendo e riassemblando una pesca un numero finito di volte possiamo costruire una palla grande come il sole!

Breve nota storica

In realtà con questo risultato, Banach e Tarski intendevano fornire argomenti a sostegno della loro decisione di non avvalersi dell’assioma della scelta e speravano di spingere alle medesime conclusioni gli altri matematici dell’epoca. Contrariamente a quanto da loro auspicato, tuttavia, la maggior parte dei matematici preferisce utilizzare tale assioma e vedere nel risultato paradossale di Banach e Tarski semplicemente un risultato controintuitivo (e tuttavia di per sé non contraddittorio).[1]


1. [In matematichese, un’enuciazione appropriata dell’assioma della scelta potrebbe essere “Data una famiglia non vuota di insiemi non vuoti esiste una funzione che ad ogni insieme della famiglia fa corrispondere un suo elemento.” Notiamo che la cardinalità dell’insieme potrebbe anche essere infinita, ecco perchè questo assioma è abbastanza contestato. Una certa classe di matematici neanche troppo ristretta è abbastanza restia ad accettare questo assioma in quanto considerato in qualche modo “non naturale” e preferiscono lavorare solo con gli assiomi che si possono realmente “costruire” nella vita reale, ecco perchè si chiamano “costruttivisti” appunto, ma questa è un altra storia…]

Il paradosso di Russell

Se qualcuno si sta chiedendo perché la parola paradosso sia in corsivo, sappia che la risposta sta arrivandola risposta è scritta poco sotto… Questo paradosso (o per lo meno presunto tale) può essere enunciato così:

L’insieme di tutti gli insiemi che non appartengono a se stessi appartiene a se stesso se e solo se non appartiene a se stesso.

Dunque risulta un po’ più chiaro perché questo non sia un paradosso ma piuttosto un’antimonia… Citando Wikipedia “un paradosso è una conclusione logica e non contraddittoria che si scontra con il nostro modo abituale di vedere le cose, mentre un’antinomia è una proposizione che risulta autocontraddittoria sia nel caso che sia vera, sia nel caso che sia falsa”. [2]

Ebbene, questo problema fu sollevato in un periodo in cui la matematica stava attraversando un grave periodo di insicurezza e di instabilità in quanto non si riusciva a darle delle basi solide su cui fondarla. La questione sollevata da Russell alimentò in maniera significativa la necessità di trovare delle basi solide e stabili su cui fondare la regina delle scienze. Il rischio era che trovare che la matematica avesse delle contraddizioni interne o delle basi non consistenti, demolisse a cascata tutte le altre scienze che si fondavano sulla matematica stessa! Si lo so, sembra catastrofico messa così, ma in realtà lo è!

Storicamente il paradosso di Russell viene scoperto proprio nel periodo in cui Frege stava scrivendo (in realtà aveva già pubblicato il primo volume) un’opera monumentale in cui procedeva alla vera e propria “logicizzazione” dei concetti che Dedekind e Peano avevano dimostrato essere alla base dell’aritmetica e, di conseguenza, di tutta la matematica. Sto parlando dei Principî dell’aritmetica.

Immaginatevi la faccia di Frege ricevendo la lettera di Russell in cui gli viene detto che tutto il lavoro della sua vita era da buttare via…

Il problema tuttavia rimaneva aperto! Si può veramente fondare la matematica su qualcosa di solido/certo/lapidario/incontestabile/uguale per tutto e per tutti? Bisogna aspettare altri 29 anni per inquadrare questo paradosso all’interno di una cornice più grande… Fu il logico dall’altisonante nome di Kurt Gödel che, nel 1931, risolse definitivamente la questione dimostrando l’impossibilità tout court di produrre una fondazione certa dell’aritmetica.

I suoi risultati sono ora una pietra miliare e vanno sotto il nome di teoremi di incompletezza. Per completezza riporto qui di seguito il principale risultato di Godel che va anche a chiudere il cerchio di questa breve storia, ma che purtroppo lascia un senso di impotenza devastante:

Teorema (primo Teorema di Incompletezza) In ogni formalizzazione coerente della matematica che sia sufficientemente potente da poter assiomatizzare la teoria elementare dei numeri naturali — vale a dire, sufficientemente potente da definire la struttura dei numeri naturali dotati delle operazioni di somma e prodotto — è possibile costruire una proposizione sintatticamente corretta che non può essere né dimostrata né confutata all’interno dello stesso sistema.2


2. [L’idea di fondo della dimostrazione può essere così riassunta: Supponiamo esista una proposizione G la cui interpretazione standard sia “ non è dimostrabile in “. Se , cioè se $latexG$ fosse dimostrabile in $latexP, G$ risulterebbe falsa. Ma per il teorema di completezza di Gödel, ogni proposizione dimostrabile in risulta vera, dunque G non può essere dimostrabile in P e quindi è vera. Quindi risulta falsa e, per lo stesso motivo, non può essere dimostrabile in P. Pertanto se esiste una proposizione il cui contenuto è “io non sono dimostrabile in P”, tale proposizione risulterà vera ma non dimostrabile.]


So che sarà dura, ma questa notte cercate di riuscire a dormire…

Au revoir,

Erik

Bibliografia

[1] https://it.wikipedia.org/wiki/Paradosso_di_Banach-Tarski

[2] https://it.wikipedia.org/wiki/Paradosso_di_Russell

Il commesso viaggiatore… Alla scoperta della Programmazione Lineare

Amazon riceve decine di milioni di nuovi ordini ogni giorno. Un numero che solo a pensarlo può dare un senso di stordimento.

Mettiamoci nei panni di uno dei servizi di spedizione a cui questa grande compagnia si appoggia. Il flusso di pacchi da gestire è enorme e per aumentare al massimo il profitto bisogna trovare un modo per ridurre al minimo il percorso di ogni spedizioniere.

Qui salta fuori il famoso problema del “Commesso viaggiatore”, ossia come trovare il tragitto più breve che passi per un insieme finito di punti nello spazio.

In questo post cercheremo di cogliere la reale complessità del problema e di risolverlo andando così… alla scoperta della Programmazione Lineare.

Cos’è il Travelling Salesman Problem?

Nell’introduzione abbiamo visto come il problema che stiamo analizzando nasca da un contesto prettamente concreto. Per cercare di capire come risolverlo la prima cosa da fare è sempre la stessa: fare conoscenza con il problema. Per fare questo, solitamente, i matematici non seguono alla lettera le regole del galateo, ma si mettono a dividere tutto in pezzi e a dare un nome ad ogni componente.

Noi da aspiranti matematici faremo lo stesso!

Definiamo quindi un insieme contenente tutti i punti da raggiungere, e un insieme T che rappresenti i possibili tragitti con la loro lunghezza: se esiste un percorso che va da a   di lunghezza .

Utilizzando il vettore , di cui ogni componente rappresenta un tragitto all’interno del percorso considerato (vedremo poi meglio come è fatto), definiamo una funzione che assegna ad ogni percorso la sua lunghezza.

Il problema si può ora vedere in modo più formale come: trovare il vettore   tale per cui  sia minimo.

Forse tutto questo matematichese ti ha confuso un po’, ma se provi a rileggere il tutto con attenzione ti accorgerai che non abbiamo fatto altro che riscrivere in formula il problema di prima.

Ora puoi dire che come era scritto inizialmente era molto più semplice (e ti daremmo ragione), ma questa nuova veste dà al quesito un aspetto più trattabile da un punto di vista matematico/computazionale.

Per trovare una soluzione al problema del commesso viaggiatore andiamo a scoprire uno degli strumenti più potenti nel campo dell’ottimizzazione lineare: la Programmazione Lineare.

Preliminari alla Programmazione Lineare

Prima di riuscire a riscrivere il problema dobbiamo introdurre il concetto di funzione lineare.

Diciamo funzione lineare una funzione del tipo dove .

Guardandola bene possiamo capire che il termine lineare significa semplicemente che l’argomento della funzione è di primo grado.

Analogamente diciamo che un vincolo è lineare se è nella forma  dove e .

Ricerchiamo l’ottimo con la PL

A questo punto vogliamo esprimere un percorso tramite il vettore . Come facciamo?

Una possibile soluzione è la seguente: definiamo una variabile per ogni possibile tragitto. Ad esempio identifica il tragitto dal punto  al punto . Ora poniamo  uguale a 1 se il tragitto è compreso nel percorso considerato, 0 altrimenti.

Ricordandoci del significato di  possiamo finalmente costruire la nostra tanto sudata funzione lineare .

Ci resta soltanto da porre delle condizioni che obblighino il percorso analizzato a passare per tutti i punti.

Ne servono 3!

, ossia ogni punto ha solo un percorso “entrante” …

, ossia ogni punto ha solo un percorso “uscente”….

e

, ossia le uniche possibilità sono utilizzare un tragitto (1) o non considerarlo (0).

(Per correttezza si dovrebbe utilizzare una quarta condizione per evitare la presenza di sottocircuiti non connessi che però qui tralasciamo per semplicità).

Formalizzazione del problema del commesso viaggiatore

Riassumendo tutto quello che abbiamo detto il Travelling Salesman Problem diventa:

sotto le condizioni

Molto bene… E ora?

Abbiamo dato una veste molto elegante al nostro problema, ma come lo risolviamo?

Il bello della programmazione lineare è proprio questo, “non ci interessa”!

Una volta scritto il problema secondo questo formalismo è sufficiente delegarlo ad un buon risolutore.

Qui trovate una spiegazione di come risolvere problemi del genere utilizzando Excel.

Per capire cosa succede all’interno di questi applicativi bisognerebbe aprire una lunghissima e complessa parentesi sul metodo del simplesso. Lascio ai più curiosi l’occasione di approfondire (poi se serve un aiuto scriveteci pure 🙂 ).

Il lato oscuro del commesso viaggiatore

Siamo quasi alla fine e sembra ormai che per i servizi di spedizione il problema delle consegne sia stato risolto. Tutto va bene finché il numero di punti di consegna non aumenta e il nostro metodo non riesce più a fornire una soluzione.

La modellizzazione che abbiamo fatto è infatti NP-completa e quindi il tempo di esecuzione del nostro metodo cresce in modo non polinomiale (e quindi MOLTO velocemente) al crescere del numero di punti analizzati.

E’ proprio questa difficoltà che apre lo scenario ad altre tecniche di risoluzione. L’ideale sarebbe trovare un algoritmo polinomiale, ma non sappiamo ancora se questo è possibile (l’argomento della NP vs P è stato accennato recentemente qui).

Per ora sembra che, nel caso in cui il percorso debba passare per un numero elevato di punti, non si possa trovare la soluzione ottima al problema del commesso viaggiatore in tempi ragionevoli. In pratica quindi si deve abbandonare la speranza di trovare l’ottimo ed accontentarsi di una sua approssimazione.

Futuri viaggi del commesso

Entriamo così nel mondo dell’euristica dove si va a cercare di trovare dei buoni candidati per ottenere l’ottimo utilizzando tecniche di tipo probabilistico/stocastico.

Queste metodologie sono molto interessanti e suggestive. Nel futuro andremo quindi a richiamare il nostro commesso per partire con lui in un nuovo viaggio… alla scoperta del Calcolo Stocastico!

Come abbiamo visto in questo articolo spesso molti problemi della vita quotidiana vengono affrontati facendo uso del sapere matematico.

Questo mi fa pensare che chi dedica la vita allo studio della matematica non sia poi così folle!

Spero che l’articolo ti sia piaciuto, a presto 😉

Marco

Caffè matematico n° 2 – Il cubo di Rubik – Il gioco del Demonio

Benvenuti a questo secondo caffè matematico: oggi parliamo un po’ di algebr… ehm, del cubo di Rubik! Dato che il tempo a disposizione è poco (il tempo di un caffè appunto 😉 ) sarò breve, ma l’argomento è molto interessante e merita di essere approfondito, pertanto prometto di scriverne al riguardo tra non molto ;).

Il cubo di Rubik

Praticamente tutti conoscono il famosissimo cubo del professore Ernő Rubik. Esso è probabilmente il gioco più venduto della storia ed è considerato da coloro che non sono mai riusciti a risolverlo un vero rompicapo.

Ma cosa vuol dire effettivamente risolverlo? Beh, matematicamente si potrebbe dire che il problema è ben posto, cioè che la soluzione esiste ed è unica. Essa altro non è che il procedimento algoritmico che riesce a permutare i singoli blocchetti in modo che su tutte le facce compaia un solo colore, diverso per tutte e 6 le facce.

Un po’ di algebra

Ma in quanti modi differenti si possono permutare le facce del cubo? Beh, facciamo un po’ di calcoli… Ci sono 3 strati verticali e 3 orizzontali in ogni faccia e possono essere ruotati singolarmente 3 volte, fino a tornare alla posizione originaria. Dunque siamo già a 3x3x3 possibilità di modificarlo. Tutto questo va considerato per 6 facce. Giusto? SBAGLIATO! Attenzione! Se ruotate una faccia, anche tutte quelle intorno vengono di conseguenza modicate! Trovare tutte le possibili permutazioni non è purtroppo così facile come sembra…

Si potrebbe andare avanti parecchio, ma meglio se vi do la soluzione… Si può dimostrare che il numero di configurazioni differenti che un cubo di Rubik può assumere è dato da:

227314537211=43252003274489856000,

cioè circa 0.4*1020. Immaginiamo che per guardare ogni possibile configurazione ci voglia un secondo. 60 fanno un minuto. Per 60 e siamo a un’ora e così via… Se adesso dividiamo 43252003274489856000 per i secondi che ci sono in un anno, otteniamo 1370 miliardi. Il nostro Universo ha poco meno di 14 miliardi di anni, la terra 4. Il sole ne brucerà per circa altri 5. Insomma, riuscire ad elencare tutte le configurazioni di un cubo di Rubik sembra un’impresa assolutamente impossibile.

Giochi senza frontiere

Questo fatto però non deve scoraggiarci: per trovare la soluzione al rompicapo infatti non è necessario conoscere tutte le possibili configurazioni, ma basta saper destreggiarsi tra un po’ di esse con sufficiente abilità. Tra le tante soluzioni che si possono trovare in rete, tutte quante hanno come denominatore comune l’approccio algoritmico: non importa avere un’idea geniale e ogni volta rimettersi a pensarne una nuova: basta solo osservare la configurazione in cui il cubo si trova e procedere algoritmicamente sistemando gruppi di tasselli alla volta.

Attualmente nessuno riesce a farlo in meno di 4 secondi e 73. Voi ci siete mai riusciti? In quanto?

A mercoledì prossimo con il prossimo caffè 😉

Au revoir

Erik

ceterum censeo festascienze esse facendam

Che cos’è un paradosso? Scopri alcuni importanti paradossi e il significato del termine

Che cos’è un paradosso? Spesso si sente nominare questa parola che assume significati diversi in base al contesto. Con questo articolo ho quindi l’obiettivo di fare chiarezza su questo concetto. Intanto ti suggerisco un libro molto interessante su questo argomento: C’era una volta un paradosso. Storie di illusioni e verità rovesciate.

Ovviamente non sarà un semplice articolo teorico, ma ci saranno anche svariati esempi.

Prima di iniziare, ti consiglio di andarti a leggere questi articoli che avevo pubblicato ormai qualche mese fa. Riguardano alcuni interessanti paradossi:

Il paradosso di Monty Hall

Il paradosso del compleanno

Il paradosso di Russel

Il paradosso del mentitore

Direi che per ora è abbastanza. 🙂

Possiamo iniziare con un po’ di teoria e definizioni.

Introduzione

Che cos’è un paradosso per il dizionario? Ecco qui:

Proposizione che per forma o contenuto si oppone all’opinione comune o all’esperienza quotidiana, riuscendo perciò sorprendente o bizzarra.

Non male come definizione, ma noi vogliamo di più. Rimangono infatti alcune questioni in sospeso leggendo le righe qui sopra. Cosa vuol dire opporsi all’opinione comune? Quando un’affermazione è definibile “bizzarra”?

Vediamo un’altra definizione data da Mark Sainsbury. Per lui, si tratta di “una conclusione evidentemente inaccettabile, che deriva da premesse evidentemente accettabili per mezzo di un ragionamento evidentemente accettabile”.

Forse un po’ contorta, ma fornisce abbastanza l’idea di ciò di cui siamo parlando.

Noi, che siamo matematici e ci chiediamo il perchè di ogni cosa, vogliamo andarne più a fondo. Giusto?!

Il paradosso abbiamo visto che è sostanzialmente un’affermazione insolita. Definiamo paradosso una proposizione (o tesi) che, partendo da determinate ipotesi, arriva a delle conclusioni che sono inaspettate e/o non verosimili.

In senso logico-linguistico indica un ragionamento contraddittorio che dev’essere accettato o un ragionamento corretto che porta ad una contraddizione.

In matematica è invece una proposizione eventualmente dimostrata e logicamente coerente, ma lontana dall’intuizione.

A breve pubblicherò una puntata del podcast sui paradossi e la potrai ascoltare qui o sulle varie piattaforme di podcasting.

In filosofia ed economia il termine paradosso è usato spesso anche come sinonimo di antinomia. In matematica invece si distinguono i due termini: il paradosso consiste in una proposizione eventualmente dimostrata e logicamente coerente, ma lontana dall’intuizione; l’antinomia, invece, consiste in una vera e propria contraddizione logica.

Analizziamo un semplice paradosso per capire meglio le definizioni appena lette. Il paradosso che stai per leggere, si chiama paradosso di Achille e la Tartaruga. Esso è frutto della mente del filosofo greco Zenone.

Il paradosso racconta di una corsa tra Achille ed una tartaruga che parte con 500 metri di vantaggio. Sulla carta non c’è storia. Achille è destinato a superare la testuggine. Ed anche al momento del via Achille parte molto più veloce dell’animale.

Il Pieveloce copre 500 metri mentre la tartaruga ne ha percorsi solo 50. Ha quindi 50 metri di vantaggio sull’eroe. Achille copre 550 metri, ma la tartaruga nel frattempo ne ha fatti altri 5. Achille recupera i cinque metri, ma la tartaruga ne ha fatto 0.5.

E così via, in una serie di distanze sempre più piccole tra Achille e la tartaruga, con quest’ultima che andrà sempre più veloce. Logicamente Achille supererà l’animale ma, con il suo paradosso, Zenone vuole dimostrarci quanto la scomposizione dei numeri sia potenzialmente infinita.

Questo esempio penso sia abbastanza semplice da capire, ma allo stesso tempo davvero utile per interpretare le definizioni di “paradosso” che ho scritto nelle prime righe dell’articolo.

Nella concezione comune, infatti, Achille è più veloce della tartaruga. Viene quindi logico pensare che lui superi la tartaruga. Da un punto di vista matematico, però, risulta chiaro che (con questi dati) la tartaruga riesca sempre ad avere un vantaggio su Achille, seppur infinitesimo.

Un po’ strano, no?! Non preoccuparti perchè ne vedremo di più strani 😉

Un po’ di storia

Il più antico paradosso si ritiene essere il paradosso di Epimenide, in cui il Cretese Epimenide afferma: “Tutti i cretesi sono bugiardi”. Non volendo dilungarmi troppo in questo articolo, non lo approfondisco nelle prossime righe. Tuttavia, puoi leggere un intero articolo riguardo a questo paradosso: Il paradosso del mentitore. Esso è esattamente il paradosso che ti ho citato qualche riga più sopra.

Diciamo che il concetto di paradosso non ha una vera e propria origine, è intrinseco a noi e al nostro modo di ragionare. Ci sono tracce di paradossi sin dall’inizio della storia scritta, ma probabilmente sono solo i primi ad essere documentati.

Sono abbastanza sicuro che si parlasse di paradossi, magari definendoli in maniere diverse, già da prima, molto prima!

Se ti interessa approfondire questo aspetto dei paradossi, potresti trovare qualche informazione interessante su questo libro:

Paradossi, lo trovi qui: https://goo.gl/JfBLQ6

Se non ti spaventa l’inglese, invece, ho trovato un PDF di quasi 200 pagine davvero fantastico sui paradossi e sulla loro origine che tratta molti aspetti molto interessanti dell’argomento. Per accederci, ti basta inserire la tua email qui sotto (se ti iscrivi, riceverai una mia email ogni mattina alle 8, con alcuni indovinelli, curiosità e consigli)

3 paradossi famosi

Concludiamo questo articolo, per me molto interessante, citando tre dei paradossi più famosi e interessanti. Ovviamente non ti parlerò di quelli a cui ho già dedicato un intero articolo 😉

Paradosso di Don Chisiotte (Miguel Cervantes, 1547 – 1616):

“Una guardia chiede a tutti i visitatori ‘Perché sei venuto?’ Se il visitatore risponde in modo veritiero, tutto bene. Se risponde falsamente, viene impiccato. Un giorno un visitatore rispose: ‘Vengo per essere impiccato’. Cosa dovrà fare la guardia ?”
Se non lo avesse fatto impiccare, avrebbe voluto dire che aveva mentito e che quindi doveva essere impiccato. Ma se lo avesse fatto impiccare, avrebbe voluto dire che aveva detto la verità e quindi non avrebbe dovuto essere impiccato.

Fonte: furiacervelli

Il condannato a morte

“In un paese esotico governato da un tiranno abbastanza stupido ma con l’amore per i giochini matematici un bel giorno si presentano alla corte di sua maestà un gendarme e il più illustre matematico del paese. Il gendarme accusa il matematico di essere stato colto sul fatto in uno dei più atroci reati, non importa quale, e il matematico in effetti non fa altro che ammettere le sue colpe… La pena prevista è la condanna a morte.
Tuttavia il tiranno non vuole perdere una delle mente più brillanti del paese e così gli concede un modo per salvarsi la vita, esprimendo così la sua sentenza di condanna:
“Sarai rinchiuso oggi nelle prigioni del castello e verrai ghigliottinato un giorno qualsiasi a partire da oggi nell’arco di una settimana, ma la cosa più terribile è che non potrai mai prevedere con certezza il giorno della tua morte!!!”.
Ebbene, il matematico riuscì con facilità a dimostrare l’inapplicabiltà della condanna ed ebbe così salva la vita.”
In questo modo il condannato non potrà essere impiccato il settimo giorno perché altrimenti il sesto saprebbe già in anticipo il giorno in cui morirà. Di conseguenza anche se venisse ucciso il sesto giorno saprebbe in anticipo la data dell’esecuzione, che non potrebbe avvenire il giorno seguente.

Continuando in questo modo il prigioniero potrebbe concludere che non sarà mai ucciso perché altrimenti l’affermazione del giudice risulterebbe falsa. Questo è un caso interessante di come la realtà possa essere diversa dalla logica!

L‘impercettibile raddoppiamento notturno

Supponiamo che la scorsa notte, mentre tutti dormivamo, tutto l’universo abbia raddoppiato le proprie dimensioni. Vi sarebbe un qualche modo di accorgersi di ciò che è successo?
Chiaramente NO!

Questo non me la sento di affrontarlo in qualche riga, penso di utilizzarlo per iniziare un futuro articolo sulle dimensioni. Argomento non facile e per questo avrò bisogno di parecchi esempi 😉

Ovviamente, se non l’hai ancora letto, puoi informarti anche sul paradosso dell’albergo di Hilbert. E’ davvero molto interessante e ne ho parlato qui: L’albergo di Hilbert.

Per questo articolo, è tutto. Se hai consigli, domande o critiche da farmi, dimmi pure. Puoi lasciare un commento qui sotto, contattarmi sulla pagina Facebook MATHONE o inviarmi una mail a list@mathone.it.

Alla prossima! 😉

Algoritmo moltiplicazione egizia

Eccoci arrivati all’approfondimento del secondo algoritmo citato nell’articolo precedente, l’algoritmo per la moltiplicazione utilizzato nell’antico Egitto.

L’articolo in cui l’ho introdotto è il seguente (se non l’hai ancora letto ti consiglio di darci un’occhiata) : Algoritmi antichi e curiosi .

Ecco qui la pseudocodifica dell’algoritmo di cui andremo a parlare tra poco:

a,b interi

z = 0

finchè (a>0):

se a dispari -> z=z+b

a=a//z (divisione intera)

b=b*2

risultato z

Prima di cominciare con un breve approfondimento dedicato, ho pensato di introdurre l’argomento con un video in cui ci sono alcuni esempi. I passaggi seguiti non sono proprio evidenti ma ti assicuro che è esattamente ciò che viene definito dall’algoritmo scritto qui sopra.

Penso che possa anche risultarti più chiaro il funzionamento.

Andiamo ora a vedere il funzionamento dell’algoritmo “ragionando in base 2”. Ti dico questo perchè il codice prima citato può essere adattato ad una qualsiasi base.

I due casi che si possono presentare in prima battuta sono i seguenti:

  1. a pari
  2. a dispari

Scriviamo quindi a=2a’ nel primo caso e a=2a”+1 nel secondo.

Analizziamo ora il primo caso.

In tali condizioni z diventerà uguale alla seguente espressione: (2a’)b = a’ (2b) in quanto moltiplicare a*b o o (a/2)*(2b) è la stessa cosa.

Pertanto le operazioni da eseguire dopo il “finchè” nel primo caso non sono rilevanti più di tanto.

Ma andiamo ora ad analizzare il secondo caso, ossia con a dispari.

z=ab=(2a”+1)b=2a”b + b = a” (2b) +b

Ora quindi siamo nelle stesse condizioni del caso precedente per il primo addendo, abbiamo però una addendo “b” in più. Per cui possiamo dire di fare (a/2)*(2b) ed assegnare tale espressione alla variabile z, ricordandoci però di quel “+b” che compare nell’espressione prima citata.

Per cui nel caso a sia dispari, mi vado a ricordare di b e lo sommo a priori a z.

Andando quindi a riassumere il tutto, che probabilmente non ti è ancora del tutto chiaro (è difficile spiegare un algoritmo scrivendo 🙂 ), diciamo che l’algoritmo della moltiplicazione egizia si basa su un un principio unico.

Esso è il seguente: A * B = (A/2) * (2B).

Questo è infatti ciò che viene eseguito a priori in questo algoritmo.

Tuttavia nel caso A sia dispari, nel dividere per 2 (con la divisione intera) si andrebbe a perdere qualcosa. Pertanto, siccome so che succede sempre così, mi faccio trovare pronto e sommo a priori B a z. Così da non perdermi nulla nella divisione intera di a.

Spero di averti chiarito abbastanza il comportamento di questo algoritmo.

In caso tu abbia dubbi, critiche o suggerimenti (come al solito) non esitare a commentare o contattarmi.

Alla scoperta di algoritmi antichi e curiosi

Se hai a che fare con la matematica frequentemente, la dimestichezza con gli algoritmi certo non ti manca 😉 Tuttavia, per mettere tutti i lettori di questo articolo su un punto di partenza più o meno equo, ho pensato di iniziare il tutto con una “definizione” di algoritmo.

Un algoritmo è un procedimento che risolve un determinato problema attraverso un numero finito di passi elementari.

Questa non è una vera e propria definizione, in quanto per essere completa dovrebbe fornire anche un bell’elenco di proprietà di cui deve godere un algoritmo. Tuttavia ritengo che, per quello che andrai a leggere nelle prossime righe, questa breve introduzione al concetto di algoritmo sia più che sufficiente.

Di algoritmi noti ve ne sono un’infinità e, ogni giorno, programmatori, matematici, fisici e ingegneri di tutto il mondo ne inventano di nuovi per risolvere i problemi che si trovano ad affrontare quotidianamente al lavoro.

Nonostante molti algoritmi siano noti ai più, ritengo che ve ne siano alcuni davvero curiosi, intriganti e per lo più finiti nel dimenticatoio.

Certamente se alcuni di questi sono stati col tempo tralasciati c’è un motivo, il principale è senz’altro la loro inefficienza (ossia incapacità di arrivare ad un risultato in pochi passi).

Tuttavia li trovo curiosi da un punto di vista teorico e metodologico.

Partiamo quindi con un semplice elenco dei 4 algoritmi antichi e curiosi che ti andrò a presentare, seppur brevemente (non escludo di trattarli in modo approfondito e esteso in articoli dedicati in futuro), nelle seguenti righe.

Lista dei 4 algoritmi antichi e curiosi trattati di seguito:

  • Moltiplicazione egizia
  • Algoritmo di Euclide per il calcolo dell’MCD
  • Algoritmo babilonese calcolo radice quadrata
  • Moltiplicazione alla russa

Andiamo ora a trattarli brevemente uno per uno 🙂

Algoritmo moltiplicazione egizia

Questo algoritmo è molto antico e anche intrigante, infatti permette di fare la moltiplicazione di due numeri naturali in una maniera che apparentemente può sembrare davvero misteriosa.

Prima di spiegare come funziona l’algoritmo, ti faccio vedere un procedimento svolto, vediamo se ti è subito chiaro 😉

Ora ti scrivo l’algoritmo in un linguaggio comprensibile (pseudocodifica):

a,b interi

z = 0

finchè (a>0):

se a dispari -> z=z+b

a=a//z (divisione intera)

b=b*2

risultato z

Se provi a tracciare o comunque ad eseguire manualmente questo algoritmo, probabilmente riesci ad accorgerti che si basa sulla notazione in base 2. Tuttavia preferisco non dimenticare informazioni importati per scrivere poco, quindi a questo, come ai seguenti algoritmi, dedicherò un intero articolo in futuro. Per ora quindi accontentati di queste informazioni, oppure ti basta digitare ‘moltiplicazione egizia’ su Google e troverai le risposte alle tue domande 😉

Algoritmo di Euclide per il calcolo dell’MCD

Questo non è per nulla un algoritmo inefficiente, infatti permette di trovare l’MCD tra due numeri in molti meno passi rispetto al comune procedimento. Infatti invece di trovare prima i divisori di un numero, trovare i divisori del secondo e cercare il più grande divisore in comune, l’algoritmo che ti sto per presentare utilizza solo somme e differenze 🙂

Partiamo, questa volta, con la pseudocodifica:

a,b naturali

finchè a!=b (!= significa diverso):

se a>b allora a=a-b

altrimenti b=b-a

risultato a

Provare per credere 😉 con questi semplici conti arriverai a trovare facilmente l’MCD tra due numeri. E’ certamente meno intuitivo del procedimento che comunemente fai per trovare il massimo comune divisore tra due numeri, tuttavia nella scrittura di codici (programmazione) questo algoritmo risulta spesso molto utile.

Prova a capire come fa a ‘funzionare’ e scrivilo nei commenti! Comunque nelle prossime settimane pubblicherò un articolo dedicato a questo specifico algoritmo.

Ti consiglio quindi di iscriverti alla newsletter per rimanere aggiornato sulle nuove pubblicazioni, ricevere anteprime e contenuti riservati! Ti basta compilare i due seguenti campi:



Algoritmo babilonese calcolo radice quadrata

Se te lo sei perso, mi interessa informarti che in passato ho scritto un articolo illustrante l’algoritmo (comunemente indicato) per calcolare la radice quadrata. Lo puoi trovare qui.

Ora però te ne illustro un altro, più banale da apprendere, facile da applicare e molto efficiente ma sostanzialmente in disuso. Fu introdotto dai babilonesi, pensa che storia che ha questo algoritmo alle spalle! 😉 Perchè dimenticarlo?

Ecco la sua pseudocodifica:

x,a naturali (x è il numero di cui si vuole estrarre la radice, a un’approssimazione per difetto                    che si intuisce, in caso non se ne abbia idea a=1 )

finchè non è abbastanza preciso il risultato:

t=x

r=(t+a)/2 (media aritmetica)

s=x/r (media armonica)

t=r

a=s

risultato s

 

Le operazioni dopo il finchè puoi anche decidere a priori di eseguire 3-4 volte, tanto la velocità con cui s converge alla radice effettiva di x è davvero elevata. Prova per esempio con la radice di 2, vedrai che già dopo 3 iterazioni avrai una precisione di 5-6 cifre dopo la virgola.

Moltiplicazione alla russa

Un algoritmo relativo alla moltiplicazione, te l’ho già presentato, tuttavia trovo interessante ed intuitivo anche un secondo algoritmo per eseguire i prodotti tra due numeri naturali. Sto parlando della moltiplicazione alla russa. Sostanzialmente il metodo si basa sul raddoppiare il primo fattore e dimezzare il secondo, finchè questo non diventa 1. In caso di numero dispari, ad essere diviso sarà n-1. Il risultato del prodotto è infine la somma dei numeri disposti sotto il primo fattore, corrispondenti ai numeri  dispari della seconda colonna.

Immagine presa da http://www.aliperlamente.it/ED/Moltiplicazioni/Molt.russa.pdf

 

Bene, spero di averti incuriosito ed interessato con questi cenni a 4 algoritmi antichi e curiosi. Se ne conosci altri degni di nota, ti prego di contattarmi nei commenti, sulla pagina Facebook o nel modulo per contattarmi raggiungibile da qui.

Spero possano nascere discussioni interessanti 😉

Paradosso del compleanno

Quante persone ci devono essere in una stanza perchè la probabilità che due di loro siano nate lo stesso giorno sia maggiore al 50% ?

Se sei già iscritto alla newsletter, hai già ricevuto una mail in cui ti ho introdotto al Paradosso del compleanno. Se non sei ancora iscritto, intanto ti invito a farlo compilando il modulo qui sotto, poi ti consiglio di aspettare a proseguire la lettura e provare a trovare una risposta alla domanda qui sopra.

Se non sai che cosa sia un paradosso, ti consiglio di leggerti l’articolo: Che cos’è una paradosso?

Bene, spero che tu abbia provato a trovare una risposta alla domanda del Paradosso del compleanno:) .

Ho pensato che fosse meglio illustrare la spiegazione passo per passo, basandomi su un ragionamento ad esclusione che penso sia naturale seguire.

Quindi…partiamo!

Per semplificare leggermente la situazione, non considero la possibilità che un anno possa essere bisestile. Prendiamo quindi come riferimento un anno di 365 giorni. Comunque, se vuoi essere più preciso, puoi risolvere il paradosso del compleanno anche considerando la possibilità dell’anno bisestile, non si complicherà nulla di molto 😉 .

Il primo numero che facilmente ti è saltato in mente è 366. Infatti necessariamente se ci sono 366 persone, con 365 compleanni disponibili, due di queste sono certamente nate lo stesso giorno. Tuttavia qui siamo di fronte ad una probabilità che l’evento si verifichi che è pari a 100%. Il problema ci dice di trovare il numero sufficiente ad avere una probabilità maggiore al 50%.

Iniziamo quindi a fare qualche taglio sul numero di persone…

Per evitare di perdersi in inutili conti, mi avvicino un po’ alla soluzione, senza però dirti ancora il risultato finale. Ti sembrerà strano infatti, ma con sole 57 persone si ha già il 99% di probabilità che due persone siano nate lo stesso giorno. Strano, vero? Si chiama paradosso del compleanno per qualcosa 😉

Tuttavia per avere poco più del 50% di probabilità ne bastano molte meno…

Ma ora veniamo al ragionamento matematico da seguire per arrivare alla soluzione. C’è infatti un piccolo accorgimento da seguire: non ragionare sulla singola persona ma ragionare a coppie. Infatti non ci interessa in che giorno sono nati i singoli, ci interessa che due dei presenti siano nati lo stesso giorno.

Iniziamo quindi a considerare il numero di coppie possibili con persone presenti.

Partiamo dal caso in cui vi siano tre persone, mettiamo che siano P1, P2, P3. Le coppie possibili sono quindi (P1,P2), (P1,P3) e (P2,P3). Ora con un ragionamento analogo, si può arrivare a dire che con 4 persone (P1, P2, P3, P4) si possono formare al massimo 6 coppie. Se non te ne sei ancora accorto, si può trovare il numero delle coppie possibili applicando una semplice formula, che coinvolge l’utilizzo del fattoriale (!).

La formula in questione è la seguente:

dove nel nostro caso n è il numero delle persone presenti e k è 2, ovvero la dimensione dei gruppi in cui vogliamo combinare le persone.

Non mi soffermo più di tanto sull’aspetto teorico (magari in futuro potrei dedicare un po’ di articoli a questi argomenti..), quindi se non ti riesci a spiegare questi risultati, ti consiglio di ricercare su Google “Combinazioni semplici”, troverai le risposte a tutte le tue domande 🙂 .

Ora prova a calcolare quante coppie possibili ci sono con 57 persone…

Adesso inizia a sembrarti un po’ più plausibile che con 57 persone ci sia quasi la certezza che due siano nate lo stesso giorno?

Ma veniamo finalmente agli ultimi passaggi, quelli che ci porteranno ad arrivare al risultato esatto.

Ora diventa un fatto di puri calcoli, infatti la strategia da adottare te l’ho già spiegata. Devi sostanzialmente cominciare con una coppia, continuare ad aggiungere gente (il nostro n) e vedere come cambia la probabilità. Tuttavia c’è un ultimo consiglio che posso darti. Non ti consiglio di controllare la probabilità di condividere un compleanno, ma ti suggerisco di calcolare la probabilità che ogni nuova persona abbia un compleanno diverso da quelle già presenti.

Quindi, partendo da una persona sola, puoi vedere facilmente come la probabilità che la seconda persona non sia nata lo stesso giorno della prima sia del 364/365. La terza persona ora avrà un giorno in meno (disponibile) rispetto alla precedente, quindi ha a disposizione 363 giorni. Tuttavia essendo la nascita di una persona non influenzata del compleanno degli altri, nella teoria della probabilità si impara che due eventi del genere, affinchè accadano insieme hanno una probabilità del 364/365*363/365=0,9918, cioè del 99,18%.

Ricapitolando il ragionamento, quindi, con tre persone si ha la probabilità del 99,18% che queste tre siano nate in giorni diversi.

Procedendo analogamente, aggiungendo persone, magari evitando di fare troppi conti per niente (quindi provando ad aggiungere 4-5 persone ogni volta), dovresti arrivare a scoprire il numero di persone sufficiente per avere una probabilità maggiore al 50% che due di questa siano nate lo stesso giorno.

Dai conti, dovrebbe risultarti che sono necessarie 23 persone per avere una probabilità maggiore al 50%. Infatti moltiplicando le prime 23 frazioni (rappresentanti le probabilità che l’evento non si verifichi), come abbiamo fatto prima, si giunge a dire che con 23 frazioni il prodotto è 0,493. Ossia con 23 persone c’è il 49,3% di probabilità che due non siano nate lo stesso giorno.

Quindi in questa situazione ci sarà il 50,7% di probabilità che due siano nate lo stesso giorno, proprio come volevamo noi.

Bene, il percorso che abbiamo dovuto fare per arrivare alla soluzione non è stato molto breve, tuttavia le analisi fatte non hanno nulla di complicato al loro interno.

Quindi se nella lettura hai accumulato dubbi, richieste o suggerimenti, ti invito a commentare o a contattarmi con l’apposito form disponibile qui. Anche una rilettura potrebbe esserti utile ;).

Ti sarei molto grato anche se condividessi l’articolo con i tuoi amici.

Se vuoi un’ulteriore spiegazione puoi guardare anche questo video che trovo molto ben fatto:

Spero di essere stato abbastanza chiaro, alla prossima!

 

 

Il paradosso del mentitore

Questa frase è falsa

 

Hai letto attentamente la frase citata qui sopra? Non sembra essere una frase molto complicata, giusto? 😉 Questo è quello che viene chiamato il paradosso del mentitore.

Ora ti faccio un piccola domanda e ti chiedo uno sforzo un po’ più grande: Sapresti dimostrarmi se la frase sopra citata è vera o falsa?

Hai provato a pensare ad una possibile dimostrazione/spiegazione?

Bene 🙂 sono contento che, incuriosito, hai deciso di proseguire la lettura. Purtroppo però devo dirti che non c’è alcun modo per rispondere alla domanda che ti ho posto. Analizziamo quindi i due casi possibili relativi alla proposizione prima citata, il caso in cui sia vera e quello in cui sia falsa.

  • Se fosse vera, allora la frase non sarebbe veramente falsa (la verità della proposizione non invalida la falsità espressa nel contenuto della proposizione).
  • Se invece la proposizione fosse falsa, allora il contenuto si capovolgerebbe (è come se dicesse “Questa frase è vera“) quando abbiamo appena affermato il contrario.

Spero che tu non ci sia rimasto male…comunque sono sicuro che ci hai pensato almeno un attimo alla possibilità che non vi sia risposta a tale domanda. Dopotutto…il titolo dell’articolo contiene la parola paradosso 🙂

Questo è conosciuto come paradosso del mentitore, o meglio antinomia del mentitore. Talvolta puoi trovarlo anche sotto un nome ancor più suggestivo: Paradosso di autoreferenzialità.

Questo paradosso è stato di particolare interesse per molti personaggi illustri nel corso della storia, alcuni di essi hanno anche provato a fornire un’elaborata e spesso poco lineare soluzione al problema che ti ho posto prima. Ti lascio la possibilità di documentarti liberamente su tali soluzioni, se vuoi a questo link ne potrai leggere alcune 😉

Spero che l’articolo ti abbia incuriosito e che ti abbia lasciato un po’ perplesso, perchè in fondo è questo il bello di un teorema, di un paradosso e della matematica, subito non sono del tutto chiari, ma dopo sono affascinanti 🙂 Lascia pure un commento se hai dubbi, suggerimenti o critiche da pormi, sarò lieto di risponderti.

Il paradosso di Russell

Il paradosso di Russell, formulato dall’omonimo Bertrand Russell tra il 1901 e il 1902, è una delle antinomie più importanti della storia della filosofia e della logica. E’ anche conosciuto dai più come il paradosso del barbiere.

In questa sede ho pensato che fosse più appropriato farne una trattazione più generalizzata, limitandomi quindi ad una semplice enunciazione del paradosso in termini della teoria degli insiemi.

Il paradosso di Russell dice quindi che:

L’insieme di tutti gli insiemi che non appartengono a se stessi appartiene a se stesso se e solo se non appartiene a se stesso. Formalmente,

Ora, ho pensato di limitarmi ad enunciare tale paradosso in maniera formale, perchè credo che a fini divulgativi sia più interessante presentarlo proprio come il paradosso del barbiere che, senza particolari sforzi, può essere ricondotto all’enunciato sopra citato.

Il paradosso del barbiere è il seguente:

Un certo Villaggio ha tra i suoi abitanti un solo barbiere. Egli è un uomo ben sbarbato che rade tutti – e unicamente – gli uomini del villaggio che non si radono da soli. Questi sono i fatti. La domanda è: << Chi rade il barbiere?? >>

Ora potresti pensare, se per caso non avessi mai sentito parlare di questa antinomia, che il barbiere si rada da solo. Tuttavia in tal caso, essendo che lui stesso è un barbiere, lui non dovrebbe essere in grado di radersi da solo in quanto si fa radere dal barbiere. Nel caso in cui invece lui supponga di non essere in grado di radersi e decida di andare a farsi radere dal barbiere, lui stesso, sarebbe necessariamente in grado di radersi da solo.

Forse non ti è proprio chiaro, tuttavia questo è evidentemente un paradosso, una situazione senza alcuna via d’uscita. Sostanzialmente è una contestualizzazione ad una situazione verosimile dell’effettivo paradosso di Russell prima citato.

 

Per adesso ritengo sufficiente averti introdotto a questo paradosso, quindi ti lascio qui di seguito qualche riferimento nel caso tu voglia approfondire personalmente l’argomento, comunque penso proprio che in futuro ci ritornerò su questo tema, dato che mi attrae parecchio.

Per un po’ di storia clicca qui

Per una spiegazione video del paradosso del barbiere clicca qui

Per un topic dedicato alla spiegazione formale ma non troppo complicata del paradosso di Russel clicca qui

Bene, spero di esserti stato utile e di averti stimolato almeno un po’ di stupore e curiosità. Questo articolo non aveva infatti lo scopo di trattare ogni tematica relativa all’argomento, ma semplicemente vuole metterti a conoscenza di questa bizzarra situazione e stimolarti a pensarci su.

Se ti è stato utile o comunque se ritieni l’articolo interessante mi renderesti molto felice se lasciassi un tuo commento qui sotto e/o condividessi l’articolo con i tuoi amici 😉

Detto ciò ti saluto, spero che possa nascere qualche discussione interessante qui o sulla pagina Facebook MATHONE.