mercoledì 9 giugno 2010

Guessing game con spiegazione

I guessing game sono spesso eseguiti da illusionisti o da matematici e consistono nell'indovinare un numero che scegliete voi.
Durante il gioco,il matematico o l'illusionista vi chiede di scegliere un numero e di effettuare alcune operazioni algebriche intermedie (ad esempio somme,prodotti,divisioni etc),il matematico o l'illusionista tramite il risultato finale di queste operazioni sul numero scelto,risale in maniera univoca al numero che avete scelto.

Naturalmente lo spettatore a cui fate il gioco ha la percezione che le operazioni che sta facendo (di cui l'illusionista/matematico non conosce i risultati) siano assolutamente poco indicative e che dare il risultato finale di tali operazioni non è sufficiente a capire il numero che avete scelto.

L'illusionista a questo punto vi stupisce dicendo esattamente il numero che avete scelto.

Adesso vi presento un guessing game e vi darò la spiegazione sia con una regola pratica,sia con una dimostrazione.

Scegliete un numero tra i numeri 8 e 9..
Moltiplicate il numero scelto per un numero dispari a piacere.
Moltiplicate il risultato precedente con un numero pari a piacere.
Sommate il primo e secondo risultato del prodotto.

Da questo risultato riuscirete a capire esattamente quale tra i due numeri lo spettatore ha scelto.

Prima di passare alla spiegazione del trucco e alla dimostrazione matematica vi voglio fare due esempi per chiarire eventuali dubbi.

Esempio 1
Scegliamo il numero 8.
Moltiplichiamo 8*13=104
Moltiplichiamo 104*6=624
Sommiamo 104+624=728

Esempio 2
Scegliamo il numero 9
Moltiplichiamo 9*27=243
Moltiplichiamo 243*10=2430
Sommiamo 243+2430=2673

Se notate,nei due esempi,la somma finale (che dovete chiedere allo spettatore),quando abbiamo scelto 8 è risultata pari,quando abbiamo scelto 9 è risultata dispari e questo come dimostrerò in seguito non è casuale.

Quindi la regola pratica per sapere quale numero lo spettatore ha scelto basta vedere se la somma finale (che voi conoscete) è pari o è dispari
Se la somma è pari allora lo spettatore ha scelto 8
Se la somma è dispari allora lo spettatore ha scelto 9

Passiamo alla parte matematica.

Chiamiamo a il numero scelto dallo spettatore,m il numero dispari ed n il numero pari,con a,m,n appartenenti all'insieme dei numeri Naturali e con a che può assumere valore 8 o valore 9.

Procediamo cercando di creare l'operazione tra questi numeri procedendo secondo l'ordine prefissato e facendo di volta in volta delle dovute considerazioni.

Moltiplichiamo a*m
Poichè m è un numero dispari allora m=2k+1,quindi a*m=a*(2k+1)
Sviluppando il prodotto a*(2k+1) otteniamo 2ak+a,quindi a*m=2ak+a

a*m=2ak+a lo chiamiamo p1 (perchè chiamarlo Paperino lo avrebbe reso ridicolo)

Moltiplichiamo il risultato ottenuto per n ottentendo (2ak+a)*n
Sviluppando il prodotto (2ak+a)*n otteniamo 2ank+2an

2ank+2an lo chiamiamo p2 (perchè ci piace così)

Sommiamo p1+p2 ottenendo così

2ak+a+2ank+2an.

Se osservate adesso il seguente polinomio,potete notare che possiamo "raccogliere il termine 'a' a fattor comune".
Utilizzando la legge distributiva "raccogliamo il termine 'a' a fattor comune" ottenendo
2ak+a+2ank+2an=a*(2k+1+2nk+2n)

Utilizzando ancora la legge distributiva nel polinomio interno possiamo affermare
a*(2k+1+2nk+2n)=a*(2k+1 +2(nk+n))

Guardate adesso i termini del polinomio come sono diventati,vi ricorda qualcosa?
2k+1 è sicuramente un termine dispari e lo indicheremo con D,2(nk+n) è sicuramente un termine pari(perchè è multiplo di due ;)) e lo indicheremo con P.
Quindi
a*(2k+1 +2(nk+n))=a*(D+P).

Dall'osservazione che un numero pari sommato ad un numero dispari da sempre un numero dispari,che chiamiamo D per comodità,otteniamo

