El problema de les set vaques

Dedicat a l'àvia

Aquest és un conte que ens explicaven quan érem petits. No és matemàticament correcte al 100%, però la solució és elegant i, com tots els contes infantils, és agradable de llegir-lo. Diu així:


Hi havia una vegada una família de pagesos, un pare i tres fills, que tenien un ramat de vaques. Un dia inesperat el pare va morir. En el testament hi havia deixat escrit:

Dono la meitat de les vaques al meu fill gran. De la resta, el fill mitjà se'n quedarà la meitat. De les altres, el fill petit se'n quedarà també una meitat.

En aquell moment la família disposava de set vaques. Després de fer els números, els va sortir el següent repartiment:

Gran:  3,5 vaques
Mitjà: 1,75 vaques
Petit: 0,875 vaques

Com havien de fer el repartiment? Com el fill gran podia quedar-se amb 3 vaques i mitja? I pels altres fills encara era més complicat, com es podien quedar amb 0,75 vaques o 0,875, en el cas del petit?

Els fills van anar a trobar el savi, conegut per la seva experiència en solucionar casos com els seus. El savi els va dir:

Preneu la meva vaca i torneu a fer el repartiment. Segur que us ajudarà. I, quan hagueu solucionat el problema ja ho arreglarem d'alguna manera.

Els fills van tornar cap a casa seva amb la vaca del savi. Després de fer els càlculs de nou els va sortir el següent repartiment:

Gran:  4 vaques
Mitjà: 2 vaques
Petit: 1 vaca

Ara havien solucionat el problema de les meitats i altres fraccions de vaca. A més, els sobrava una vaca, que ràpidament van tornar al savi. Quan eren allà van preguntar-li:

Savi, vostè ens ha ajudat en el repartiment, però ens queda el dubte de si aquest ha estat just per a nosaltres, o bé si hi ha hagut algú que se n'ha beneficiat.

El savi els va respondre:

Pel fill gran, el repartiment és just, ja que abans li tocaven 3,5 vaques i ara li'n toquen 4. Pel fill mitjà, el repartiment també és beneficiós, ja que abans li tocaven 1,75 vaques i ara li'n toquen 2. I pel fill petit també: passa de 0,875 a 1 vaca. Així que no hi veig cap problema en fer aquest repartiment.

I així els fills van poder fer un repartiment de les vaques bastant semblant al que deia el testament sense haver de partir cap vaca per la meitat i beneficiós per a tots ells.

Treballar amb dades agregades - la paradoxa de Simpson

Extret de Statistics for Business and Economics, Anderson, Sweeney, Williams pags 45 - 49

Una taula creuada (crosstabulation) és un resum en forma de taula per a dues variables.
Per exemple, si estudiem la valoració que fan d'un restaurant diversos clients en funció del que paguen podríem tenir una taula com la següent:

                  Preu pagat per l'àpat
Valoració  |  10-19€  20-29€  30-39€  40-49€  |  Total
------------------------------------------------------
Bo         |   42      40       2       0     |    84
Molt bo    |   34      64      46       6     |   150
Excel·lent |    2      14      28      22     |    66
------------------------------------------------------
Total      |   78     118      76      28     |   300

Les dades en dues o més taules creuades sovint són combinades conjuntament tot formant una taula creuada agregada on algunes variables es recombinen. En aquests casos, hem d'anar en molt de compte a l'hora d'extreure conclusions sobre la relació entre les diverses variables. Fins i tot, en alguns casos, les conclusions basades en la taula creuada agregada poden ser totalment falsejades si es contrasten amb les dades de les taules creuades originals. És el que es coneix com a Paradoxa de Simpson. Ho mostrem en un exemple:

La jutgessa Alícia i el jutge Bartomeu han presidit diversos casos tant a l'Audiència Nacional com al Tribunal Suprem. Alguns dels veredictes que han emès han estat apel·lats després. En la majoria de casos, l'apel·lació ha confirmat el veredicte original, però en alguns casos l'ha canviat.
A continuació mostrem una taula creuada on hi ha el resum, per cada jutge, dels casos en els que l'apel·lació ha confirmat la decisió del jutge i en quins l'ha canviat.

                      Jutge
Veredicte  |  Alicia        Bartomeu    |  Total
------------------------------------------------
Confirmat  |  129 (86%)     110 (88%)   |   239
Canviat    |   21 (14%)      15 (12%)   |    36
------------------------------------------------
Total (%)  |  150 (100%)    125 (100%)  |   275
------------------------------------------------

La conclusió que podem treure de la taula anterior és que el jutge Bartomeu és més bo que la jutgessa Alícia, ja te un percentatge més gran d'encert en els veredictes quan aquests s'apel·len.

Però...

Si fem les taules creuades segons el tribunal on s'han pres les decisions veurem que obtenim uns resultats sorprenents:

                Jutgessa Alícia
           |  Tribunal   Audiència  |
Veredicte  |   Suprem    Nacional   | Total 
-------------------------------------------
Confirmat  |  29 (91%)   100 (85%)  |  129
Canviat    |   3 (9%)     18 (15%)  |   21  
------------------------------------------- 
Total (%)  |  32 (100%)  118 (100%) |  150  
------------------------------------------- 


                 Jutge Bartomeu
           |  Tribunal   Audiència  |
Veredicte  |   Suprem    Nacional   | Total
-------------------------------------------
Confirmat  |  90 (90%)   20 (80%)   |   110
Canviat    |  10 (10%)    5 (20%)   |    15
-------------------------------------------
Total (%)  | 100 (100%)  25 (100%)  |   125
-------------------------------------------

De la taula creuada i els percentatges de la jutgessa Alícia, veiem que els seus veredictes van ser confirmats en un 91% al Tribunal Suprem i en un 85% a l'Audiència Nacional. La taula del jutge Bartomeu mostra uns percentatges del 90% i el 80%, respectivament. Comparant aquests percentatges, veiem que la jutgessa Alícia té millors percentatges tant al Tribunal Suprem com a l'Audiència Nacional. Aquest resultat contradiu la conclusió anterior que el jutge Bartomeu és millor!

L'explicació del fenomen és la següent: el jutge Bartomeu ha presidit molts més casos (comparat amb la jutgessa Alícia) al Tribunal Suprem, tribunal que té un percentatge de confirmació dels veredictes més alt que l'Audiència Nacional (és a dir, a vista dels percentatges, és un tribunal més "fàcil"). Aquest major percentatge fa que els seus resultats globals siguin molt bons i arribin a superar el global de la jutgessa.

La conclusió que en podem extreure és que, tal com ens il·lustra la paradoxa de Simpson, hem d'anar molt en compte a l'hora d'extreure conclusions de taules creuades on s'utilitzen quantitats agregades. Sempre haurem d'investigar si hi ha si hi ha variables "ocultes" que poden alterar-ne les conclusions.

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?