Bézout y las arenas del tiempo

Un problema clásico entre los entusiastas de los rompecabezas es el siguiente:

---

Dados dos relojes de arena, uno de \(7\) minutos y otro de \(4\) minutos, ¿podemos medir exactamente \(9\) minutos?

---

Cualquiera que se ponga a ello puede juguetear un poco y encontrar una solución, pero cuando un amigo me habló de este problema en relación con una de sus alumnas (hola Álex :) la chispa de las matemáticas me sacudió y numerosas preguntas aparecieron en mi cabeza: ¿Qué tiempos es posible medir con estos dos relojes? ¿Y con dos relojes de arena cualesquiera? ¿Hay algún algoritmo, un proceso claro, que muestre cómo medir cualquier tiempo con dos relojes? Esto es muy común entre los matemáticos, escuchamos un problema interesante, lo resolvemos y, en lugar de dar el asunto por zanjado como haría cualquier persona normal, nos enfrascamos aún más en él tratando de resolver todo tipo de preguntas que se nos ocurren sobre el mismo. Somos así y tenéis que querernos como tal (hola Marina :).

Estoy convencido de que alguien con cierto bagaje matemático podría encontrar rápidamente la respuesta a estas preguntas utilizando ciertos «teoremas clave», pero creo que lo bonito del problema es que te puede llevar a descubrir esos resultados por ti mismo solamente con saber aritmética básica, la del cole vamos. Ese es el camino que recorreremos en esta entrada, mientras explicamos de paso cómo suele trabajar un matemático al resolver un problema. Citando al gran Mathologer, abrochaos vuestros cinturones matemáticos y acompañadme en esta aventura. Recorramos juntos el «camino del matemático».

1. De tiempo y arena

A modo de calentamiento, comencemos estudiando el problema de medir \(9\) minutos con los relojes de \(7\) y \(4\) minutos. Podríamos dar directamente una solución válida y, de hecho, os propongo que busquéis vuestra propia solución antes de continuar leyendo y la pongáis en los comentarios, pero como nuestro fin es analizar qué tiempos podemos medir con los dos relojes, vamos a explorar el problema con algo más de detalle.

Como tenemos un reloj de \(7\) minutos, al que llamaremos «el grande», y otro de \(4\) minutos, al que llamaremos «el pequeño», está claro que podemos medir estos dos tiempos de forma exacta, pero no son los únicos que podemos medir de forma directa. Observemos que si giramos el reloj grande y, cuando acabe, giramos el reloj pequeño, entonces habremos medido \(11\) minutos, la suma de los \(7\) del grande y los \(4\) del pequeño. Y nada nos impide seguir haciendo esto, si ahora giramos otra vez el pequeño mediremos \(7+4+4 = 15\) minutos, mientras que si giramos el grande mediremos \(7+4+7 = 18\) minutos.

Como hemos dicho, nada nos impide ir repitiendo este proceso indefinidamente: giramos uno de los relojes y, en cuanto acabe, volvemos a girarlo o giramos el otro. Los tiempos que podemos medir siguiendo este proceso serán de la forma \(7+4+4+7\), \(7+7+7\) o \(4+7+4+4\), entre muchos otros. Si agrupamos estas sumas utilizando las conocidas propiedades asociativa y conmutativa que todos aprendemos en el cole, podemos expresarlas como \((7+7) + (4+4)\), \(7+7+7\) o \(7 + (4+4+4)\) y, si recordamos que multiplicar significa repetir una suma muchas veces, podemos simplificar aún más lo anterior y asegurar que con nuestros dos relojes podemos medir tiempos de la forma \(2 \cdot 7 + 2 \cdot 4\), \(3 \cdot 7 + 0 \cdot 4\) o \(1 \cdot 7 + 3 \cdot 4\).

En general, hemos descubierto que siempre podemos medir tiempos de la forma

\(T_1 : = a \cdot 7 + b \cdot 4 \quad (1)\)

para cualesquiera números enteros \(a, b \geq 0\).

Si estos fueran los únicos tiempos que podemos medir con nuestros relojes estaríamos jodidos, porque fijaos que si \(a \geq 2\), entonces \(T_1 \geq 14\) y si \(b \geq 3\), entonces \(T_1 \geq 12\), mientras que si \(0 \leq a \leq 1\) y \(0 \leq b \leq 2\), las únicas posibilidades para \(T_1\) son \(0, 4, 7, 8, 11\) y \(15\). Es decir, con este proceso nunca podremos medir \(9\) minutos, pero no perdáis la esperanza, porque en el cole no solo nos enseñaron a sumar y multiplicar, también nos enseñaron a restar. Fijaos en lo siguiente, si giramos los dos relojes al mismo tiempo, cuando el pequeño se vacíe aún faltarán \(3\) minutos para que el grande termine, la resta o diferencia entre los tiempos de ambos, por lo que también podemos medir \(3\) minutos de forma exacta, un tiempo que, cómo acabamos de ver, no es posible medir con el proceso anterior.

Hemos ganado algo, pero todavía podemos ganar mucho más si seguimos explorando esta vía. Imaginad que ahora hacemos lo siguiente:

1. Giramos ambos relojes al mismo tiempo.
2. En cuanto alguno de ellos acabe, ya sea el grande o el pequeño, volvemos a girarlo.
3. Repetimos este proceso hasta haber girado el grande 2 veces y el pequeño 3 (teniendo en cuenta el primer giro al comienzo).
4. En cuanto el pequeño acabe, después del tercer giro, empezamos a contar el tiempo hasta que acabe el grande tras su segundo giro.

