Problema dos selos de Frobenius (1)

Todos coñecemos a Frobenius, seguramente en referencia ao teorema de Rouché-Frobenius, que forma parte da materia de Matemáticas II de 2º de Bacharelato:

Teorema de Rouché-Frobenius. Sexa $A\in \mathfrak{M}_{m\times n}$ (unha matriz $m\times n$), a matriz de coeficientes dun sistema de ecuacións lineares, sexa $X\in \mathfrak{M}_{n\times 1}$ o vector de incógnitas e $B\in \mathfrak{M}_{m\times 1}$ o vector de termos independentes. Así $AX=B$ representa un sistema de $m$ ecuacións e $n$ incógnitas. Finalmente sexa a matriz ampliada $A^{*}=(A|B)\in \mathfrak{M}_{m\times (n+1)}$. Daquela

O sistema é compatible $\Longleftrightarrow rang(A)=rang(A^{*}) $ 

É ben curioso que este resultado reciba distintas denominacións polo mundo adiante, atribuíndose en cada unha delas a autoría a persoas distintas. Parece ser que Eugène Rouché (1832-1910)  publicou no 1875 un artigo no que enuncia o xerme do teorema anterior. Ese mesmo ano Georges Fontenè (1848-1923) dá non só unha nova versión, senón que engade tamén unha demostración. No 1880 Rouché publica unha versión máis traballada do seu artigo. Uns anos despois Alfredo Capelli (1885-1910) fai uso do concepto de rango para dar unha nova versión do teorema. Aínda outra máis viría da man de Leopold Kronecker (1823-1891) e finalmente un alumno seu, Ferdinand Georg Frobenius (1849-1917) publica un artigo co teorema recoñecendo a autoría aos matemáticos franceses. Que nos países de fala hispana sexa coñecido como teorema de Rouché-Frobenius débese a Julio Rey Pastor (1888-1962).

O problema dos selos de Frobenius

Despois desta innecesaria digresión recollida de Pimedios, presentamos o problema de Frobenius:

Problema de Frobenius. Dados os números naturais $a_{1},a_{2},...,a_{n}$ de máximo común divisor $1$, determinar o maior natural que non pode poñerse como combinación linear deles.

O problema permanece aberto cando temos $3$ ou máis números . O caso con dous números, resolto por James Joseph Sylvester (1814-1897) será o que abordaremos aquí. 

Problema dos selos de Frobenius. Supoñamos que os selos de correos teñen unicamente dous valores,  $a$ e $b$, con $a$ e $b$ coprimos. Dispoñemos dunha cantidade ilimitada de selos de ambos tipos. Trátase de determinar cal é a maior cantidade que non pode ser obtida facendo uso deses selos.

A primeira cuestión que nos asalta é sobre a necesidade de que $a$ e $b$ teñan que ser coprimos. Se non o fosen, pensemos por exemplo no caso $a=2$ e $b=4$. Non poderiamos obter nunca resultados impares. Pola contra

Teorema 1. Se $a$ e $b$ son coprimos, a cantidade de sumas que non se pode conseguir usando selos deses dous valores é finita.

Un dos nosos obxectivos será o de presentar unha (fermosa) demostración deste teorema. Para irlle collendo o sabor á cuestión, resolvamos primeiro un caso particular.

Sempre xuntos

 

Problema dos selos de Frobenius.Caso concreto. Dispoñemos de selos de correos de só dous valores, $4$ e $7$ céntimos. Cal é a maior cantidade que non pode ser obtida facendo uso deses selos? 

Sempre podemos facer un intento de abordar o problema pola forza bruta. Iso si, se o facemos con algo de orde e sistematicamente veremos que podemos chegar a algunha primeira conxectura.

a\b	0	1	2	3	4	5
0	0	7	14	21	28	35
1	4	11	18	25	32	39
2	8	15	22	29	36	43
3	12	19	26	33	40	47
4	16	23	30	37	45	51
5	20	27	34	41	49	55

Repasando a táboa cun pouco de atención decatarémonos de que a partir do $18$ van ir aparecendo todos os naturais. Velaí que o maior número que non podemos construír co $4$ e o $7$ é o $17=4 \cdot 7-4-7$. En xeral verificarase o seguinte teorema:

Teorema 2. Dados dous naturais coprimos $a$ e $b$, a maior cantidade que non podemos conseguir mediante unha combinación linear deles é $a\cdot b-a-b$

Pasemos a demostrar estes teoremas.

Demostración do Teorema 1

A demostración do Teorema 1 recólloa dun libro que é un goce en cada unha das súas páxinas, Beautiful Mathematics (MAA 2011) de Martin Erickson. Alí, despois deste resultado, Erickson demostra outros relacionados co problema usando funcións xeneradoras. O que trasladamos aquí vai por outro camiño, un que me parece especialmente fermoso e sorprendente, pois fai uso de ténicas de xeometría analítica moi básicas, tanto que están ao nivel do que se pide na ESO. Aínda hai outra sorpresa máis. A demostración comeza facendo uso do lema de Bezout:

Lema de Bezout. Sexan $a$ e $b$ enteiros e sexa $d$ o seu máximo común divisor. Entón existirán $x$ e $y$ enteiros tales que $ax+by=d$

No noso caso $a$ e $b$ son coprimos, daquela existen outros enteiros $x_{0}$ e $y_{0}$ de forma que $$ax_{0}+by_{0}=1\quad \quad [1]$$ Por exemplo, para caso particular proposto de $a=4$ e $b=7$, os valores de $x_{0}$ e $y_{0}$ serán respectivamente $2$ e $-1$. Así escribiremos acertadamente que $2\cdot 4 - 1 \cdot 7 = 1$ Reparemos que un dos valores é negativo. Confirmamos, xa que logo, que en xeral $x_{0}$ e $y_{0}$ non teñen por que ser positivos.

Sexa $c\gt ab$, imos ver que existen naturais (positivos) $x$ e $y$ tales que $ax+by=c$. Aquí quería facer unha observación terminolóxica. Os puntos de $\mathbb{Z}^{2}\subset \mathbb{R}^{2}$ reciben en inglés o nome de "lattice points". En galego o termo que usaremos será o de "puntos da retícula". 

Se multiplicamos identidade [1] por $c$ temos que $acx_{0}+bcy_{0}=c$. Isto significa que a recta $r:\,  ax+by=c$ contén un punto da retícula, o punto $\left( cx_{0} , cy_{0}\right)$.  Pero, como xa advertimos anteriormente, non temos asegurado que esas coordenadas sexan positivas. De feito, posiblemente non o sexan. Pero poderemos buscar outro punto desa mesma recta que si teña coordenadas naturais (enteiras e positivas). Para iso faremos un estudo da recta $r:\,  ax+by=c$. Lembremos que $a, b, c\gt 0$. O vector director de $r$ é $\overrightarrow{v_{r}}=\left( -b,a \right)$ e a súa pendente $m=-\frac{a}{b}\lt 0$. Velaí que $r$ é decrecente. Ademais corta aos eixos de coordenadas en valores positivos $\left( \frac{c}{a},0 \right)$ e $\left( 0,\frac{b}{a} \right)$. Un debuxo axudaranos a entender mellor a situación.

A distancia entre os puntos de corte da recta $r$ cos eixos: $\sqrt{\left( \frac{c}{a} \right)^{2}+\left(\frac{c}{b}  \right)^{2}}$

Dado o punto de $r$ de coordenadas enteiras  $\left( cx_{0} , cy_{0}\right)$ podemos ir achando outros puntos da recta que tamén pertenzan á retícula desprazándonos $b$ unidades en horizontal e $a$ unidades en vertical. Disto sacamos dúas conclusións. Unha, que a distancia entre dous puntos da recta consecutivos con coordenadas enteiras distan entre si $\sqrt{a^{2}+b^{2}}$ unidades. E dúas: calquera outro punto de $r$ de coordenadas enteiras terá a forma $(cx_{0}+bt,cy_{0}-at)$ con $t\in \mathbb{Z}$.

Como partimos de que $c\gt ab$ temos que $\frac{c}{ab}\gt 1$. Multiplicando ambos membros da desigualdade por $\sqrt{a^{2}+b^{2}}$ temos que

$$\frac{c}{ab}\sqrt{a^{2}+b^{2}}\gt \sqrt{a^{2}+b^{2}}$$

$$\sqrt{\left( \frac{c}{b} \right)^{2}+\left( \frac{c}{a} \right)^{2}}\gt \sqrt{a^{2}+b^{2}}$$

A distancia entre dous puntos consecutivos de $r$ pertencentes á retícula é menor que o segmento de $r$ que está no primeiro cuadrante. En conclusión, ten que haber un punto de $r$ con ambas coordenadas positivas, que era o que queriamos demostrar.

Como a lonxitude desta entrada vai sendo considerable, deixaremos para a seguinte a demostración do Teorema 2. Será unha demostración que garda unha sorpresa fantástica.

A selección natural de exercicios (e 2)

Na entrada anterior xa adiantaba que resolvería o seguinte exercicio:

Exercicio 1. Determina o ángulo que forman as funcións $f(x)=\sqrt{1-x^{2}}$ e $f'(x)$ no punto de corte.

Respecto doutros deste mesmo tipo, este ten a orixinalidade de que non se dan dúas funcións, senón só unha (e a súa derivada). A curiosidade lévanos a determinar esa derivada:

$f'(x)=-\frac{x}{\sqrt{1-x^{2}}}$

Achemos o punto de corte de $f$ e $f'$:

$\sqrt{1-x^{2}}=-\frac{x}{\sqrt{1-x^{2}}}$

$1-x^{2}=-x$

$x^{2}-x-1=0$

Chegamos a unha ecuación cadrática ben famosa, a que ten como solucións  $x_1=\phi=\frac{1+\sqrt{5}}{2}$, o número áureo, e $x_2=\frac{1-\sqrt{5}}{2}=-\frac{1}{\phi}$. Desbotamos a primeira e quedámonos coa segunda. A razón está en cal é o punto de corte de $f$, a semicircunferencia superior de raio $1$  e $f'$ 

