27.11.13

Proba de operacións básicas con números enteiros

Escribo este post simplemente para introducir un test de operacións sinxelas con números enteiros. Perdón pola diglosia imposta...

24.11.13

Matrices e Pitágoras?-II


No anterior post levoume un anaco empezar a albiscar a relación das matrices coa Teoría de Números, a nivel elemental. Hoxe chegarei por fin ao obxectivo que me fixo comezar co título Matrices e Pitágoras despois de ler un artigo titulado "Modified Farey Trees and Pythagorean Triples" de Shin-Ichi Katayama (podedes atopalo nesta web). O artigo segue unha liña comezada hai 50 anos por F.J.M. Barning, quen conectou as distintas triplas pitagóricas mediante certo tipo de matrices. Pero primeiro haberá que lembrar certos conceptos:

A ecuación pitagórica, seguramente a máis coñecida das ecuacións diofánticas, xorde no estudo dos triángulos rectángulos con lonxitudes dos lados que sexan números naturais:
$$\small{a^2+b^2=c^2}$$
As solucións constan de tres números, polo que se chaman ternas pitagóricas. A primeira terna, que todos os alumnos teñen visto á altura de 1º de E.S.O., é a famosa $\small{(a,b,c)=(3,4,5)}$, e é a base das aplicacións para crear ángulos rectos en carpintería, por exemplo.

A corda  (3,4,5) cos seus 12 nós

Ademais a terna (3,4,5) ten unha peculiaridade, pois os tres números non posúen ningún factor primo común. A estas ternas pitagóricas coñecémolas como ternas primitivas.

É sinxelo atopar todas as ternas pitagóricas primitivas, se comparamos o procedemento coa sofisticación a onde ten chegado o estudo das ecuacións diofánticas. Vexámolo:

Se a terna (a,b,c) é primitiva, automaticamente chegamos a que o termo c ten que ser impar, e b e a de paridade oposta, é dicir, un par e o outro impar (breve explicación: se b e a fosen pares, c tamén o sería, e 2 sería un factor común; se b e a fosen impares, o seu cadrado deixaría resto 1 ao ser divido entre 4, co cal c² deixaría resto 2 ao ser dividido entre 4, polo que c² sería un cadrado perfecto par e non divisible entre 4, o que é absurdo). Supoñamos que a é impar e b par. Reescribimos a ecuación como $\small{b^2=c^2-a^2=(c+a)(c-a)}$
Como b, c+a e c-a son pares, podemos dividir os dous membros entre 2 sen saír dos naturais:
$$\small{\left(\frac{b}{2}\right)^2=\frac{c+a}{2} \cdot \frac{c-a}{2} }$$
Agora chega o paso crucial, que ao ser copiado tantos pseudo-descubrimentos provocou no estudo do Derradeiro Teorema de Fermat:

Como $\small{\frac{c+a}{2}}$ e $\small{\frac{c-a}{2}}$ son números coprimos e o seu produto é un cadrado perfecto, cada un deles ten que ser un cadrado á súa vez. Chamémoslles u e v, de tal xeito que:

$$\small{\frac{c+a}{2}=u^2, \frac{c-a}{2}=v^2}\Longrightarrow c=u^2+v^2, a=u^2-v^2, b=2uv$$
Chegando á expresión xeral para as ternas primitivas $(a,b,c)=(u^2-v^2, 2uv, u^2+v^2)$
Onde hai que salientar que u e v son coprimos e teñen paridade oposta para sermos coherentes co carácter primitivo da terna (a,b,c).

Por exemplo, a terna (3,4,5) correspóndese nesta parametrización cos valores u=2, v=1; (5,12,13) con u=3,v=2; (21,20,29) con u=5, v=2; (33,56,65) con u=7, v=4...

Hai outra aproximación á solución que utiliza a parametrización de curvas, mais require algo máis de traballo. Así que vaiamos por fin á alucinante relación entre as matrices e as ternas pitagóricas:

No devandito artigo aparece un procedemento aparentemente standard que eu nunca vira. Como quedei pampo quería compartilo neste faiado que manteño na rede:

Se definimos as matrices $$\small{M_1=\left( \begin{array}{ccc}1&-2&2\\ 2&-1&2\\2&-2&3 \end{array}\right),M_2=\left( \begin{array}{ccc}1&2&2\\ 2&1&2\\ 2&2&3 \end{array}\right),M_3=\left( \begin{array}{ccc} -1&2&2\\ -2&1&2\\ -2&2&3 \end{array}\right)}$$
resulta que podemos obter todas as ternas primitivas a partir soamente da primeira, (3,4,5)! Este feito é o que me deixou abraiado. A técnica concreta é xa, na miña opinión, case menos importante:

Dada calquera terna primitiva (a,b,c) existe un número r natural tal que:
$$ \left( \begin{array}{ccc} a \\ b \\ c \\ \end{array}\right)=M_{\sigma(1)}M_{\sigma(2)} \dots M_{\sigma(r)}\left( \begin{array}{ccc} 3 \\ 4 \\ 5 \\ \end{array}\right)$$
onde $\small{(\sigma(1),\sigma(2),\dots \sigma(r))\in\{1,2,3\}^r}$
Aínda máis: a representación da terna (a,b,c) é única, e calquera representación dá lugar a outra terna primitiva. En realidade as matrices poden ser utilizadas para conectar dúas ternas primitivas ao chou, sen pasarmos pola (3,4,5)
Para ver uns exemplos, a terna (5,12,13) que mencionei máis arriba aparece cando collemos só a matriz $\small{M_1} $, a (21,20,29) collendo $\small{M_2 }$...
Como era de supoñer, a wikipedia ten un artigo no que podemos ler sobre esta representación matricial. Nel atoparemos a árbore das ternas pitagóricas primitivas. Unha estrutura ben elegante:

Se coñecesemos ben a relación entre as ternas primitivas e os números primos que forman
os parámetros u e v, quizais poderíamos coñecer algo máis dos fuxidíos primos.
Xa está ben de tantas Matemáticas por hoxe. Prometo que o vindeiro post será máis leve...





16.11.13

Matrices e Pitágoras?


Hai anos estaba a ler un libro de historia da Teoría de Números e no epígrafe sobre o problema dos números que poden ser expresados como suma de dous cadrados dei co coñecido resultado:

"Se dous números poden expresarse como suma de dous cadrados entón o seu produto tamén pode ser expresado dese xeito"

Vexamos un caso particular:
$$\small{\begin{cases} 13=3^2+2^2 \\ 17=4^2+1^2 \end{cases}\rightarrow 221=13\cdot17=14^2+5^2}$$
Habitualmente este resultado aparece demostrado utilizando igualdades polinómicas, técnica na que Euler destacou coa súa vista proverbial1. Pero aquel día non sei que tería eu rondando polo miolo, que atopei varios xeitos "naturais" de amosar o devandito resultado.
Enfocando o problema: tentei amosar que, se multiplicamos dous números expresables como suma de dous cadrados, $\small{P=a^2+b^2}$ e $\small{Q=c^2+d^2}$, obtemos outro número PQ, tamén expresable $\small{PQ=(ac-bd)^2+(ad+bc)^2}$

Ao ver a suma de dous cadrados pensei automaticamente nos números complexos, quizais (non o lembro con exactitude) porque pasara pouco tempo desde que factorizara algún polinomio no corpo complexo. E rapidamente apareceu a proba:
$$\small{PQ=(a^2+b^2)(c^2+d^2)=(a+bi)(a-bi)(c+di)(c-di)=}$$
$$\small{(a+bi)(c+di)(a-bi)(c-di)=[(ac-bd)+(ad+bc)i][(ac-bd)-(ad+bc)i]}$$
$$\small{=(ac-bd)^2+(ad+bc)^2}$$

Se tentades traducir esta fórmula ao caso particular de antes, cos números 13 e 17, veredes que obtedes a expresión $\small{221=10^2+(-5)^2=10^2+5^2}$. Para obter a que escribín no exemplo hai que intercambiar os valores de a e b.

Como aquel día estaba con forzas e en Matemáticas unhas ideas conectan axiña con outras, levei isto a outro contexto, o dos determinantes:

Observando que a expresión $\small{a^2+b^2}$ pode tamén escribirse $\small{ \left|  \begin{array}{ccc}
 a & -b \\
 b & a \\
\end{array} \right|} $, xa é directo:

$$\small{ \left|  \begin{array}{ccc}
 a & -b \\
 b & a \\
\end{array} \right| \cdot  \left|  \begin{array}{ccc}
 c & -d \\
 d & c \\
\end{array} \right| =  \left| \left( \begin{array}{ccc}
 a & -b \\
 b & a \\
\end{array}\right) \left( \begin{array}{ccc}
 c & -d \\
 d & c \\
\end{array}\right) \right|= \left| \left( \begin{array}{ccc}
 ac-bd & -(ad+bc) \\
 ad+bc & ac-bd \\
\end{array}\right) \right| }$$