a*D.
In sostanza a moltiplica un numero dispari!!
Se a è pari,allora a*D è sicuramente pari

se a è dispari allora a*D è sicuramente dispari.
Ed è esattamente quello che volevamo verificare!.

Questa piccola dimostrazione ci dice inoltre che 8 e 9 non sono gli unici numeri per cui vale la regola pratica descritta sopra,basta prendere un numero pari e un numero dispari e fare sempre colpo!

Spero che vi siate divertiti e che possiate meravigliare qualche vostro amico con questo giochino anche se non conoscete la dimostrazione ;).
Have fun

martedì 8 giugno 2010

Teoria degli insiemi e antinomia di Russel

In questo post vi parlerò della teoria degli insiemi e della famosa antinomia di Russel.

La teoria che vi illustrerò in parte è chiamata anche teoria "ingenua" degli insiemi.
La teoria,è chiamata "ingenua" appunto perchè presenta delle debolezze e delle ambiguità dovute alla sua "libertà".

Nella teoria degli insiemi,l'elemento chiave è appunto l'insieme (altrimenti l'avrebbero chiamata teoria del ravanello o che so io..).

La struttura di insieme non viene definita e l'insieme viene considerato un concetto primitivo.
Altri esempi di concetti primitivi sono il punto,la retta o il piano nella geometria Euclidea.

Un insieme viene espresso,solitamente,con le lettere maiuscole dell'alfabeto ad esempio A,B,C mentre gli elementi di un insieme con le lettere minuscole dell'alfabeto ad esempio a,b,c.

Se l'elemento a fa parte dell'insieme A si dice che a appartiene ad A.

Un insieme può essere espresso nel seguente modo:
A={1,2,3,4,5,6}
Tale modo di rappresentare un insieme si dice rappresentazione "esplicita" di un insieme.
L'insieme A contiene come elementi i numeri 1,2,3,4,5,6.

La maggiore "libertà" di questa teoria (che poi ci porterà alla antinomia) è dovuta al fatto che un insieme può contenere elementi di natura arbitraria,ed anche di natura diversa tra di loro:potremmo per esempio costruire un insieme che ha come elementi il numero 5, la città di Milano e il concetto astratto di amore.

Per arrivare alla antinomia di Russel voglio mostrarvi alcuni insiemi che contengono altri insiemi.

1)
Facciamo prima un esempio di un insieme che contiene se stesso.
Costruiamo l'insieme A i cui elementi sono gli insiemi che contengono più di due elementi.
Ovviamente l'insieme A è infinito dato che ci sono infiniti insiemi che contengono più di due elementi,proviamo ad elencare qualche elemento di A in modo esplicito.

A={{2,3,!};{k,a,b};{sM,ciao,<};......}

Dato che A contiene più di due elementi,A contiene anche se stesso,quindi A è contenuto in A (lo so che è strano ma è così).

2)
Adesso facciamo un esempio di un insieme che NON contiene se stesso.
Costruiamo l'insieme A i cui elementi sono gli insiemi che contengono 1 solo elemento.
A,come nell'esempio precedente, è infinito.
Diamo qualche esempio di elemento in A.

A={{1};{=};{L};{7};.......}
Dato che A contiene più di un elemento,A NON contiene se stesso.

Fatti questi due esempi adesso costruiamo il seguente insieme A e cercheremo di capire se A contiene se stesso oppure no.

Costruiamo l'insieme A i cui elementi sono gli insiemi che NON contengono se stessi.
Per fare qualche esempio.

A={{B};{S};....}

Adesso quello che ci chiediamo è "A è contenuto in A oppure non è contenuto in A?".
E' chiaro che A non può essere contenuto in A perchè altrimenti si andrebbe in contraddizione con la frase che ci permette di costruire gli insiemi (ricordiamoci ci che gli elementi sono gli insiemi che NON contengono se stessi)
Ma se A non contiene se stesso,allora dovrebbe essere da qualche parte nell'elenco degli elementi e ricadiamo nuovamente nell'errore di sopra.

Come abbiamo appena visto,A contiene A e contemporaneamente A non contiene A e questo genera una antinomia.

La letteratura matematica ci fornisce esempi più o meno concreti di Antinomie.
L'esempio tipico è quello del barbiere che avete visto nel link di wikipedia sull'antinomia di Russel.