$$f(\frac{-1}{\phi})=\sqrt{1-\frac{1}{\phi^{2}}}=\sqrt{\frac{\phi^{2}-1}{\phi^{2}}}=\sqrt{\frac{\phi}{\phi^{2}}}=\sqrt{\frac{1}{\phi}}=f'\left( \frac{1}{\phi} \right)=tan\alpha$$

Para calcular a pendente da recta tanxente a $f'$ temos que calcular a súa derivada $f''$:

$$f''(x)=-\frac{\sqrt{1-x^2}+\frac{x^2}{\sqrt{1-x^2}}}{1-x^2}=-\frac{1-x^2+x^2}{\left( 1-x^2 \right)\sqrt{1-x^2}}=-\frac{-1}{\left( 1-x^2 \right)^{\frac{3}{2}}}$$

$$f''(-\frac{1}{\phi})=-\frac{1}{\left( 1-\frac{1}{\phi^2} \right)^{\frac{3}{2}}}=-\frac{1}{\left( \frac{\phi^2-1}{\phi^2} \right)^{\frac{3}{2}}}=-\frac{1}{\left( \frac{1}{\phi} \right)^{\frac{3}{2}}}=-\phi^\frac{3}{2}=-\sqrt{\phi^3}=-\phi\sqrt{\phi}=tan\beta$$

Sexa $\gamma=\alpha - \beta$:

$$tan\gamma=tan\left( \alpha-\beta \right)=\frac{tan\alpha-tan\beta}{1+tan\alpha\cdot tan\beta}=\frac{\frac{1}{\sqrt{\phi}}+\phi\sqrt{\phi}}{1-\frac{1}{\sqrt{\phi}}\phi\sqrt{\phi}}=\frac{\frac{1+\phi^2}{\sqrt{\phi}}}{1-\phi}=\frac{\phi+2}{\sqrt{\phi}\left( 1-\phi \right)}$$

Como despois de achar esta alfaia estou seguro de que as ansias de seguir pescudando un tesouro non fixeron outra cousa que incrementarse, regalaremos un par de exercicios máis.

Exercicio 2. Determina o ángulo que forman as funcións $f(x)=cosx$  e  $g(x)=tanx$ no primeiro punto de corte despois da orixe.

Exercicio 3. Determina o ángulo que forman as funcións $f(x)=senhx$  e  $g(x)=cothx$ no primeiro punto de corte despois da orixe.

A selección natural de exercicios (1)

Segundo o principio da selección natural, aqueles organismos mellor adaptados ao medio serán os que sobrevivan fronte a outros que acaban desaparecendo. Do mesmo xeito aqueles exercicios que aparecen nos libros de texto son o que teñen máis posibilidades de reproducirse nas aulas de Matemáticas. En particular, como as aulas de 2º de bacharelato só en parte están orientadas ao ensino, na medida en que funcionan como unha academia para preparar a selectividade, os exercicios destas probas teñen asegurado o seu espazo. Daquela, dependendo da orientación que lle vaian dando os grupos de traballo, veremos tamén como cambian os tipos de exercicios que o profesorado levamos á aula. 

