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.