¿Cuánto tiempo hemos medido con este proceso?

Si nos fijamos, en total, desde que hemos girado ambos relojes por primera vez hasta que ha acabado el grande tras su segundo giro habremos medido \(2 \cdot 7 = 14\) minutos, pero si comenzamos a medir el tiempo justo cuando ha acabado el pequeño tras girarlo tres veces, es decir, cuando han pasado ya \(3 \cdot 4 = 12\) minutos, entonces habremos medido \(14 – 12 = 2\) minutos. ¡Hemos encontrado otro tiempo nuevo que también podemos medir!

Aún más, en lugar de girar \(2\) veces el grande y \(3\) el pequeño, podríamos haber girado, por ejemplo, \(3\) veces el grande y \(4\) veces el pequeño en el proceso anterior y habríamos medido \(3 \cdot 7 = 21\) minutos en total y \(3 \cdot 7 – 4 \cdot 4 = 5\) minutos si comenzamos a contar el tiempo desde que acaba el reloj pequeño tras su cuarto giro.

Siguiendo este nuevo proceso, lo que ahora hemos descubierto es que también podemos medir cualquier tiempo de la forma

\(T_2 : = a \cdot 7 – b \cdot 4 \quad (2)\)

con \(a, b > 0\) siempre que \(T_2\) sea mayor que cero (equivalentemente, siempre que \(a \cdot 7 > b \cdot 4\))¹, porque, por desgracia, aún no sabemos como viajar atrás en el tiempo.

Sin nada de esfuerzo extra, un proceso completamente análogo al anterior también nos proporciona un método para medir cualquier tiempo de la forma

\(T_3 : = a \cdot 4 – b \cdot 7 \quad (3)\)

con \(a, b > 0\) siempre que \(T_3\) sea mayor que cero².

¿Nos permite esto resolver el problema original? Pues la verdad es que sí, porque podemos expresar

\(9 = 3 \cdot 7 – 3 \cdot 4,\)

es decir, \(9\) es un tiempo de la forma \(T_2\) y siguiendo el segundo proceso que hemos descrito podremos medirlo.

Antes de seguir avanzando, creo que es importante recalcar el camino que hemos seguido, porque es, en cierto modo, «el camino del matemático»:

1. Ante un problema nuevo hemos comenzado explorando y buscando patrones sencillos. En nuestro caso, rápidamente hemos visto un método para medir cualquier tiempo de la forma \(T_1\). Como queremos saber si podemos medir \(9\) minutos con nuestros relojes, este descubrimiento transforma nuestro problema original en saber si \(9\) se puede expresar de dicha forma.
2. Como \(9\) no es un tiempo de la forma \(T_1\) continuamos con la exploración y encontramos un nuevo método sencillo con el que medir cualquier tiempo de la forma \(T_2\) o \(T_3\). Esto transforma de nuevo nuestro problema en saber si \(9\) se puede expresar de alguna de estas formas.
3. Como en este caso sí que se cumple que \(9\) es un tiempo de la forma \(T_2\), hemos resuelto el problema.

He destacado la palabra «transforma», porque es muy común en matemáticas que al intentar resolver un problema difícil lo vayamos transformando en otros problemas sobre los que tengamos más información hasta dar con su solución. En este caso, hemos pasado de un problema sobre medir ciertos tiempos con relojes de arena a un problema sobre si \(9\) se puede expresar como cierta combinación de sumas, restas y productos de otros números.

2. Buscando generalidad

En este punto alguien podría pensar que hemos complicado mucho las cosas, que su solución al problema es mucho más directa. Si ese alguien eres tú, te digo, camarada, que es posible que tengas razón, que el problema original puede resolverse sin «tanto rollo», pero recuerda que nuestro fin es dar respuesta a preguntas mucho más grandes: buscamos conocer TODOS los tiempos que estos dos relojes (o, más en general, dos relojes cualesquiera) nos permiten medir.

Ante este problema mucho más general, hemos dado pasos de gigante. En efecto, conocemos ya tres procesos distintos que nos permiten medir tiempos de la forma \(T_1\), \(T_2\) o \(T_3\). Además, sabemos que los tiempos de la forma \(T_1\) tienen sus limitaciones, pero aún no hemos encontrado limitaciones para los de la forma \(T_2\) o \(T_3\), es decir, aún no hemos encontrado ningún número natural que no sea de esta forma. ¿Existirá alguno? Explorémoslo juntos para los tiempos de la forma \(T_2\) (os dejo como deberes los de la forma \(T_3\)).

En primer lugar, si sabemos que cierto número natural es de la forma \(T_2\), por ejemplo, sabemos que

\(9 = 3 \cdot 7 – 3 \cdot 4, \quad (4)\)

¿hay alguna familia de números relacionados con el \(9\) que también sean de la forma \(T_2\)? Os doy una pista: repasad el concepto de múltiplo de un número que aprendisteis en el cole.

Sin más preámbulos, fijaos que si multiplicamos el \(9\) por cualquier número positivo \(m\), entonces por (4) tenemos que

\(m \cdot 9 = m \cdot (3 \cdot 7 – 3 \cdot 4),\)

y si recordamos otra importante propiedad con la que a todos nos han machacado, la propiedad distributiva, podemos simplificar esta expresión como

\(m \cdot 9 = m \cdot (3 \cdot 7 – 3 \cdot 4) = (m \cdot 3) \cdot 7 – (m \cdot 3) \cdot 4 \quad (5)\)