PAAU 2020. Convocatoria ordinaria. Exercicio 3. Determine os valores de b e c para que a función $$f(x)= \left\{ \begin{array}{cl} e^{2x} & se \ x \leq 0 \\ x^{2}+bx+c & se \ x > 0 \end{array} \right.$$   sexa primeiro continua e logo derivable, en x=0

Imos dar a solución do exercicio seguindo as indicacións do grupo de traballo das PAU. 

Como $\displaystyle \lim_{x \to 0^{-}} f(x)=\displaystyle \lim_{x \to 0^{-}}e^{2x}=1=e^{0}=1$. para que $f$ sexa continua en $x=0$ o límite pola dereita ten que ser so mesmo: $\displaystyle \lim_{x \to 0^{+}} f(x)=\displaystyle \lim_{x \to 0^{+}}x^{2}+bx+c=c=1$. Daquela $f$ será continua cando $c=1$ 

En canto á derivabilidade, como para que $f$ o sexa en $x=0$, debe ser necesariamente continua, partiremos de que $c=1$: $$f(x)= \left\{ \begin{array}{cl} e^{2x} & se \ x \leq 0 \\ x^{2}+bx+1 & se \ x > 0 \end{array} \right.$$ Derivamos: $$f'(x)= \left\{ \begin{array}{cl}2 e^{2x} & se \ x < 0 \\ 2x+b & se \ x > 0 \end{array} \right.$$ Pasemos a calcular os límites laterais da derivada na orixe:$\displaystyle \lim_{x \to 0^{-}} f'(x)=\displaystyle \lim_{x \to 0^{-}}2e^{2x}=2$. Como o $\displaystyle \lim_{x \to 0^{+}} f'(x)=\displaystyle \lim_{x \to 0^{+}}2x+b=b$, para que a función sexa derivable no cero, $b=2$ (e $c=1$).

Unha vez rematado este repaso pode que haxa quen quede satisfeito pero a min quédame unha molestia no corpo, unha intranquilidade que vén do ensino das matemáticas que eu mesmo recibín. Aquí hai algo que proe: dá a impresión que se unha función $f$ é derivable, parece que esta derivada, $f'$, ten que ser necesariamente continua e resulta que isto non é certo. A mellor forma de certificalo é dando un deses marabillosos contraexemplos dos que está inzado o cálculo diferencial. 

As inconsistencias e os exemplos mostruosos que comezaron a abrollar no cálculo no transcurso do XIX acabaron derivando nunha análise moito máis profunda e demorada desta rama das matemáticas. É o cocñecido proceso histórico da aritmetización do cálculo da que Karl Weierstrass foi figura destacada. Agora aquí toca traer un deses exemplos cos que no primeiro ano da carreira se comeza a enxergar a profunza fermosura das matemáticas.$$ f(x)=\left\{\begin{matrix} x^2sen(\frac{1}{x}) \ se\quad x\neq 0 \\0 \quad \quad se \ x=0 \end{matrix}\right.$$  

Podemos comprobar que a seguinte expresión é a súa derivada:$$ f'(x)=\left\{\begin{matrix} 2xsen(\frac{1}{x})-cos(\frac{1}{x}) \ se\ x\neq 0 \\0 \quad \quad \quad \quad \quad \quad se \ x=0 \end{matrix}\right.$$  

En efecto, $f$ é derivable en $x=0$: $$f'(0)=\displaystyle \lim_{x \to 0}\frac{f(x)-f(0)}{x-0}=\displaystyle \lim_{x \to 0}\frac{x^{2}sen\left ( \frac{1}{x} \right )}{x}=\displaystyle \lim_{x \to 0}xsen(\frac{1}{x})=0$$  

Porén $f'$ non pode ser continua na orixe porque $cos(\frac{1}{x}) $ oscila brutalmente no entorno do $0$. 

Á esquerda da imaxe vemos a gráfica de $f$ limitada polas funcións punteadas $\pm x^2$ e á dereita a gráfica da derivada, $f'$  

En conclusión, o profesorado de matemáticas de 2º de bacharelato estamos contribuíndo a espallar unha idea falsa entre o alumnado por traballar un tipo de exercicios que se desde a CIUG puxeron de moda desde hai uns poucos anos. 

Fronte a isto vou contrapoñer outro modelo de exercicios que nunca vin nin na selectividade, nin tan sequera nos libros de texto. Non vou ser orixinal, porque recollo o exercicio de entre os que me propuxeran a min cando era estudante de 3º de BUP. Lembro perfectamente que me impresionara moi positivamente, en primeiro lugar pola súa dificultade. Non fóra quen de abordalo. Con todo, quedara encantado con el porque  me decatara inmediatamente de que usando a mesma técnica podía calcular o ángulo que forman dúas curvas que se cortan nun punto.

Exercicio de 3º de BUP. Determina o ángulo que forman as funcións $f(x)=x^2$ e $g(x)=\sqrt{x}$ no punto $(1,1)$

Un debuxo axuda a explicar o método de resolución.

Está claro que o ángulo buscado vén dado pola seguinte diferenza: $ \gamma =\alpha -\beta $. O que nos convén é usar unha fórmula trigonométrica, a da tanxente dunha diferenza de ángulos,  que forma parte do currículo de 1º de bacharelato e que daquela, cando se introduce na aula,  parece deses típicos ítems dos que nunca se vai botar man, unha desas cousas inútiles que fai máis difícil a existencia cando non forman parte do noso coñecemento e que nos levan a afirmar: que triste é a vida do que non sabe matemáticas!

$f'(x)=2x; \quad f'(1)=2=tan \alpha$

$g'(x)=\frac{1}{2\sqrt{x}}; \quad g'(1)=\frac{1}{2}=tan\beta$ É o momento de usar a citada fórmula:

$$tan\gamma=tan(\alpha-\beta)=\frac{tan\alpha-tan\beta}{1+tan\alpha \cdot tan\beta}=\frac{2-\frac{1}{2}}{1+2\frac{1}{2}}=\frac{3}{4}$$

Curiosamente o ángulo buscado é un ángulo agudo do triángulo pitagórico máis sinxelo, o de lados 3, 4 e 5, e que coñece todo albanel.

Para rematar deixo como regalo outro exercicio deste mesmo estilo que foi o que me moveu a escribir esta entrada pois ten unha pequena alfaia gardada. 

Se teño folgos, na seguinte entrada paso o traballo de escribir o $\LaTeX{}$ da solución; claro que, a quen chege ata aquí non lle paga a pena agardar pois calquera que entenda as anteriores liñas ben pode facelo por si mesmo.

Exercicio 1. Determina o ángulo que forman as funcións $f(x)=\sqrt{1-x^{2}}$ e $f'(x)$ no seu punto de corte.

Todos os camiños levan a Roma (e 2)

Na entrada anterior propoñíamos un problema sobre grafos. De entre todos os tipos de grafos, podemos concordar en que os máis simples son os denominados grafos camiño ou grafos lineares. O grafo linear de lonxitude $n$ denótase $P_{n}$. Ilustraremos a idea co grafo linear $P_{4}$:

Camiños nun grafo linear. Cantos camiños de lonxitude $k$ hai entre os vértices de $P_{4}$?

Trátase de determinar a matriz dos camiños de lonxitude $k$ de $P_{4}$. Nesa referida entrada xa explicaramos o camiño a seguir para obter a solución. Debemos comezar pola matriz de adxacencia do grafo: $$A=\begin{pmatrix} 0 & 1& 0& 0 \\ 1 & 0 & 1 & 0\\ 0 & 1 & 0 &1 \\ 0 & 0& 1& 0 \end{pmatrix}$$

A solución virá dada polas potencias da matriz de adxacencia. O elemento $(i,j)$ de $A^{k}$ indícanos o número de camiños de lonxitude $k$ entre os nodos $i$ e $j$. 

$A^{2}=\begin{pmatrix} 1 & 0&1 & 0\\ 0& 2 & 0 & 1\\ 1 & 0 & 2 & 0\\ 0 & 1 & 0& 1 \end{pmatrix}$ ; $A^{3}=\begin{pmatrix} 0 & 2& 0 & 1\\ 2& 0& 3 & 0\\ 0& 3& 0& 2\\ 1 & 0 &2 & 0 \end{pmatrix}$  ;   $A^{4}=\begin{pmatrix} 0 & 2 & 3&0 \\ 0& 5& 0&3 \\ 3& 0& 5&0 \\ 0 & 3& 0 & 2 \end{pmatrix}$   ;   $A^{5}=\begin{pmatrix} 0 & 5& 0 &3 \\ 5 & 0 & 8& 0 \\ 0& 8 & 0 & 5 \\ 3& 0& 5 & 0 \end{pmatrix}$

Curiosamente os elementos das matrices son vellos coñecidos. Efectivamente, son números da sucesión de Fibonacci (de aí o título da entrada: "Todos os camiños levan a Roma"; se para os de clásicas o centro do mundo se situa en Roma, os de matematemáticas caemos indefectiblemente na sucesisión argallada por Leonardo de Pisa). Volvamos a lembrar en que consiste a famosa sucesión:

$f_0$	$f_1$	$f_2$	$f_3$	$f_4$	$f_5$	$f_6$	$f_7$	$f_8$	$f_9$	$f_{10}$	$f_{11}$	$f_{12}$	$...$	$f_k$
$0$	$1$	$1$	$2$	$3$	$5$	$8$	$13$	$21$	$34$	$55$	$89$	$144$	$...$	$f_{k-1}+f_{k-2}$

Parece bastante evidente que as potencias pares seguen un patrón distinto das potencias impares. Seguindo a Martin Erickson en Beautiful Mathematics (MAA 2011)  conxecturaremos que:

Se $k$ é par: $A^{k}=\begin{pmatrix} f_{k-1} & 0&f_{k} & 0\\ 0& f_{k+1} & 0 & f_{k}\\ f_{k} & 0 & f_{k+1} & 0\\ 0 & f_{k} & 0& f_{k-1} \end{pmatrix}$

Se $k$ é impar: $A^{k}=\begin{pmatrix} 0 & f_{k}& 0 & f_{k-1}\\ f_{k}& 0& f_{k+1} & 0\\ 0& f_{k+1}& 0& f_{k}\\ f_{k-1} & 0 &f_{k} & 0 \end{pmatrix}$

Demostraremos por indución que este resultado é certo. Xa comprobamos máis arriba que o é para os valores de $k=1$, $k=2$, $k=3$, $k=4$ e $k=5$, algúns deles pares, outros impares. Supoñamos as fórmulas certas para un determinado valor $k$ e comprobaremos que serven para $k+1$.

Se $k$ é par: $A^{k+1}=A^{k}A=\begin{pmatrix} f_{k-1} & 0&f_{k} & 0\\ 0& f_{k+1} & 0 & f_{k}\\ f_{k} & 0 & f_{k+1} & 0\\ 0 & f_{k} & 0& f_{k-1} \end{pmatrix} \begin{pmatrix} 0 & 1& 0& 0 \\ 1 & 0 & 1 & 0\\ 0 & 1 & 0 &1 \\ 0 & 0& 1& 0 \end{pmatrix}=\begin{pmatrix} 0 & f_{k-1}+f_{k}& 0 & f_{k}\\ f_{k+1}& 0& f_{k+1}+f_{k} & 0\\ 0& f_{k}+f_{k+1}& 0& f_{k+1}\\ f_{k-1} & 0 &f_{k}+f_{k-1} & 0 \end{pmatrix}=$ $=\begin{pmatrix} 0 & f_{k+1}& 0 & f_{k}\\ f_{k+1}& 0& f_{k+2} & 0\\ 0& f_{k+2}& 0& f_{k+1}\\ f_{k} & 0 &f_{k+1} & 0 \end{pmatrix}$

Se $k$ é impar:

$A^{k+1}=A^{k}A=\begin{pmatrix} 0 & f_{k}& 0 & f_{k-1}\\ f_{k}& 0& f_{k+1} & 0\\ 0& f_{k+1}& 0& f_{k}\\ f_{k-1} & 0 &f_{k} & 0 \end{pmatrix} \begin{pmatrix} 0 & 1& 0& 0 \\ 1 & 0 & 1 & 0\\ 0 & 1 & 0 &1 \\ 0 & 0& 1& 0 \end{pmatrix}=\begin{pmatrix} f_{k} & 0&f_{k}+f_{k-1} & 0\\ 0& f_{k}+f_{k+1} & 0 & f_{k+1}\\ f_{k+1} & 0 & f_{k+1}+f_{k} & 0\\ 0 & f_{k-1}+f_{k} & 0& f_{k} \end{pmatrix}=$

$=\begin{pmatrix} f_{k} & 0&f_{k+1} & 0\\ 0& f_{k+2} & 0 & f_{k+1}\\ f_{k+1} & 0 & f_{k+2} & 0\\ 0 & f_{k+1} & 0& f_{k} \end{pmatrix}$

Todos os camiños levan a Roma (1)

Non sei se agora se estuda algo de teoría de grafos no grao de Matemáticas. Na miña época non se tocaba ese tema, por iso eu non teño nin idea sobre o asunto. Con todo, como son algo atolondrado, non é esta a primeira entrada do blogue que leva a etiqueta "grafos". Ao meu favor teño que todas esas entradas son moi básicas pois nada hai que saber de teoría de grafos para poder seguilas sen dificultade. Velaquí un novo exemplo no que verificar esta afirmación. 

Vou poñer como referencia un texto de divulgación, En busca del grafo perdido (Ariel, 2021), escrito por Clara Grima. Nun dos seus capítulos, para explicar o que é a matriz de adxacencia dun grafo, recolle unha escena da película do 1997 O indomable Will Hunting (Good Will Hunting) na que un profesor do mítico MIT (Massachusetts Institute of Technology) propón o seguinte problema:

A matriz de adxacencia deste grafo será: $$ A=\begin{pmatrix} 0 & 1& 0& 1\\ 1& 0 &2 & 1 \\ 0 &2 & 0 & 0 \\ 1& 1& 0 & 0 \end{pmatrix} $$

Onde cada elemento $a_{ij}$ indica o número de arestas que conectan o vértice $i$ co vértice $j$. A propia matriz describe o número de camiño de lonxitude $1$ entre os vértices. Que pasa cos camiños de lonxitude $2$, isto é, os formados por dúas arestas?

O vértice $1$ pode conectarse consigo mesmo por medio de dúas arestas de dúas formas: $(1,2,1)$ e $(1,4,1)$. 

Ese mesmo vértice pode conectarse co vértice $2$ mediante un único camiño de lonxitude $2$: $(1,4,2)$. 

O vértice $1$ pode conectarse mediante dous camiños de lonxitude $2$ co vértice $3$: $(1,2,3)$ seguindo a aresta superior, e outro seguindo a aresta inferior.

Finalmente o vértice $1$ pode conectarse co vértice $4$ mediante un único camiño de dúas arestas, o camiño $(1,2,4)$

Resumindo, o número de camiños cos que o vértice $1$ pode conectarse con todos os vértices do grafo virá dado polos elementos da  fila $\begin{pmatrix} 2 & 1 & 2 &1 \end{pmatrix}$. Se fixeramos o mesmo co resto dos vértices obteriamos a seguinte matriz:$$A^{2}=\begin{pmatrix} 0 & 1& 0& 1\\ 1& 0 &2 & 1 \\ 0 &2 & 0 & 0 \\ 1& 1& 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1& 0& 1\\ 1& 0 &2 & 1 \\ 0 &2 & 0 & 0 \\ 1& 1& 0 & 0 \end{pmatrix} =\begin{pmatrix} 2 & 1& 2& 1\\ 1& 6 &0 & 1 \\ 2 &0 & 4 & 2 \\ 1& 1& 2 & 2 \end{pmatrix} $$  

Efectivamente, os camiños de lonxitude $2$ virán indicados polos coeficientes da matriz $A^{2}$. En xeral os coeficientes de $A^{n}$ resolven o problema de determinar a cantidade de camiños de lonxitude $n$. Daquela, a solución da segunda pregunta do problema da película obtense así:

$$A^{3}=A^{2}A=\begin{pmatrix} 2 & 1& 2& 1\\ 1& 6 &0 & 1 \\ 2 &0 & 4 & 2 \\ 1& 1& 2 & 2 \end{pmatrix} \begin{pmatrix} 0 & 1& 0& 1\\ 1& 0 &2 & 1 \\ 0 &2 & 0 & 0 \\ 1& 1& 0 & 0 \end{pmatrix}=\begin{pmatrix} 2 & 7& 2& 3\\ 7& 2 &12 & 7 \\ 2 &12 & 0 & 2 \\ 3& 7& 2 & 2 \end{pmatrix}$$

Ben, ata aquí temos todos os vimbios para propoñer, e resolver, un problemiña.

Un problema simple

De entre todos os tipos de grafos, podemos concordar en que os máis simples son os denominados grafos camiño ou grafos lineares. O grafo linear de lonxitude $n$ denótase $P_{n}$. Ilustraremos a idea co grafo linear $P_{4}$:

Camiños nun grafo linear. Cantos camiños de lonxitude $k$ hai entre os vértices de $P_{4}$?

Trátase de determinar a matriz dos camiños de lonxitude $k$ de $P_{4}$. Para saborear o problema podemos abordar primeiro algúns casos máis simples. Poderiamos comezar estudando os camiños de $P_{2}$:

A matriz de adxacencia deste grafo será $A=\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$; como $A^{2}=\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}=I$ teremos que :

$A^{k}=\begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix}=A$ se $k$ é impar e $A^{k}=\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}=I$ se $k$ é par.

