Calcular PI tirant pedres en un quadrat

Segurament aquest títol és difícil d'entendre, però el problema és tant senzill com preguntar-se si seríem capaços de trobar el nombre PI tirant només pedres. El procediment és el següent:

D'alguna manera dibuixem un quadrat al terra i també hi tracem un cercle inscrit.

Després comencem a tirar pedres. Les tirem aleatòriament, de manera que cada pedra pot caure a tant a fora com a dins del quadrat.

Quan ja haguem tirat N pedres, podem contar les que han caigut a dins del cercle NC i les que ho han fet a dins del quadrat NQ. La relació entre aquests dos nombres ha de ser equivalent a la relació de les àrees del cercle i del quadrat. És a dir, com més gran sigui una àrea, més pedres podrà contenir.

En altres paraules, es complirà la relació NC/NQ=AreaCercle/AreaQuadrat. Substituint el valor de les àrees obtenim: NC/NQ=PI*(R^2)/((2R)^2)=PI/4. És a dir: PI=4*NC/NQ.

Per tant, fent el quocient entre les pedres que han caigut a dins del cercle i les de dins del quadrat, i multiplicant-ho per 4 hem d'obtenir el nombre PI.

És evident que les pedres es tiren aleatòriament i que tirant 10 o 20 pedres estarem molt lluny del nombre que estem buscant. De totes maneres, tirant milions i milions de pedres s'ha d'obtenir un valor molt similar a PI. De fet, l'únic que fa falta tenir el temps de tirar tantes pedres.

Pot comú al pis

Fa uns anys, en Vila, en Joan i en Camp van llogar un pis per anar-hi a passar el curs. Per fer front a les despeses comunes, van decidir tenir un pot on cadascú hi va posar 50€.

Una setmana més tard, en Vila i en Camp van anar a un supermercat per comprar menjar. El cost total del menjar va ser de 90€. Quan van arribar al pis, en Joan va dir que no li agradava el que havien comprat i que no contessin amb ell per aquest menjar. En Vila i en Camp van dir que no hi havia cap problema i que passarien els compes corresponents.

En fer els comptes, en Vila va dir que, òbviament, ells havien de pagar 30€ perquè el que havien comprat no era d’en Joan. Encara que a en Camp no li acabava de convèncer la decisió, cadascú va posar 15€ al pot comú.

Durant la nit, en Camp va estar pensant amb la decisió que havien pres i va pensar que havia de parlar amb els seus companys de pis al matí següent. Quan es van llevar, en Camp va dir:

-Tenim 90€ al pot comú. És a dir, 150€ inicials, menys 90€ que vam gastar, més els 30€ que vam afegir-hi jo i en Vila després de la compra.

Llavors, en Joan va exclamar:

-Jo he pagat 50€, no he comprat res, i ara rebo només 30€!

Què ha passat?

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

La solució d’aquest problema pot ser pensada de dues maneres diferents:

A) En Vila i en Camp havien de pagar 30 €. Però aquesta quantitat l’havien de pagar directament a en Joan i no al pot comú. El fet de posar-ho al pot comú fa que realment no paguin 30€ ja que ells també reben aquesta quantitat.

Si ho paguen a en Joan, llavors hi haurà 60€ al pot comú. Després, al dividir-lo, rebran 20€ cadascú. Per tant, en Joan tindrà els 30€ que li han pagat directament més els 20€ del pot comú. Cosa que és correcte.

B) Si en Vila i en Camp volen retornar als diners al pot, han de pagar tots els 90€. És a dir, 45€ cadascú.

Fent-ho d’aquesta manera, restauren els 150€ inicials al pot comú i, si el divideixen, tots recuperen 50€.

Quin és el número més gran que podem escriure?

Dedicat a l'Adrià Gascon.
Extret de http://www.scottaaronson.com/writings/bignumbers.html

Imaginem que participem en un concurs on, en 15 segons, hem d'escriure el número més gran que coneguem (un nombre concret, no s'hi val escriure "infinit"). Quins nombres podem escriure?

La primera idea que ens ve al cap és escriure una seqüència de nous:
999999999999999999

Però de seguida ens n'adomem que, si en comptes d'escriure nous escrivim uns, anem molt més ràpid i podem escriure moltes més xifres en el mateix temps:
11111111111111111111111

I si exponenciem? Quin número és més gran: (9^9)^9 o 9^(9^9)? El segon, així que una nova proposta és el número
9^(9^(9^(9...)))
que s'abrevia com
9^9^9^9...