domenica 6 giugno 2010

Quanti triangoli ci sono?

Questo è un tipico problema logico in cui bisogna contare TUTTI i triangoli presenti nella figura.
Ho rotto così tanto le scatole ai prof e ai miei colleghi con questo problema da farmi appioppare l'appellativo di "l'uomo dei triangoli" dal professore di matematica discreta.

Alcuni esempi di queste figure sono queste.
Allora,quanti triangoli riuscite a vedere?

Ovviamente una persona come me non si accontenta di sapere quanti triangoli ci sono in figure specifiche ma cerca regolarità e generalizzazioni al problema posto.

La generalizzazione in questo caso può essere la seguente:
Come variano i triangoli al variare dell'altezza del triangolo più grande?
E' possibile dare una formula generica in base all'altezza?

In termini più matematici l'ultima domanda può essere formulata nel modo seguente:
E' possibile risalire alla funzione f:N->N (dove N è l'insieme dei numeri naturali) a partire da considerazioni fatte su alcuni casi specifici?
Dopo qualche periodo di riflessione ho posto il problema al mio collega Fabio D'Asaro che,dopo pochi secondi elabora una soluzione al problema.
Fabio,ha notato che il numero di triangoli di lato 1 con la punta verso l'alto è la sommatoria dei primi n numeri.
Quindi nella prima figura i triangoli verso l'alto sono 4+3+2+1.una volta contati i triangoli di lato uno con la punta verso l'alto contiamo quelli di lato uno con la punta verso il basso e si può notare che questi sono la sommatoria dei primi n/2 numeri (arrotondato per difetto).

Dopo avere presentato il risultato al professore di matematica discreta,egli mi mostra questo risultato in cui è mostrata una formula molto più compatta della formula trovata da Fabio.
Invece qui potete travare i primi valori della sequenza numerica con riferimenti a libri
Ovviamente la formula riportata su mathword.wolfram è il modo più semplice per sapere quanti triangoli ci sono,in base all'altezza.

Bruteforce su un puzzle

Il problema consiste nello scoprire quanti confronti dobbiamo fare (nel caso peggiore) se dobbiamo provare a risolvere un puzzle con il metodo del bruteforce.

Se dividiamo il puzzle nei suoi componenti atomici (i pezzi del puzzle),possiamo immaginare il puzzle come una griglia composta da tali componenti.

Quindi dividiamo l'immagine del puzzle secondo questa griglia e numeriamo ogni casella in modo progressivo a partire da 1.

Adesso consideriamo i seguenti predicati:

P(1)="Inserimento del pezzo nella casella 1"
P(2)="Inserimento del pezzo nella casella 2"
....
....
P(x)="Inserimento del pezzo nella casella x"

Dove x sono i pezzi del puzzle.

P(1) assume x*4 possibili valori distinti considerando che ogni pezzo può essere posizionato in 4 maniere diverse.
Possiamo notare,che scelto comunque un valore per P(1),P(2) assume 4*(x-1) valori distinti.
Scelto comunque un valore per P(1) e P(2),P(3) assume 4*(x-2) valori distinti.
...
...
Scelto comunque un valore per P(1),(P2),.....,(Px-1) P(x) assume 1 solo valore

Per il principio delle scelte multiple possiamo affermare quindi,che il numero totale di confronti nel caso peggiore è 4x*4(x-1)*4(x-2)*......*4 ovvero 4*x!.



Un altro metodo per arrivare allo stesso risultato è il seguente.
Numeriamo la griglia e i pezzi in modo progressivo a partire da 1.
Costruiamo 2 insiemi A,B costituiti dai primi x numeri naturali,dove A sono le caselle distinte e B sono i pezzi distinti.

A={1,2,3,......,x} caselle
B={1,2,3,......,x} pezzi

Se f è la funzione definita in A con valori in B che associa ad ogni casella uno ed un solo pezzo,il problema diventa trovare la funzione che associa ad ogni casella il pezzo giusto.

Possiamo supporre che la funzione che stiamo cercando sia la funzione identica.


Quindi
1->1
2->2
3->3
...
...
x->x

Adesso,numeriamo ogni coppia di elementi della funzione sempre in modo progressivo a partire da 1.