Que sucede no caso de $P_{3}$? Mirando o grafo

Vemos que a súa matriz de adxacencia é $A=\begin{pmatrix} 0 &1 & 0 \\ 1&0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$  polo que $A^{2}=\begin{pmatrix} 1 &0 & 1 \\ 0&2 & 0 \\ 1 & 0 & 1 \end{pmatrix}$ ; $A^{3}=\begin{pmatrix} 0 &2 & 0 \\ 2&0 & 2 \\ 0 & 2 & 0 \end{pmatrix}=2\begin{pmatrix} 0 &1 & 0 \\ 1&0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$;         $A^{4}=\begin{pmatrix} 2 &0 & 2 \\ 0&2 & 0 \\ 2& 0 & 2 \end{pmatrix}=2\begin{pmatrix} 1 &0 & 1 \\ 0&2 & 0 \\ 1 & 0 & 1 \end{pmatrix}$ ; $A^{5}=\begin{pmatrix} 0 &4 & 0 \\ 4&0 & 4 \\ 0 & 4 & 0 \end{pmatrix}=4\begin{pmatrix} 0 &1 & 0 \\ 1&0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$;         $A^{6}=\begin{pmatrix} 4 &0 & 4 \\ 0&8 & 0 \\ 4& 0 & 4 \end{pmatrix}=4\begin{pmatrix} 1 &0 & 1 \\ 0&2 & 0 \\ 1 & 0 & 1 \end{pmatrix}$  