y queda claro que \(m \cdot 9\) también es de la forma \(T_2\).

Es decir, hemos visto que cualquier múltiplo positivo de \(9\) es también de la forma \(T_2\), pero el \(9\) no tiene nada especial, si lo cambiamos por cualquier número \(n\) que sea de la forma \(T_2\), siguiendo el mismo razonamiento podemos ver que todos sus múltiplos positivos son también de la forma \(T_2\). Como esto parece importante, vamos a ponerle nombre:

Lema 2.1: Si \(n\) es un número de la forma \(T_2\), entonces cualquiera de sus múltiplos positivos, es decir, cualquier número de la forma \(m \cdot n\) con \(m > 0\), será también de la forma \(T_2\).

Este descubrimiento nos permite decir, por ejemplo, que con nuestros dos relojes de arena podremos medir cualquier tiempo par, porque en nuestra exploración de la sección anterior ya vimos que el \(2\) es de la forma \(T_2\). Además, nos permite transformar de nuevo nuestro problema de si todo número es de la forma \(T_2\) a preguntarnos: ¿hay algún número de la forma \(T_2\) cuyos múltiplos sean todos los números naturales?

Esta pregunta tiene dos partes. Por un lado nos preguntamos si, en general, hay algún número cuyos múltiplos sean todos los números naturales, y por otra si dicho número es de la forma \(T_2\).

La respuesta a la primera pregunta es fácil si utilizamos otro concepto clave que estoy seguro que todos recordaréis: el \(1\) es el elemento neutro para el producto. ¿Que no os suena esto del «elemento neutro»? ¿Y eso de que al multiplicar cualquier número \(n\) por \(1\) siempre obtenemos de nuevo \(n\)? Ahora sí, ¿no? En matemáticas, cuando tenemos algún número u objeto que al operarlo con cualquier otro lo deja igual lo llamamos elemento neutro (porque no hace nada vamos). Por ejemplo, el \(0\) es el elemento neutro para la suma. Muy bien, ya sabemos una palabra complicada para representar algo muy sencillo, ¿pero cómo nos ayuda esto en nuestra búsqueda? Pues muy fácil, si al multiplicar cualquier número por \(1\) obtenemos el mismo número, esto nos esta diciendo que los múltiplos de \(1\) son TODOS los números, que es justo lo que buscábamos. Por tanto, si \(1\) es de la forma \(T_2\), gracias al Lema 2.1 demostraríamos de un plumazo que con nuestros dos relojes podemos medir cualquier tiempo. Redoble de tambores…

\(1 = 3 \cdot 7 – 5 \cdot 4.\)

¡Ya está! Ahora sabemos que con nuestros dos relojes podemos medir cualquier tiempo que nos dé la gana, pero… ¿Y si nos dan otros relojes distintos?

3. Buscando aún más generalidad

Ya sabemos que con dos relojes de arena, uno de \(7\) y otro de \(4\) minutos, podemos medir cualquier tiempo, pero llegados a este punto no vamos a rendirnos, vamos a estudiar TODOS los relojes, vamos a domar a las arenas del tiempo.

Hasta ahora estábamos tratando un caso particular del problema de los relojes de arena, pero ya estamos listos para abstraerlo, es decir, en lugar de explorar con relojes concretos, podemos considerar dos relojes de arena de tiempos \(x\) e \(y\) (las temidas \(x\) e \(y\) de las matemáticas), de modo que \(x > y > 0\). Este es otro paso en el «camino del matemático», la abstracción.

Si repetimos todo lo que hemos hecho, pero cambiamos cada aparición del «\(7\)» por una «\(x\)» y cada aparición del «\(4\)» por una «\(y\)», obtenemos que podemos medir cualquier tiempo de la forma

\(T_1^{x, y} : = a \cdot x + b \cdot y\)

con \(a, b \geq 0\) ambos no nulos³, cualquiera de la forma

\(T_2^{x,y} : = a \cdot x – b \cdot y\)

con \(a, b > 0\) cumpliendo que \(T_2^{x,y}\) sea positivo y cualquiera de la forma

\(T_3^{x,y} : = a \cdot y – b \cdot x\)

con \(a, b > 0\) cumpliendo que \(T_3^{x,y}\) sea positivo. Además, también tenemos un método preciso, un algoritmo, que nos permite medir estos tiempos. Que recalquemos esto puede parecerle una tontería a alguno de vosotros, pero en matemáticas no lo es, porque muchas veces conocemos la existencia de ciertos objetos matemáticos, pero no somos capaces de dar un ejemplo explícito de ninguno. Así de fascinantes u odiosas, depende de cómo se mire, son las matemáticas.

Volviendo a nuestro problema, podemos simplificar un poco las cosas si observamos que podemos combinar los tiempos de la forma \(T_1^{x, y}, T_2^{x, y}\) y \(T_3^{x, y}\) en una única expresión, pues son exactamente⁴ los tiempos de la forma

\(T^{x,y} : = a \cdot x + b \cdot y \quad (6)\)

con \(a\) y \(b\) números enteros cualesquiera (positivos, nulos o negativos), pero de modo que \(T^{x,y}\) sea positivo.

En resumen, sabemos que podemos medir cualquier tiempo de la forma \(T^{x,y}\) y tenemos un algoritmo para hacerlo. Más aún, siguiendo un razonamiento análogo al que nos ha permitido probar el Lema 2.1 podemos demostrar el siguiente lema general que nos garantiza que con encontrar unos pocos números de la forma \(T^{x,y}\) podemos encontrar infinitos más:

Lema 3.1: Si \(n\) es un número de la forma \(T^{x,y}\), entonces cualquiera de sus múltiplos positivos, es decir, cualquier número de la forma \(m \cdot n\) con \(m > 0\), será también de la forma \(T^{x,y}\). Además, si \(p\) es otro número de esta forma, entonces \(n + p\) también lo es y, si \(p > n\), \(p – n\) también.

Finalmente, si terminamos de recorrer el mismo camino que hicimos para los relojes de \(7\) y \(4\) minutos, podemos utilizar este Lema 3.1 para asegurar que si \(1\) es de la forma \(T_{x,y}\), entonces podremos medir cualquier tiempo con nuestros relojes de \(x\) e \(y\) minutos.

Todo lo que hemos visto nos sugiere que estudiar los números de la forma \(T_{x,y}\) es importante para resolver nuestro problema, por lo que vamos a ello.

4. Bézout y el temido máximo común divisor

Parece que nuevamente hemos transformado nuestro problema sobre relojes de arena en uno sobre cierto tipo de números. Concretamente, fijados dos números naturales \(x > y >0\) queremos estudiar los números de la forma \(T^{x,y}\). Para hacer este estudio más fácil, al menos más ordenado, podemos utilizar otra de las herramientas del matemático: ponerle nombre a las cosas. Puede parecer una tontería, pero ayuda mucho a la hora de ordenar las ideas. En nuestro caso, vamos a denotar por \(C^{x,y}\) al conjunto de todos los números de la forma \(T^{x,y}\) y buscaremos «quitarle la máscara» a este conjunto para descubrir que, como siempre ocurría en Scooby-Doo, es un viejo conocido.

Un buen punto de partida es buscar algún elemento importante dentro de \(C^{x,y}\). Nos podemos fijar en que tanto \(x\) como \(y\) están en \(C^{x,y}\) (¿por qué?) y, además, son muy importantes porque en cierto modo son los «padres» de todos los demás números en \(C^{x,y}\). Sin embargo, ya los tenemos muy vistos, queremos encontrar otro número nuevo y especial. Para ello, lo que podemos hacer entonces es observar que, como \(C^{x,y}\) es un conjunto no vacío de enteros positivos, tiene que tener un elemento mínimo⁵ al que podemos llamar \(n_0\). Este número ya parece algo más interesante, es el menor de todos los que están en \(C^{x,y}\), es decir, el menor número de la forma \(T^{x,y}\) y eso ya tiene su mérito. Además, como está en \(C^{x,y}\) sabemos que es positivo y que existen ciertos enteros \(a_0, b_0\) tales que

\(n_0 = a_0 \cdot x + b_0 \cdot y. \quad (7)\)

Ahora que ya tenemos un elemento nuevo y especial, lo que nos gustaría es compararlo de alguna forma con sus «padres» \(x\) e \(y\), y para ello podemos utilizar otra herramienta con la que nos machacaron hasta la saciedad en el cole, el algoritmo de la división. ¿No lo recordáis? Y si os digo que es aquel de la frase «dividendo es igual al divisor por cociente más el resto», ¿suenan ahora campanas? Si lo traducimos a un lenguaje algo más formal y, en este caso, más explicativo, lo que tenemos es el siguiente teorema:

Teorema 4.1 (Algoritmo de la división): Dados dos números enteros \(D\) (dividendo) y \(d\) (divisor) con \(d \not = 0\), existen dos únicos números enteros \(q\) (cociente) y \(r\) (resto) que cumplen:

1. \(D = d \cdot q + r\).
2. \(0 \leq r < d\).

En esencia, lo que nos dice el algoritmo de la división es que siempre podemos repartir (de forma única) cualquier cantidad \(D\) de objetos entre \(d\) personas de modo que, como mucho, nos sobre menos de \(d\) objetos, los cuales ya no podemos repartir de forma justa entre este grupo de personas (alguna se quedaría con una menor cantidad del preciado objeto).

Si aún no ha quedado claro, podemos pensarlo con manzanas, que siempre nos hace la vida más fácil. Si tenemos \(D=13\) manzanas y queremos repartirlas entre \(d = 4\) caballos, podemos ir repartiendo una a cada caballo hasta que nos quedemos sin manzanas. Tras hacer esto tres veces habremos repartido \(4 \cdot 3 = 12\) manzanas, pero aún nos sobrará \(1\) de ellas que ya no podremos repartir de forma igualitaria entre los caballos (nunca nos pueden sobrar \(4\) o más manzanas, porque entonces podríamos haber hecho al menos un grupo más de \(4\) manzanas para repartir entre los caballos). Por tanto, vemos que podemos repartir \(q = 3\) manzanas a cada uno de los \(4\) caballos y nos sobrará \(r = 1\) manzana, es decir, podemos expresar \(13 = 4 \cdot 3 + 1\) tal y como nos dice el algoritmo de la división.

Volviendo al asunto de los relojes y al conjunto \(C^{x,y}\), el algoritmo de la división nos dice que podemos dividir \(x\) entre \(n_0\), es decir, que existen ciertos enteros \(q, r\) tales que \(0 \leq r < n_0\) y

\(x = n_0 \cdot q + r. \quad (8)\)

Alguien puede decir ahora: «¿muy bien y qué?». Pues «mucho qué» en realidad, porque recordad que por (7) podemos expresar