Hi ha operacions més poderoses que l'exponencial? Sí, de fet l'operació exponencial forma part d'una cadena d'operacions, anomenada la seqüència d'hiperoperacions.
La hiperoperació elemental consisteix en sumar 1:
H0(a,b) = b + 1

La hiperoperació primera consisteix en sumar:
H1(a,b) = a + b

La segona és la multiplicació:
H2(a,b) = a * b

La tercera és l'exponenciació:
H3(a,b) = a ^ b

La quarta s'anomena tetració, i es defineix com:
H4(a,b) = a ^ a ^ a ^ ... ^ a (b vegades)

La fórmula general d'una hiperoperació és:
Hn(a,b) = b + 1 si n = 0
Hn(a,b) = a si n = 1, b = 0
Hn(a,b) = 0 si n = 2, b = 0
Hn(a,b) = 1 si n >= 3, b = 0
Hn(a,b) = Hn-1(a,Hn(a,b-1)) altrament

Així, pel cas de la tetració, tenim el que havíem comentat:
H4(a,b) = H3(a,H4(a,b-1)) = H3(a,H3(a,H4(a,b-2))) = ... = a ^ (a ^ ... ^ a)

Si fixem els valors de a i b al subíndex de la hiperoperació obtenim (una versió de) la seqüència d'Ackermann. Els seus primers elements en són:
A(1) = 1 + 1
A(2) = 2 * 2
A(3) = 3 ^ 3
A(4) = 4 ^ 4 ^ 4 ^ 4

i la fórmula general és:
A(n) = Hn(n,n)

que podem calcular amb la recurrència que hem presentat abans.

Una bona resposta a la pregunta que plantegem en aquest escrit és, doncs, un número ben gran de la seqüència d'Ackermann.

La funció d'Ackermann, és a dir, la funció que donat n computa A(n) té propietats que la fan especial. És una funció computable total que no és primitiva recursiva. És a dir, existeix un algorisme (un programa) que la pot computar, però que creix més ràpid que les funcions primitives recursives. Per aquest escrit en tenim prou quedant-nos amb aquesta idea, no ho detallarem més. La funció d'Ackermann mostra que, tot i que totes les funcions primitives recursives són computables, el recíproc no és cert.

Però encara hi ha nombres més grans que els de la seqüència d'Ackermann. Però necessitem utilitzar la definició de Màquina de Turing. Una funció és computable si existeix una Màquina de Turing que la calcula en un nombre finit de passos. I podem classificar les Màquines de Turing segons el nombre de regles que tenen escrites a la cinta. Llavors, fixat un nombre N de regles, hi ha un nombre finit de MT que tenen N regles, i es divideixen en dos conjunts: les que no s'aturen i les que s'aturen. D'aquestes últimes, cadascuna executarà un nombre de passos fins aturar-se. Doncs la seqüència "Busy Beaver" es defineix com:
BB(N) = max{nombre de passos abans d'aturar-se d'una MT amb N regles}

Aquests nombres són immensos: de fet se'n coneixen ben pocs:
BB(1) = 1
BB(2) = 6
BB(3) = 21
BB(4) = 107

No es coneix el valor de BB(5), tot i que se sap que és més gran de 47 milions. I pel que fa al valor de BB(6), es coneix que supera els 8.000 bilions...

Què us sembla si responem la pregunta inicial amb un nombre ben gran de la seqüència BB?

Un altre de probabilitats

Dedicat a en Dani Alonso

Una dona embarassada sap, pels resultats d'una ecografia, que està esperant bessons, i que seran dos varons. El seu metge li ha dit que 1 de cada 3 parts dobles resulta ser de bessons idèntics.
Quina és la probabilitat que els dos fills d'aquesta dona siguin bessons idèntics?


- - -
- - -
- - -
- - -
- - -
- - -
- - -
- - -


Solució 1:

Assumim que la probabilitat que una fecundació
produeixi un nen o una nena és la mateixa, 1/2.

Pr(2 nens) = 1/4
Pr(2 nens | bessons idèntics) = 1/2
Pr(bessons idèntics) = 1/3

Teorema de Bayes:

Pr(A|B) = Pr(B|A) * P(A) / P(B)

Si prenem:
A = bessons idèntics
B = 2 nens
tenim:

Pr(bessons idèntics | 2 nens)

Pr(2 nens | bessons idèntics) * Pr(bessons idèntics)
=  ----------------------------------------------------
                Pr(2 nens)

1/2 * 1/3
= --------- = 2/3
 1/4

Solució 2:

La clau del raonament és en la suposició (errònia)
que la probabilitat de tenir dos nens és 1/4.
En realitat és la següent:

Pr(2 nens)
= Pr(2 nens | no idèntics) + Pr(2 nens | bessons idèntics)
= 1/4 * 2/3 + 1/2 * 1/3 = 1/6 + 1/6 = 1/3

Llavors el càlcul és:

Pr(2 nens) = 1/3

Pr(2 nens | bessons idèntics) = 1/2
Pr(bessons idèntics) = 1/3

Teorema de Bayes:

Pr(A|B) = Pr(B|A) * P(A) / P(B)

Si prenem:
A = bessons idèntics
B = 2 nens

tenim:

Pr(bessons idèntics | 2 nens)

Pr(2 nens | bessons idèntics) * Pr(bessons idèntics)
= ----------------------------------------------------
              Pr(2 nens)

1/2 * 1/3
= --------- = 1/2
 1/3

En aquest problema, l'esdeveniment "tenir dos nens" no és ben bé tenir dos nens, sinó més aviat "tenir dos nens en un mateix part". Llavors s'entén més el resultat de la segona solució.

En el món de la probabilitat tot és relatiu (el problema de les 3 portes n'és un bon exemple): quan llegeixo de nou l'enunciat veig que també podem arribar a la conclusió que la probabilitat de tenir bessons idèntics és 1/3, tal i com li diu el metge a la dona inicialment.

Per tant, en la meva modesta opinió, hi ha tres resultats possibles (1/3, 1/2 o 2/3) que poden ser justificables des d'algun punt de vista.

Què ha de fer el tirador?

L'altre dia vaig topar-me amb un problema d'aquells que la resposta no és la que sembla a primera vista. És el següent.

Se suposa que hi ha tres tiradors. El primer d'ells és molt bo, té un percentatge d'encert del 100%. On posa l'ull posa la bala. El segon no ho és tant, té una efectivitat del 50%. El tercer és el més dolent de tots, només encerta en un de cada tres tirs que fa, el 33%.

Aquests tres tiradors es troben enfrontats en un duel on, alternativament s'hauran d'anar disparant. Primer començarà un, després l'altre, després l'altre, un altre cop el primer, etc.

Per donar opcions a tots, es decideix que l'ordre serà el següent: primer dispararà el pistoler més dolent (el del 33%), després el mitjà (el del 50%) i finalment el més bo (el del 100%). En cas que hi hagi més rondes es repetirà l'ordre.

Pregunta

Suposem que nosaltres som els consellers/amics del tirador més dolent (el del 33%). Què li hem d'aconsellar que faci en el seu tir? Disparar contra el més bo? Contra el mitjà?


...
...
...
...



Resposta

Disparar contra el més bo oi? Té una cosa millor a fer: FALLAR. Fixem-nos-hi.

Si dispara contra el més bo i el mata, llavors el mitjà el dispararà a ell, amb un 50% de possibilitats de morir.

Si dispara contra el mitjà i el mata encara és pitjor, ja que llavors el més bo el matarà segur.

En canvi, si falla (expressament o no, però és més fàcil fer-ho expressament) llavors el torn passa al mitjà. Aquest dispararà contra el més bo (òbviament). Si el mata llavors el nostre tirador té la possibilitat de sortir viu del duel, ja que efectua el següent tir (33% de possibilitats). Si el mitjà falla, llavors el torn passa al més bo. Aquest clarament matarà el mitjà i igualment el nostre amic tirador tindrà la possibilitat de sortir-ne viu si encerta en el següent tir.

En tots dos casos la situació és sensiblement millor que si dispara contra un dels dos pistolers i el mata.


De tota manera, la millor solució seria solucionar les coses amb una conversa i estalviar-se haver de fer servir les armes :-)

Cavallers i escuders

El llibre de divertiments lògics que m'agrada més és un de Raymond Smullyan que té per títol ¿Cómo se llama este libro? En particular, m'apassiona la secció d'endevinalles sobre els cavallers i els escuders. Les endevinalles que hi apareixen són molt típiques de la lògica, i també estan a d'altres llibres, però en aquest que cito n'hi ha un bon recull, la majoria ideades per l'autor.

Se suposa que hi ha una illa en la que certs habitants anomenats cavallers diuen sempre la veritat, i d'altres anomenats escuders sempre menteixen. Se suposa que tot habitant de la illa és o cavaller o escuder. Amb aquest plantejament tan senzill podem pensar moltes endevinalles.