Xa se ve como vai continuar.

Agora é o momento de abordar o problema orixinal, o dos camiños de $P_{4}$. É o teu turno. Prométoche que ten premio. Nunha próxima entrada, darei a solución.

A fórmula de Lehmer

De revisarmos as etiquetas das entradas deste blogue, comprobariamos que hai moitas con referencias ao número aúreo ou á sucesión de Fibonacci. A razón é ben evidente. Aquí tratamos matemáticas bonitas e non difíciles. Resulta que eses temas están adornados con estas condicións, consecuentemente volvemos a eles unha e outra vez. Sendo isto así estaría tentado a recoller ducias de resultados dalgún libro que trata estas cuestións como é o caso de Fibonaccci and Lucas Numbers with Applications (Wiley, 2011), escrito por Thomas Koshy e do que xa se editou un segundo tomo. Así e todo voume centrar nunha única fórmula polo extraordinaria que resulta ser. Koshy atribúella a D. H. Lehmer (1905-1991), incluso nos informa que data concretamente do 1936, cando Lehmer estaba na Universidade de Lehigh. Todos coñecemos a relación entre a sucesión de Fibonacci $\left\{ f_{n} \right\}$ e o número áureo $\phi$. No entanto a fórmula de Lehmer pon en relación a sucesión de Fibonacci con outro número ubicuo, o número $\pi$:

Fórmula de Lehmer. $$\sum_{n=1}^{\infty }arctan\frac{1}{f_{2n+1}}=\frac{\pi}{4}$$

Recordemos, unha vez máis, en que consiste a sucesión de Fibonacci:

$f_0$	$f_1$	$f_2$	$f_3$	$f_4$	$f_5$	$f_6$	$f_7$	$f_8$	$f_9$	$f_{10}$	$f_{11}$	$f_{12}$	$...$	$f_n$
$0$	$1$	$1$	$2$	$3$	$5$	$8$	$13$	$21$	$34$	$55$	$89$	$144$	$...$	$f_{n-1}+f_{n-2}$

Para poder deducir a fórmula precisaremos de dous lemas. O primeiro deles é ben coñecido, e xa o temos usado noutras entradas deste blogue. Trátase do:

Lema 1. Fórmula de Cassini. $f_{k+1}\cdot f_{k-1}-f_{k}^{2}=\left( -1 \right)^{n}$

A fórmula de Cassini é un lema do lema 2, pois empregarémola para demostralo. Trátase doutra fórmula:

Lema 2. $arctan\frac{1}{f_{2n+1}}=arctan\frac{1}{f_{2n}}-arctan\frac{1}{f_{2n+2}}$

A demostración é bastante natural. Calcularemos a tanxente do segundo membro e veremos que é $\frac{1}{f_{2n+1}}$. Para iso aplicamos a fórmula da tanxente dunha resta (lembrade as clases de 1º de bacharelato)