Sospeito que esta ponte entre os complexos e os determinantes debeu de construírse aproximadamente por este camiño: complexos-forma exponencial dos complexos-forma trigonométrica dos complexos- matrices de xiro-determinantes, mais recoñezo que dou paus de cego, pois xa pasaron máis de dez anos. A proba é breve, pero porque oculta o paso esencial que, alén de decatarse da expresión como determinante de a²+b², consiste en utilizar que a aplicación determinante de matrices se comporta ben co produto de matrices (para o connossieur, o determinante é un homomorfismo de grupos entre $\small{M_{n \times n}} $ e $\small{(\mathbb{R},\cdot)} $)

Agora sei que o camiño de utilizar matrices para amosar cuestións de Teoría de Números é certamente natural. Daquela aínda non lera sobre o xeito de expresar recorrencias como a da sucesión de Fibonacci mediante produto de matrices, cousa que agora está "de moda" debido a que aparece en libros de texto do bacharelato, xunto á potenciación de matrices. O método vén sendo:

$$ \left( \begin{array}{ccc}
 F_2  \\
 F_1  \\
\end{array}\right)=\left( \begin{array}{ccc}
 1 & 1 \\
 1 & 0 \\
\end{array}\right) \left( \begin{array}{ccc}
 F_1  \\
 F_0  \\
\end{array}\right) $$
Reiterando a expresión:
$$ \left( \begin{array}{ccc}
 F_3  \\
 F_2  \\
\end{array}\right)=\left( \begin{array}{ccc}
 1 & 1 \\
 1 & 0 \\
\end{array}\right) \left( \begin{array}{ccc}
 F_2  \\
 F_1  \\
\end{array}\right)=\left( \begin{array}{ccc}
 1 & 1 \\
 1 & 0 \\
\end{array}\right)^2 \left( \begin{array}{ccc}
 F_1  \\
 F_0  \\
\end{array}\right) $$

En xeral, e tendo en conta que $\small{F_1=1}$e que $\small{ F_0=0}$ chegamos a que:

$$ \left( \begin{array}{ccc}
 F_{n+1}  \\
 F_n  \\
\end{array}\right)=\left( \begin{array}{ccc}
 1 & 1 \\
 1 & 0 \\
\end{array}\right)^n \left( \begin{array}{ccc}
 1  \\
 0  \\
\end{array}\right) $$

O que leva tamén a que
$$ \left( \begin{array}{ccc}
 F_{n+1} & F_n  \\
 F_n  & F_{n-1}\\
\end{array}\right)=\left( \begin{array}{ccc}
 1 & 1 \\
 1 & 0 \\
\end{array}\right)^n  $$

Como propina, se calculamos os determinantes dos dous membros da igualdade anterior obteremos a famosa identidade de Cassini:
$$F_{n+1}F_{n-1}-F_n^2=(-1)^n$$

Tamén, como a matriz $\small{A=\left( \begin{array}{ccc}
 1 & 1 \\
 1 & 0 \\
\end{array}\right)}$ cumpre obviamente que $\small{A^{m+n}=A^m \cdot A^n}$, obtemos rapidamente que:
$$F_mF_{n+1}+F_{m-1}F_n=F_{m+n}$$
e a súa consecuencia, da que xa falei por acó (xunta o meu pseudo-descubrimento):
$$F_{2n+1}=F_{n+1}^2+F_n^2$$

E o lector que non estea xa mareado a estas alturas de post preguntará "E Pitágoras onde vai?". Vai na continuación deste longo post, permanezan ante os seus aparatos.



1 O de Euler é sobrenatural. Ollade para a identidade que atopou, 200 anos antes dos ordenadores: $$(a_1^2+a_2^2+a_3^2+a_4^2)(b_1^2+b_2^2+b_3^2+b_4^2)=(a_1 b_1 - a_2 b_2 - a_3 b_3 - a_4 b_4)^2 +(a_1 b_2 + a_2 b_1 + a_3 b_4 - a_4 b_3)^2+$$ $$(a_1 b_3 - a_2 b_4 + a_3 b_1 + a_4 b_2)^2 +(a_1 b_4 + a_2 b_3 - a_3 b_2 + a_4 b_1)^2$$