1->1 la numeriamo con 1
2->2 la numeriamo con 2
3->3 la numeriamo con 3
...
...
x->x numeriamo con x

Quello che abbiamo trovato,quindi,è la seguente disposizione dei numeri naturali

1,2,3,......,x

In sostanza l'unica disposizione corretta dei pezzi nel puzzle è quella rappresentata sopra.
Per sapere quante sono TUTTE le possibili disposizioni (quindi tutti i modi di mettere i pezzi nelle caselle) basta trovare una permutazione dei primi x numeri.
Le permutazioni di x numeri sono x!.
Se poi consideriamo che ogni pezzo può essere posizionato in 4 maniere differenti allora il numero diventa 4*x!

Per concludere,poichè x! cresce quasi quanto n^x,NON provate mai a fare bruteforce su un puzzle.
Già solo per 10 pezzi dovete fare 3.628.800 prove per avere la soluzione.

martedì 1 giugno 2010

L'errore di Eulero

Il più grande errore di Eulero è dovuto,probabilmente, alla sua superbia.
Il problema che Eulero cercava di risolvere era di trovare due quadrati latini ortogonali,chiamati anche,quadrati greco-latini di ordine n.
http://it.wikipedia.org/wiki/Quadrato_latino

Eulero dopo avere ragionato riuscì a trovare un algoritmo che permetteva di trovare tutti i quadrati greco-latini di ordine diverso da n=4k+2 o se preferiti dei numeri congruenti a 2 modulo 4 ed espresse la seguente congettura.

"Per tutti gli n della forma n=4k+2, non é possibile costruire un quadrato greco-latino di ordine n."

Qualche tempo dopo Bose, Shrikhande e Parker riuscirono congiuntamente a dimostrare che per ogni n>6 esiste una coppia di quadrati latini ortogonali di ordine n.

Quindi,non solo Eulero si era sbagliato,ma si era sbagliato anche davvero di tanto.
Eulero in pratica affermava che non esisteva una classe di quadrati greco-latini (tutti quelli di ordine 4k+2),mentre in realtà non esistevano solo 2 quadrati greco-latini ovvero quello di ordine 2 e quello di ordine 6.

Si può verificare manualmente che non è possibile trovare un quadrato greco-latino di ordine 2,il problema è verificare che non è possibile trovare un quadrato greco-latino di ordine 6.

Nel 1901 Tarry dimostrò che per n=6 la congettura di Eulero era vera.
Tarry ridusse il problema all’esame di particolari quadrati latini di ordine 6, detti “ridotti” (in numero di 9408) e dopo un esame di tali quadrati scoprì che non ne esistevano 2 ortogonali.

In ogni caso,nonostante questo grossolano errore,Eulero rimane comunque un grande personaggio della matematica.

lunedì 31 maggio 2010

La legge della bella ragazza

Con tutto il rispetto per le belle ragazze che leggono il mio blog,ovviamente quello che scrivo è per fare ridere,quindi sorridete ;)

Ennesimo corollario della legge di Murphy.

Una bella ragazza è sempre impegnata con qualcun altro.

Se una bella ragazza per caso non ha un ragazzo o non è impegnata lo resterà esattamente fino a due secondi prima che tu possa provarci o che tu le chieda di uscire.

Se una bella ragazza non ha un ragazzo e se tu gli riesci a chiedere di uscire o a provarci puoi stare sicuro che è stupida per quanto è carina oppure potrebbe fare impallidire il più sboccato dei marinai quando parla.

Una bella ragazza che ti abborda è una prostituta oppure un trans.

Una bella ragazza senza ragazzo,gentile,raffinata e intelligente è sicuramente omosessuale.

Quando chiedi il numero di telefono ad una bella ragazza appare il suo ragazzo,se non succede allora il numero è sicuramente sbagliato.

Una bella ragazza in fotografia potrebbe non essere tanto bella dal vivo.

Se avete altri suggerimenti o commenti scrivete pure ;)

Goodbye Martin Gardner

Nonostante la triste notizia sia in giro da un pò io l'ho appresa da pochi minuti.
Ho avuto il piacere di leggere un libro di Gardner e mi ha affascinato molto con i suoi racconti,enigmi e battute sul mondo dei matematici.
Mi rincresce davvero salutare per sempre questo grandioso matematico.

Ci vediamo dall'altro lato ;).

fonte notizia