$$tan\left( \alpha-\beta \right)=\frac{tan\alpha-tan\beta}{1+tan\alpha \cdot tan\beta}$$

$$tan\left( arctan\frac{1}{f_{2n}}-arctan\frac{1}{f_{_{2n+2}}} \right)=\frac{\frac{1}{f_{2n}}-\frac{1}{f_{2n+2}}}{1+\frac{1}{f_{2n}}\cdot \frac{1}{f_{2n+2}}}=$$

$$=\frac{f_{2n+2}-f_{2n}}{f_{2n}f_{2n+2}+1}=\frac{f_{2n+1}}{f_{2n}f_{2n+2}+1}=(*)$$

Agora simplifaremos o deniminador por medio da fórmula de Cassini. Efectivamente, tomando $k=2n+1$ a fórmula de Cassini queda:

$$f_{2n+2}\cdot f_{2n}-f_{2n+1}^{2}=\left( -1 \right)^{2n+1}=-1$$

Despexando $f_{2n+1}^{2}$:

$$f_{2n+1}^{2}=f_{2n+1}\cdot f_{2n}+1$$

Continuamos e rematamos coa demostración do lema 2:

$$(*)=\frac{f_{2n+1}}{f_{2n+1}^{2}}=\frac{1}{f_{2n+1}}$$

Co lema 2 na faltriqueira a obteción da fórmula de Lehmer é un xogo infantil. En primeiro lugar calcularemos a serie de sumas parciais, que se simplifica moito porque se cancelan todos os termos agás o primeiro e mais o último:

$$\sum_{n=1}^{m}arctan\frac{1}{f_{2n+1}}=\sum_{n=1}^{m}\left( arctan\frac{1}{f_{2n}}-arctan\frac{1}{f_{2n+2}} \right)=$$ $$=arctan\frac{1}{f_{2}}-arctan\frac{1}{f_{2m+2}}=\frac{\pi}{2}-arctan\frac{1}{f_{2m+2}}$$

Para obter a suma da serie bastará con aplicar límites:

$$\sum_{n=1}^{\infty }arctan\frac{1}{f_{2n+1}}=\lim_{m \to \infty }\left( \sum_{n=1}^{m}arctan\frac{1}{f_{2n+1}} \right)= \lim_{m \to \infty } \left( \frac{\pi}{4}-arctan\frac{1}{f_{2m+2}} \right)=\frac{\pi}{4}-arctan \, 0=\frac{\pi}{4}$$

A serie comeza con $m=1$, isto significa que o primeiro sumando é o arcotanxente do inverso de $f_3$. Porén, se quixermos obter a suma de todos os arcotanxentes dos inversos dos termos impares da sucesión de Fibonacci só teriamos que engadir un termo, $arctan\frac{1}{f_{1}}=arctan1=\frac{\pi}{4}$. Deste xeito, a suma completa daría $\frac{\pi}{2}$:

$$\frac{\pi}{2}=arctan\frac{1}{1}+arctan\frac{1}{2}+arctan\frac{1}{5}+arctan\frac{1}{13}+arctan\frac{1}{34}+arctan\frac{1}{89}+...$$

Unha elipse e un círculo. Un cadrado e unha semicircunferencia

 Se dixera de onde recollín este problema seguramente saberías a solución sen ter que darlle ningunha volta. Daquela, como na entrada anterior, non revelarei ata o final a orixe desta proposta. Agora ben, como non vou revelalo ata o final, seguramente saberás cal é a solución.

Unha elipse e un círculo. Consideremos a elipse de semieixos $a$ e $b$. Pídese determinar para que valor da razón $\frac{b}{a}$ o círculo que pasa polos seus focos ten a mesma área que a elipse.

A cuestión é de resolución tan sinxela que non merecería espazo algún. Con todo, como este blogue non ten entre os seus méritos desprezar ningún razoamento, por simple que poida parecer, velaquí vai a solución:

A área da elipse é $\pi a b$, a do círculo será $\pi c^{2}$ onde $c^{2}=a^{2}-b^{2}$. Igualando as áreas: $$\pi ab=\pi c^{2}=\pi\left( a^{2}-b^{2} \right)$$

$$ ab=a^{2}-b^{2}$$

Dividindo por $a^{2}$: $$\frac{b}{a}=1-\frac{b^{2}}{a^{2}}$$ $$\frac{b^{2}}{a^{2}}+ \frac{b}{a}-1=0$$

Esta coñecida ecuación ten como solución positiva o número áureo $\phi=\frac{1+\sqrt{5}}{2}$

Por certo, noutra ocasión xa aparecera por este blogue un problema tan semellante a este que poderiamos dicir que son equivalenten. Trátase do problema 8 da entrada Problemas consecutivos

Finalmente, tal e como prometín, desvelo a fonte da que obtiven esta bonita cuestión. Trátase do libro de Hans Walser, The Golden Section (MAA 2001). De paso, aproveito a ocasión para recoller deste mesmo libro outro problema:

Cadrado inscrito nunha semicircunferencia. Tal e como se observa na figura, inscribimos un cadrado nunha semiciecunferencia. Pídese a razón AC/AB.