diumenge, 28 de novembre de 2010

Juguen blanques



Juguen blanques, que sembla que perden la dama, però... com poden guanyar?

dilluns, 15 de novembre de 2010

Matrius amb tres 0, tres 1 i tres 2 que tinguin rang màxim

En els comentaris del post del dia 20 d'octubre, en Gerard em deixava aquest problema:
I, ja que hi som, quantes matrius que facin servir tres cops cadascun dels números {0,1,2} tenen rang màxim? :)


El problema em sembla interessant, però és clar, no en sé la solució... i estic una mica oxidada (que fa molt que no resolc problemes d'aquest estil, vaja!)

Tot i així, com que suposo que en Gerard sap la solució (o sap com trobar-la!) i segurament algú més que es passi per aquí pot trobar-la millor, jo poso la meva proposta... i ja em direu on és l'error (si és que n'hi ha, que suposo que sí, perquè jo em pensava que n'hi hauria menys...)

En un principi, les compto totes. Trobar-les totes seria equivalent a ordenar els tres 0, els tres 1 i els tres 2. Per tant,

$$\frac{9!}{3!3!3!} = 1680. $$

D'aquestes 1680, quines seran de rang màxim?

Calculo quines no tenen rang 3, que em sembla més senzill. En principi, he trobat 3 tipus de matrius que no tinguin rang 3:

  • Les matrius que tenen 3 zeros en alguna fila o columna
  • Les matrius que tenen dues files (o columnes) iguals
  • Les matrius en les que una fila (columna) és el doble d'una altra fila (columna).


Així que anem-los a comptar:

Matrius que tenen 3 zeros en alguna fila o columna:

Si una matriu té 3 zeros en una fila (columna) qualsevol, em queden per fixar els tres 1 i els tres 2, que els posaré en 6 posicions. Per tant, fixant la fila/columna de zeros, tinc en total

$$\frac{6!}{3!3!} = 20 $$ possibilitats.

Com que els zeros poden estar en 3 files o 3 columnes, en total tinc 120 matrius que no tenen rang màxim perquè tenen tota una fila/columna de zeros.

Matrius que tenen dues files (columnes) iguals

En aquest cas, com que dues files (o columnes) han de ser iguals, totes les files (o columnes) han de tenir un 0, un 1 i un 2. Això vol dir que en total tindré 6 casos: 012,021,102,120,210,201.

Fixades les dues files i els nombres que hi ha d'haver a cada fila, només em queden 6 possibilitats més per posar el 0, l'1 i el 2 que em queden. Per tant, en tindré 36 casos (fixant quina fila i columna vull que es repeteixin).

Però... les matrius que tenen les 3 files (columnes) iguals les estic comptant 3 cops! I, a part, ja les havia comptat quan mirava les matrius que tinguessin tota una fila/columna de zeros.

Així doncs, com que tinc 3 maneres diferents de trobar les dues files que vull que siguin iguals, tindré:

3*36-6 = 102, si m'ho miro per files, i 102 si m'ho miro per columnes, en total 204 matrius.

Matrius amb una fila el doble que l'altra:

Serien els casos on tinc una fila amb 110 (o permutació) i una altra amb 220 (o permutació, que sigui la mateixa, és clar!!!)

Puc escollir 3 casos per files (i 3 per columnes), i 110 el puc posar amb 3 ordres diferents.

Altre cop he de restar els casos en què em surti una fila/columna de 0...

En total, torno a tenir 6 possibilitats pels casos que em queden "lliures", però com que ara les files no són iguals (no és el mateix que la primera fila sigui 110 i la segona 220 que al revés), per cada cas de fila/ordre en tindré 12.

Per tant, d'aquest tipus en tinc 12*3*6 = 216.

D'aquí hi he de treure les que tinguin una fila/columna de zeros (que ja les he comptat abans), que serien 2*2*3*6 = 72.

Per tant, d'aquí me'n queden 144.

D'acord, a dalt hi ha tot el rotllo, i el resultat?

Doncs si no m'he equivocat (cosa que seria molt normal, i com que està tan mal explicat no crec que ningú sigui capaç de trobar l'error... però si hi ha una manera més senzilla de calcular-ho estaré contenta de saber-ho...), el total de matrius seria:

Total de matrius: 1680
Matrius amb 000: 120
Matrius amb 2 files/col iguals i no 000: 204
Matrius amb una fila/col el doble d'una altra i no 000: 288

Total de matrius amb rang 3: 1068.

I aquí el meu problema... segons els meus càlculs són el 63.57% de totes les matrius... i jo hagués dit que n'hi hauria moltes menys.

Així doncs: és correcte? On és l'error?

dilluns, 8 de novembre de 2010

Com aconseguir ternes pitagòries a partir dels nombres de Fibonacci?

Suposem que $f_n$ són els nombres de Fibonacci: $f_1=1$, $f_2$=1, $f_3=2$, $f_4=3$, $f_5=5$, ...

Donat un nombre natural $k$ qualsevol, construim els següents nombres:

$A = f_k f_{k+3},$
$B = 2 f_{k+1} f_{k+2},$ i
$C = f_{k+1}^2 + f_{k+2}^2.$

Podem veure que $A^2+B^2=C^2$. No és difícil, però portarà un parell de línies de càlculs :-D Per veure-ho, calcularé $A^2+B^2-C^2$ i veuré que és 0:

$A^2 + B^2 - C^2 = $
$f_k^2 f_{k+3}^2 + 2 f_{k+1}^2 f_{k+2}^2 - f_{k+1}^4 - f_{k+2}^4 = $
$f_k^2 (f_{k+1} + f_{k+2})^2 - f_{k+1}^4 - f_{k+2}^4 + 2 f_{k+1}^2 (f_k+f_{k+1})^2 =$
$f_k^2 f_{k+1}^2 + f_k^4 + 2 f_k^2 f_{k+1}^2 - f_{k+1}^4 -(f_k^4 + f_{k+1}^4 + 2 f_k^2 f_{k+1}^2) + 2 f_k^2 f_{k+1}^2 +2 f_{k+1}^4,$

on tots els termes s'anul.len, i per tant és 0.

Així doncs, podem agafar k=1 i obtenim A=3, B= 4, C=5, potser la més famosa de les ternes pitagòriques. Fixem-nos que C=5, que precisament és un nombre de Fibonacci ($f_5$).

Podem agafar $k=2$ i obtenim $A=5$, $B=12$, $C=13$, una altra terna pitagòrica famosa. En aquest cas, 13 és $f_7$.

Per $k=3$, $A=16$, $B=30$ i $C=34$. 34 és $f_9$.

De fet, es pot veure que passa sempre. Fent servir una propietat dels nombres de Fibonacci que diu que:

$f_{2n+k} = f_k f_{n+1}^2 + 2 f_{k-1} f_{n+1} f_n + f_{k-2} f_n^2,$

podem comprovar que, efectivament,

$f_{2k+3} = f_3 f_{k+1}^2 + 2 f_{2} f_{k+1} f_k + f_{1} f_k^2 = $
$2 f_{k+1}^2 + 2 f_{k+1} f_k + f_k^2 =$
$f_{k+1}^2 + (f_k+f_{k+1})^2 = f_{k+1}^2 + f_{k+2}^2 = C.$

Idea: Mario Livio, La proporción áurea.