\(x = (a_0 \cdot x + b_0 \cdot y) \cdot q + r = (a_0 \cdot q) \cdot x + (b_0 \cdot q) \cdot y + r,\)

y esto nos muestra que, gracias a la genial propiedad distributiva,

\(r = x – (a_0 \cdot q) \cdot x – (b_0 \cdot q) \cdot y = (1 – a_0 \cdot q) \cdot x + (- b_0 \cdot q) \cdot y, \quad (9)\)

con lo que \(r\) es de la forma \(T^{x,y}\), es decir, está en… ¡está en \(C^{x,y}\)! Pero, \(r < n_0\) y \(n_0\) era especial entre los elementos de \(C^{x,y}\), era el menor número posible dentro de \(C^{x,y}\), ¿qué está pasando aquí? ¿Cómo podemos haber encontrado un número dentro de \(C^{x,y}\) más pequeño que \(n_0\)? Pues la respuesta es que no hemos encontrado tal número, pero hemos descubierto algo mucho mejor. Recordad que para que \(r\) estuviera en \(C^{x,y}\) tienen que cumplirse dos cosas: que sea de la forma (6) y que sea positivo. Como sabemos que no puede estar en \(C^{x,y}\), porque es más pequeño que \(n_0\), pero por (9) si que es de la forma (6), la única opción que nos queda es que no es positivo y, como \(r \geq 0\), concluimos que \(r = 0\). Por tanto, si volvemos a mirar (8) nos damos cuenta de que realmente tenemos que \(x = n_0 \cdot q\), es decir, que \(n_0\) divide a \(x\) de forma exacta, \(n_0\) es un divisor de \(x\).

Si ahora repetimos todo este tinglado cambiando «\(x\)» por «\(y\)» podéis comprobar que llegamos al mismo resultado: \(n_0\) también es un divisor de \(y\). Es decir, hemos descubierto que \(n_0\) es un divisor común de \(x\) e \(y\), y yo os pregunto: ¿cuál es el divisor común más famoso de la historia de las matemáticas? Si en tu cabeza ha sonado la frase «el máximo común divisor» puedes anotarte un bingo. Vamos a ver que \(n_0\) no es solamente un divisor común cualquiera de \(x\) e \(y\), es el máximo común divisor de \(x\) e \(y\). ¿Qué debemos hacer para demostrar esto? Pues, como ya sabemos que \(n_0\) es un divisor tanto de \(x\) como de \(y\), solo nos queda ver que es el más grande posible. Dicho de otro modo, tenemos que ver que si \(c\) es otro divisor común de \(x\) e \(y\), entonces \(c\) es más pequeño que \(n_0\).

Si \(c < 0\) es claro que \(c \leq n_0\), con lo que supongamos que \(c\) es positivo. Como \(c\) es un divisor de \(x\), es decir, divide a \(x\) de forma exacta, sabemos que existe algún entero \(a\) tal que \(x = c \cdot a\). De igual modo, como \(c\) es un divisor de \(y\) existe algún entero \(b\) tal que \(y = c \cdot b\). Si tenemos ahora en cuenta que \(n_0\) está en \(C^{x,y}\), es decir, si tenemos en cuenta (7), entonces obtenemos (otra vez por la propiedad distributiva) que

\(n_0 = a_0 \cdot x + b_0 \cdot y = a_0 \cdot (c \cdot a) + b_0 \cdot (c \cdot b) = c \cdot (a_0 \cdot a) + c \cdot (b_0 \cdot b) = c \cdot (a_0 \cdot a + b_0 \cdot b).\)

Por tanto, \(c\) divide a \(n_0\) de forma exacta y tiene que ocurrir⁶ que \(c \leq n_0\) tal y como buscábamos.

Ha sido un camino largo y es posible que alguien se haya mareado, perdido o echado una siesta, pero hemos descubierto algo muy fuerte: el máximo común divisor entre \(x\) e \(y\) está en \(C^{x,y}\), es decir, es de la forma \(T^{x,y}\). De hecho, este descubrimiento es tan importante que no somos los primeros en hacerlo y tiene hasta nombre propio:

Teorema 4.2 (Lema de Bézout): Dados dos enteros \(x\) e \(y\), existen otros enteros \(a, b\) tales que

\(\mathrm{mcd}(x,y) = a \cdot x + b \cdot y.\)

Dicho de otro modo, el máximo común divisor de dos enteros \(x\) e \(y\) siempre es de la forma \(T^{x,y}\).

¿Y qué habíamos concluido al final de la Sección 3? Que si el \(1\) es de la forma \(T^{x,y}\), entonces podemos medir cualquier tiempo que queramos con nuestros relojes de arena. Juntando esto con nuestro nuevo descubrimiento obtenemos el siguiente resultado:

Teorema 4.3: Si tenemos dos relojes de arena con tiempos \(x > y >0\), entonces podemos medir cualquier tiempo que sea múltiplo de su máximo común divisor. En particular, si \(\mathrm{mcd}(x,y) = 1\) podemos medir cualquier tiempo que queramos con dichos relojes.

Recapitulemos porqué esto es cierto para que nadie se pierda.