1. (26) Segons aquest vell problema, tres dels habitants -A, B i C- es trobaven en un jardí. Un estranger passava per allà i li va preguntar a A, "Ets cavaller o escuder?". A va respondre, però tan confosament que l'estranger no ho va entendre. Llavors l'estranger va preguntar a B, "Què ha dit A?". I B va respondre "A ha dit que és escuder". Però en aquest instant el tercer home, C, va dir, "No creguis a B, que menteix!".
   La pregunta és, què són B i C?


2. (28) En aquest problema hi ha només dos individus, A i B, cadascun dels quals és o cavaller o escuder. A diu: "Al menys un de nosaltres és escuder"
   Què són A i B?


3. (29) Suposem que A diu, "O jo sóc un escuder o B és un cavaller". Què són A i B?
   


4. (30) Suposem que A diu, "O jo sóc un escuder o en cas contrari dos més dos és igual a cinc". Què podem concloure?


5. (31) Novament tenim tres persones, A, B i C, cadascuna de les quals és o cavaller o escuder. A i B diuen el següent
   A: Tots nosaltres som escuders.
   B: Un de nosaltres, i només un, és un cavaller.
   Què són A, B i C?

Solucions

1. És impossible que un cavaller o un escuder diguin "Jo sóc escuder", ja que un cavaller estaria dient l'enunciat fals de que ell és escuder, i un escuder estaria emetent l'enunciat cert que ell és escuder. Per tant, A mai diria que és escuder. Per tant, B mentia quan va dir que A havia dit que ell era escuder. Per tant B és escuder. Com que C va dir que B estava mentint, i B estava certament mentint, C va dir la veritat, d'aquí que C és un cavaller. Concloem, doncs, que B és un escuder i C un cavaller. (És impossible saber què és A).


2. Suposem que A fos escuder. Llavors l'enunciat "Al menys un de nosaltres és escuder" seria fals (ja que els escuders emeten enunciats falsos); d'on en segueix que tots dos serien cavallers. Així, si A fos escuder, hauria de ser també cavaller, cosa impossible. Per tant A no és un escuder; és un cavaller. I per això el seu enunciat ha de ser cerr; així, al menys un d'ells és realment un escuder. Com que A és cavaller, llavors B ha de ser l'escuder. Resumint, A és cavaller i B escuder.


3. A i B són tots dos cavallers.
   


4. L'única conclusió vàlida és que l'autor d'aquest problema no és un cavaller. El fet és que ni un cavaller ni un escuder podrien haver emès aquest enunciat!
   


5. A escuder, B cavaller i C escuder.
   

Quants afinadors de piano té la ciutat de Boston?

Extret de "Matemática, ¿estás ahí?", d'Adrián Paenza

Un executiu, en un moment determinat de la seva vida, es va topar amb aquesta pregunta en una entrevista de feina. La pregunta pretenia estimar "el seu sentit comú".
-Quants afinadors de piano creu vostè que té la ciutat de Boston? -L'entrevista es feia en aquella ciutat d'Estats Units.
No es tractava, obviament, de que ell respongués amb exactitud. Possiblement ningú sap amb precisió el nombre exacte d'afinadors de piano que hi ha en una ciutat. Del que si es tractava es de que algú que visqués en una ciutat pugués estimar. No pretenien que digués ni 23 ni 450.000. Però sí volien escoltar-lo raonar. I veure'l arribar a una conclusió. Suposem, per un moment, que n'hi ha uns mil. No volien que conclogués ni 23 ni 450.000, per suposat, perquè hauria estat allunyadíssim del nombre aproximat.
De la mateixa manera, si a una persona li preguntessin quina podia ser la màxima temperatura en un dia a Barcelona, ningú respondria 450 graus, ni tampoc 150 graus sota zero. Es preten, doncs, una estimació. Però molt més encara: volien escoltar el seu raonament.



L'autor del llibre, Adrián Paenza, també fa els seus càlculs. No hem de coincidir amb el seu raonament ni amb el nombres que proposa, i invita al lector a fer el seu propi càlcul.
A Boston hi viuen aproximadament 589.000 persones i hi ha unes 250.000 cases. Per tant,
persones: 600.000
cases: 250.000
Cada quantes cases hi deu haver un piano? Cent? Mil? Deu mil? L'autor proposa cent. Per tant, amb 250.000 cases, i un piano per cada cent, significa que, segons l'autor, a Boston hi ha 2.500 pianos.
Ara bé, s'ha de fer una nova estimació. Cada afinador, quants pianos atén? Cent? Mil? Deu mil? L'autor torna a elegir cent. Per tant, si hi ha 2.500 pianos i cada afinador atén cent pianos resulta que hi haurà, d'acord amb les seves suposicions, aproximadament 25 afinadors de piano.