Archivi categoria: Algoritmi e paradossi

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:

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:

Quando Achille percorre i 10 metri iniziali di vantaggio, la tartaruga ne ha fatti altri 5 (“nuovo svantaggio”)
Quando recupera anche questi 5, la tartaruga ne ha fatti altri 2.50m
In seguito, nel tempo che Achille recupera questi 2.5m la Tartaruga ne fa 1.25m
Poi percorrono rispettivamente 2.5m e 0.625m
Quindi 0.625m e 0.3125m (Anche se sarebbero difficili da misurare, supponiamo però di riuscire senza errori)
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

1 Replica

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.¹

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. [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

Lascia una risposta

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”….

, 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

Lascia una risposta

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:

2²⁷3¹⁴5³7²11=43252003274489856000,

cioè circa 0.4*10²⁰. 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

3 Repliche

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)

[optin_box style=”10″ alignment=”center” disable_name=”Y” email_field=”email” email_default=”Inserisci la tua email” integration_type=”mailchimp” thank_you_page=”http://web.dfc.unibo.it/paolo.leonardi/materiali/cs/Paradossi.pdf” already_subscribed_url=”http://web.dfc.unibo.it/paolo.leonardi/materiali/cs/Paradossi.pdf” list=”aeff8c6727″ name_field=”FNAME” name_default=”Enter your first name” name_required=”Y” opm_packages=””][optin_box_field name=”headline”]Here’s The Headline For The Box[/optin_box_field][optin_box_field name=”paragraph”][/optin_box_field][optin_box_field name=”privacy”][/optin_box_field][optin_box_field name=”top_color”]undefined[/optin_box_field][optin_box_button type=”0″ button_below=”Y”]Scarica il PDF![/optin_box_button] [/optin_box]

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! 😉

Mathone

Pillole di matematica per comprenderla meglio ogni giorno