• En las tres primeras secciones hemos visto que con dos relojes de arena de tiempos \(x > y >0\) podemos medir cualquier tiempo de la forma \(T^{x,y}\).
• Además, el Lema 3.1 nos asegura que si un número positivo \(n\) es de la forma \(T^{x,y}\), entonces todos sus múltiplos positivos también lo son. Por tanto, si \(1\) es de la forma \(T^{x,y}\), entonces todos los enteros positivos son de esta forma y, por el punto anterior, sabemos que podemos medir cualquier tiempo con nuestros relojes.
• Por el lema de Bézout (Teorema 4.2) sabemos que el máximo común divisor entre \(x\) e \(y\) es de la forma \(T^{x,y}\), luego el punto anterior nos asegura que siempre podremos medir cualquier tiempo que sea un múltiplo positivo de \(\text{mcd}(x,y)\). En particular, si \(\text{mcd}(x,y) = 1\) podemos medir cualquier tiempo que nos dé la gana con nuestros relojes.

Los pares de números que cumplen que su máximo común divisor es \(1\) se llaman coprimos, luego el importante corolario con el que podemos cerrar la sección es que si los tiempos de dos relojes de arena son coprimos, entonces podemos medir cualquier tiempo que queramos con ellos. Además, siempre expresemos el \(1\) de la forma \(T^{x,y}\) tenemos incluso un algoritmo concreto para realizar la medida. Por no alargar más esta entrada no entraremos en detalles, pero el lector interesado puede consultar este enlace donde se explica un algoritmo que permite encontrar enteros \(a\) y \(b\) para los cuales se cumple que \(\text{mcd}(x,y) = a \cdot x + b \cdot y\).

5. Suficiente y necesario

Hemos hecho grandes avances con el problema de los relojes, pero aún nos quedan preguntas por responder. ¿Qué pasa si los tiempos de los relojes no son coprimos? ¿Podemos medir cualquier tiempo en ese caso o habrán tiempos que nunca podamos medir?

El Teorema 4.3 nos da lo que se conoce como una condición suficiente para nuestro problema: es SUFICIENTE con que un tiempo sea múltiplo del \(\text{mcd}(x,y)\) para saber que podemos medirlo. Pero, en principio, no nos asegura que también sea una condición necesaria, es decir, no sabemos si es NECESARIO que un tiempo sea múltiplo del \(\text{mcd}(x,y)\) para que podamos medirlo. Dicho de otro modo, sabemos que podemos medir cualquier tiempo que sea múltiplo del \(\text{mcd}(x,y)\), ¿pero habrá algún otro tiempo que no cumpla esto que podamos medir? Vamos a explorar esta idea que culmina el «camino del matemático»: hemos encontrado una condición suficiente para nuestro problema y ahora nos preguntamos si también es necesaria.

Para seguir este camino es obvio que tenemos que analizar con mucho más cuidado cómo podemos medir el tiempo con nuestros relojes de arena, y para ello tendremos que definir de forma precisa que entendemos por «medir» con los relojes de arena. Este es un punto que a veces se olvida al hacer matemáticas, pero que es realmente importante: para demostrar cualquier cosa sobre un proceso concreto primero tenemos que definirlo sin ambigüedades.

Observemos que cualquier proceso de medición que hagamos con nuestros dos relojes está completamente caracterizado por los giros que se hagan de los relojes, los momentos de tiempo exactos cuando se hacen, por un momento inicial desde el que empezar a medir el tiempo y por un momento final donde parar de medir el tiempo (que claramente debe ocurrir después del momento inicial).

Es obvio que ninguna medición precisa puede comenzar antes de haber girado por primera vez alguno de los dos relojes, por lo que llamaremos momento cero de la medición a este punto en el que ocurre el primer giro en la medición. Además, como no disponemos de ninguna herramienta externa a los relojes de arena, los únicos puntos de referencia temporales que tenemos son los momentos en los que alguno de los dos relojes se vacía, por tanto, si buscamos hacer medidas de tiempo exactas, únicamente tiene sentido realizar los giros en el momento cero o en estos momentos cuando se vacía algún reloj (teniendo en cuenta que podemos girar el mismo reloj que ha acabado, el otro o ambos). Por la misma razón, el momento inicial debe establecerse, o bien en el momento cero, o bien cuando algún reloj se vacíe, mientras que el momento final deberá establecerse cuando algún reloj se vacíe.

Con toda esta información podemos dar ya la definición buscada de qué es una medición y cuáles son las que realmente nos interesan:

Definición 5.1: Una medición \(M\) con dos relojes de arena de tiempos \(x > y > 0\) es cualquier proceso que comienza con los dos relojes sin arena en su parte superior y describe sin ambigüedad en qué momentos se deben girar los relojes de arena, un momento inicial desde el que comenzar a medir el tiempo y un momento final donde parar de medir. Además, diremos que la medición \(M\) es exacta cuando cumpla lo siguiente:

• La medición comienza con su momento cero.
• Sus giros solamente ocurren en el momento cero de la medición o cuando algún reloj se vacía debido a algún giro previo realizado durante la medición.
• Su momento inicial se establece en el momento cero de la medición o cuando algún reloj se vacía debido a algún giro realizado durante la medición.
• Su momento final se establece cuando algún reloj se vacía debido a algún giro realizado durante la medición.

Además, diremos que un tiempo \(T\) es medible si existe una medición exacta con los dos relojes de modo que \(T\) sea la diferencia entre su momento final y su momento inicial.

Observemos que, como decíamos antes, las únicas mediciones con relojes de arena que realmente pueden darnos medidas precisas serán las exactas. Todas las mediciones que hemos descrito a lo largo de esta entrada son exactas y, por tanto, los tiempos que ya hemos visto que podíamos medir de manera precisa son medibles de acuerdo a la definición anterior. Por aclarar completamente las ideas en las siguientes imágenes pueden verse un par de ejemplos de mediciones no exactas, las cuales para llevarse a cabo precisan de una forma externa de medir el tiempo.