5.11.13

Un starter


No artigo que enlacei por acó, que todos os meus colegas, amigos e familiares tiveron que ler polo menos tres veces, mencionaba brevemente a idea de "Math Starter". O nome en inglés fai que o concepto quede máis rechamante (máis nesta época de estupidez anglófila que nos fai padecer a administración), mais a orixe é ben tradicional: como comentaba aló, todos os profesores de Matemáticas utilizamos dalgún xeito ideas, problemas, situacións... que introducen informalmente os novos contidos que imos traballar. Esta semana utilicei un que pode que outros profesores vexan interesante na unidade de Divisibilidade de 1º de E.S.O. Aínda que a idea implícita é ben coñecida, quizais a "posta en escena" non o sexa tanto. Ollade como funciona:


  • Ao comezo da clase pídolles aos alumnos que escriban no seu caderno un número calquera de 5 cifras.
Imaxinemos que escribe o número 92836
  • Mándolles sumar as cifras dese número.
9+2+8+3+6=28
  • Agora dígolles que resten o que lles deu esa suma do número orixinal:
92836-28=92808

  • Por fin, o desenlace: Dígolle a cada un que risque unha das cinco cifras do número e que me diga as outras catro, se queren desordenadas
O alumno podería riscar un 8, 92808 e dicirme 2-0-8-9


  • Contéstolle ao alumno que riscou un 8. Se o fago case instantaneamente e 20 veces consecutivas, ademais dicíndolle aos alumnos que negan que riscase o número adiviñado que volvan botar as contas, pero esta vez ben, acabo por oír un sonoro oh! de sorpresa, o cal nunha aula de secundaria sempre é de agradecer.

Rematada a actuación, vaiamos ás Matemáticas...

A suma das cifras dun número natural é coñecida de xeito tradicional como "suma dixital". Ten a propiedade de ser congruente módulo 9 co número orixinal, é dicir, o resto que deixa o número ao ser dividido entre 9 é o mesmo que deixa a súa suma dixital. Este é o feito oculto baixo a "proba do 9" que se utilizaba para comprobar a división hai varias xeracións (eu xa nin a utilicei na EXB). Vexamos o número de antes:

92836=10315·9+1
9+2+8+3+6=28=3·9+1

Vemos que efectivamente $\small{92836 \equiv 28 (mod9)}$

Entón, se ao número lle restamos a súa suma dixital obteremos sempre un número divisible entre 9, e aí está a esencia do truco: as cinco cifras que obtemos suman un múltiplo de 9, cando riscan unha e len as outras catro só temos que recuperala calculando canto lle falta á suma desas catro para chegar a un múltiplo de 9. No exemplo, sumamos 2+0+8+9=19 e sabemos que riscaron un 8 para chegar a 27=9·3.

Obviamente o truco ten unha péga: non permite distinguir casos dubidosos, nos que o alumno risca un 0 ou un 9, para obter suma dixital das outras catro cifras múltiplo de 9; así que é útil dicir ao comezo que non risquen un 0, que é o que fago eu, ou xogar a cara e cruz neses casos.
Se alguén quere saber a proba formal da congruencia módulo 9 dun número coa súa suma dixital, é ben breve:

$$\small{a_n a_{n-1} \dots a_1 a_0 =10^n\cdot a_n+10^{n-1}\cdot a_{n-1}+ \dots +10^1\cdot a_1+10^0\cdot a_0 \equiv}$$
$$\small{1^n\cdot a_n+1^{n-1}\cdot a_{n-1}+ \dots +1^1\cdot a_1+1^0\cdot a_0 \equiv  a_n+ a_{n-1}+ \dots + a_1+ a_0 (mod9)}$$

Onde utilizamos que $\small{10\equiv 1(mod9)}$ e que as operacións aritméticas básicas son compatibles coas congruencias. É sinxelo ampliar a proba para sistemas de numeración de base p e a divisibilidade entre p-1. As mesmas ideas utilizaríamos para amosar o criterio de divisibilidade do 11. 


Os profesores que lean o truco pensarán que é algo barato, e que case é máis relevante o xeito de interpretalo, e non lles faltará razón. Pero espero que coincidan comigo en que isto é común no noso traballo. Ata situacións extremas como a que vivín o outro día: despois de explicar o horrible algoritmo da raíz cadrada, oín varios "COMO MOLA!"