Con esta nueva y más precisa notación podemos resumir todos los resultados de las secciones anteriores en el siguiente teorema:

Teorema 5.2: Dados dos relojes de arena con tiempos \(x > y >0\), cualquier tiempo de la forma \(T^{x,y}\) es medible. En particular, el \(\mathrm{mcd}(x,y)\) y cualquiera de sus múltiplos es medible.

Voy a presentaros ahora la última y tal vez más poderosa herramienta del matemático: la conjetura. Sabemos que podemos medir cualquier tiempo de la forma \(T^{x,y}\) y el Lema 3.1 nos dice que con encontrar unos pocos tiempos de esta forma podemos obtener una infinidad más. Esto nos puede hacer pensar que, tal vez, no haya ningún tiempo medible distinto a estos, es decir, nos hace conjeturar que los únicos tiempos medibles serán los de la forma \(T^{x,y}\). Una vez hecha una conjetura el matemático debe intentar demostrarla o seguir peleando con ella hasta encontrar un contraejemplo (un ejemplo que demuestre que es falsa). En nuestro caso la conjetura resulta ser verdadera y nos muestra que la condición dada en el Teorema 5.2 no es solo suficiente, sino también necesaria:

Teorema 5.3: Dados dos relojes de arena con tiempos \(x > y >0\), un tiempo \(T\) es medible si, y solo si, es de la forma \(T^{x,y}\).

La demostración es bastante más técnica que el resto de la entrada, pero el lector interesado puede consultarla aquí.

OK, tenemos una caracterización de los tiempos medibles por dos relojes de arena, pero no deja de ser algo insatisfactoria porque seguimos sin tener una buena descripción de qué números son de la forma \(T^{x,y}\). Ya vimos en el Teorema 4.2 que el máximo común divisor entre \(x\) e \(y\) es de esta forma, y por el Lema 3.1 también sabemos que cualquiera de sus múltiplos lo será. Sin embargo, como ya hemos dicho anteriormente, no sabemos si habrá otros números distintos a estos que también sean de la forma \(T^{x,y}\). Por tanto, nos queda dar el último paso en nuestro camino, debemos continuar el estudio que ya iniciamos en la Sección 4 sobre estos números para obtener una solución realmente satisfactoria a nuestro problema.

Dado que los únicos números que conocemos que son de la forma \(T^{x,y}\) son los múltiplos del \(\mathrm{mcd}(x,y)\), tiene perfecto sentido tratar de estudiar si son los únicos de esta forma, es decir, vamos a intentar demostrar que si un número es de la forma \(T^{x,y}\), entonces es un múltiplo del máximo común divisor de \(x\) e \(y\) (volvemos a utilizar la conjetura como guía). Dicho de otro modo, veamos si el \(\mathrm{mcd}(x,y)\) divide a cualquier número de la forma \(T^{x,y}\).

Si \(n\) es de la forma \(T^{x,y}\), entonces podemos expresarlo como \(n = a \cdot x + b \cdot y\) para ciertos enteros \(a\) y \(b\). Por otra parte, como el \(\mathrm{mcd}(x,y)\) divide tanto a \(x\) como a \(y\), también existen ciertos enteros \(c\) y \(d\) tales que \(x = c \cdot \mathrm{mcd}(x,y)\) e \(y = d \cdot \mathrm{mcd}(x,y)\). Juntando ambas expresiones obtenemos que

\(n = a \cdot x + b \cdot y = a \cdot (c \cdot \mathrm{mcd}(x,y)) + b \cdot (d \cdot \mathrm{mcd}(x,y)) = (a \cdot c + b \cdot d) \cdot \mathrm{mcd}(x,y),\)

con lo que, efectivamente, el \(\mathrm{mcd}(x,y)\) divide a \(n\).

En resumen, juntando lo que descubrimos en la Sección 4 con lo que acabamos de ver hemos demostrado el siguiente resultado:

Teorema 5.4 (Lema de Bézout completo): Sean \(x\) e \(y\) dos números enteros. El conjunto \(C^{x,y}\) de todos los números de la forma \(T^{x,y}\) es, exactamente, el conjunto de todos los múltiplos positivos del \(\mathrm{mcd}(x, y)\). En particular, el \(\mathrm{mcd}(x, y)\) es el menor número de la forma \(T^{x,y}\).

Y ahora sí, POR FIN, si juntamos los Teoremas 5.3 y 5.4 tenemos una solución completa a nuestro problema:

Teorema 5.5: Dados dos relojes de arena con tiempos \(x > y >0\), un tiempo \(T\) es medible si, y solo si, es un múltiplo del \(\mathrm{mcd}(x,y)\).

Así que ya sabéis, si alguien os da dos relojes de arena de \(11\) y \(4\) minutos podéis medir cualquier tiempo que os dé la gana, pero si os dan otros de \(6\) y \(3\) minutos con la intención de que midáis \(4\) minutos os estarán tomando el pelo. Este es el poder de las matemáticas, ningún estafador de relojes de arena podrá engañaros nunca más.

Con esto finalizamos nuestro camino, pero espero que hayáis disfrutado el viaje y os haya ayudado a entender mejor cómo trabaja un matemático y cómo nuestras herramientas pueden ser útiles para resolver cualquier tipo de problema, matemático o no. Aún así, si alguien se ha quedado con ganas de más, os dejo un problema para el cual no tengo respuesta.

Fijaos que, aunque hemos caracterizado los tiempos medibles y obtenido algoritmos prácticos para medirlos, no sabemos si son óptimos. Por ejemplo, con los relojes de \(7\) y \(4\) minutos sabemos que podemos expresar \(1 = 3 \cdot 7 – 5 \cdot 4\) y que, por tanto, cualquier número natural \(n\) se expresa como \(n = (3 \cdot n) \cdot 7 – (5 \cdot n) \cdot 4\). Al ser un número de la forma \(T_2^{x,y}\) tenemos un algoritmo que transforma la expresion anterior de \(n\) en una forma de medir \(n\) minutos exactamente, pero el tiempo total que tardará dicho algoritmo en ejecutarse es \((3 \cdot n) \cdot 7\) minutos. Es decir, para medir con este algoritmo, por ejemplo, \(3\) minutos, tardaremos una hora y \(3\) minutos. Sin embargo, en la Sección 1 ya vimos como hacerlo tardando solo \(7\) minutos. El problema consiste, por tanto, en encontrar un algoritmo óptimo para medir los tiempos medibles. ¿Serán los algoritmos que hemos dado, pero aplicados sobre la expresión del tiempo de la forma \(T^{x,y}\) que minimice el tiempo total de ejecución? En dicho caso, ¿hay algún algoritmo eficiente para expresar cualquier tiempo medible de esta forma?

Ahora sí, nos leemos en la próxima entrada.

1. Observemos que no perdemos nada al imponer que \(a, b >0\) en lugar de \(a, b \geq 0\). En efecto, si \(a = 0\), entonces \(T_2 = – b \cdot 4 \leq 0\), mientras que si \(b=0\), entonces \(T_2 = a \cdot 7\) que es un tiempo de la forma \(T_1\) y ya sabemos cómo medirlo. ↩︎
2. Por la misma razón que para los tiempos \(T_2\) no perdemos nada al imponer que \(a,b > 0\), en lugar de \(a, b \geq 0\). ↩︎
3. En las secciones anteriores no impusimos esta condición, pero a partir de ahora consideraremos que, para los tiempos de la forma \(T_1^{x,y}\), \(a\) y \(b\) no son ambos nulos. Es decir, consideraremos que el \(0\) no es de la forma \(T_1^{x,y}\). Esto no nos supone ninguna pérdida porque todos sabemos medir \(0\) minutos, incluso sin relojes de arena. ↩︎
4. Es claro que cualquier número de la forma \(T_1^{x, y}, T_2^{x, y}\) o \(T_3^{x, y}\) es también de la forma \(T^{x,y}\). Recíprocamente, dado un número \(n\) de la forma \(T^{x,y}\), es decir, \(n > 0\) y de modo que existen enteros \(a,b\) tales que \(n = a \cdot x + b \cdot y\), tenemos varias opciones:
   ● \(a, b \geq 0\), con lo que \(n\) es de la forma \(T_1^{x,y}\) (ya que ambos no pueden ser nulos al ser \(n >0\)).
   ● \(a \geq 0\) y \(b < 0\), con lo que realmente podemos expresar \(n = a \cdot x – (-b) \cdot y\) siendo \(a, -b > 0\) (si \(a = 0\), entonces \(n = b \cdot y\), que es negativo en este caso) y, por tanto, es un número de la forma \(T_2^{x,y}\).
   ● \(a < 0\) y \(b \geq 0\), con lo que realmente podemos expresar \(n = b \cdot y – (-a) \cdot x\) siendo \(b, -a > 0\) (si \(b = 0\), entonces \(n = a \cdot x\), que es negativo en este caso) y, por tanto, es un número de la forma \(T_3^{x,y}\).
   ● No puede darse el caso en el que \(a, b <0\), porque entonces tendríamos que \(n = a \cdot x + b \cdot y < 0\), pero sabemos que es un número positivo.
   En cualquier caso, el \(n\) es de una de las tres formas deseadas y queda demostrado que los números de la forma \(T_1^{x,y}, T_2^{x,y}\) y \(T_3^{x,y}\) son exactamente los de la forma \(T^{x,y}\). ↩︎
5. Cualquier conjunto no vacío \(C\) de enteros positivos tiene un elemento mínimo, es decir, alguno que es más pequeño que todos los demás. Como \(C\) es no vacío, sabemos que hay al menos un natural \(m\) que está en \(C\). Si \(1\) está en el conjunto \(C\), claramente es el mínimo, y si no lo está, vamos comprobando de uno en uno si cada natural \(1 < n < m\) está en \(C\). Si alguno lo está, el primero que hayamos encontrado será el mínimo de \(C\) y, si ninguno de ellos está en \(C\), entonces \(m\) es el mínimo. ↩︎
6. Cualquier divisor \(m\) de un entero positivo \(n\) es menor o igual que \(n\). Esto es intuitivamente cierto, porque si \(m\) divide a \(n\), es decir, si podemos repartir \(n\) objetos entre \(m\) personas de forma exacta, no puede haber menos objetos que personas.
   Más formalmente, si \(m < 0\), entonces es claro que \(m < n\), con lo que supongamos que \(m\) es positivo. En este caso, como sabemos que existe un entero \(a\) tal que \(n = m \cdot a\), también tenemos que \(a > 0\) (si \(a<0\), entonces \(m \cdot a < 0\) y sería \(n < 0\)), o dicho de otro modo, \(a \geq 1\) y concluimos que \(m = m \cdot 1 \leq m \cdot a = n\). ↩︎