Voy a comenzar este artículo con una actividad para un rato de aburrimiento, que podemos proponer a un niño, o que podemos intentar nosotros mismos:

Imaginemos que, por razones que no tienen importancia, se comienzan a distribuir monedas de curso legal cuyo valor es 11 céntimos. La actividad es la siguiente:

Utilizando monedas de 5 céntimos y monedas de 11 céntimos, ¿es posible conseguir 14 céntimos? ¿Y 27 céntimos? ¿Y 39? ¿Y 53?

Bien, es muy fácil darse cuenta de que no podemos conseguir 14 céntimos con estás condiciones, de que 27 céntimos pueden conseguirse con una moneda de 5 y dos de 11 y de que 53 se consigue con cuatro monedas de 5 y tres de 11. ¿Y qué ocurre con 39? Pues que por muchas vueltas que le demos tampoco puede llegarse a él con monedas de 5 y 11 céntimos.

Viendo que hay varios números que pueden conseguirse y varios que no, y pensando que cualquier cantidad de dinero suficientemente grande podrá conseguir de esta forma (aunque habrá que matizar esto un poco), puede surgirnos la siguiente pregunta: ¿cuál es la mayor cantidad de dinero que no puede conseguirse con monedas de 5 y 11 céntimos? Bien, pues esa cantidad es precisamente 39 céntimos. Podéis pensar en cualquier cantidad de céntimos mayor que 39 y seguro que podrá obtenerse combinando una cierta cantidad de monedas de 5 céntimos con otra cierta cantidad de monedas de 11 céntimos. ¿Y eso? ¿Tiene alguna base matemática? ¿De qué va todo esto? Vamos a intentar explicar en qué consiste todo este tema.

El problema de las monedas y el número de Frobenius

Lo primero, sí, todo esto tiene base matemática (¿alguien lo dudaba?), el hecho de que el número 39 sea la mayor cantidad de dinero que no puede conseguirse con monedas de 5 y 11 céntimos no es casualidad, sino que obedece a una ley.

Este ejercicio de preguntarse qué cantidades pueden formarse por combinación de ciertas cantidades dadas se denomina problema de las monedas o problema de Frobenius. El planteamiento matemático del problema de las monedas es el siguiente:

Dados a_1, \ldots a_n enteros positivos cumpliendo que el máximo común divisor de ellos es 1 (es decir, que no hay ningún factor común a todos ellos), encontrar cuál es el mayor número entero que no puede ser expresado de la forma

k_1 \cdot a_1 + \ldots +k_n \cdot a_n

siendo k_1, \ldots k_n enteros no negativos (este tipo de combinación de elementos, donde los coeficientes son no negativos, se denomina combinación cónica).

El ejemplo que hemos planteado al comienzo cumple las condiciones de este enunciado, ya que n=2 y mcd(5,11)=1.

Primera cuestión: ¿por qué los números que vamos a combinar no pueden tener factores comunes (es decir, debe ser mcd(a_1, \ldots a_n)=1)? Pues por una razón muy simple: si no fuera así no existiría ese número máximo que no puede escribirse como combinación cónica de los a_i, de hecho todo número que no fuera múltiplo del máximo común divisor de ellos sería imposible de calcular de esta manera. Por ejemplo, combinando los números 4 y 10 no hay manera de obtener 41, ni 359, ni 387043467. Por ello la condición de que los a_i no tengan factores comunes es necesaria.

Segunda cuestión: ¿existe ese número máximo que no se puede escribir como combinación cónica de los a_i siempre que su máximo común divisor sea 1? Pues sí, existe siempre en estas condiciones. El llamado teorema de Schur, debido al matemático judío-aleman Issai Schur, tiene como consecuencia que si el máximo común divisor de los a_i es 1, existe este mayor número que no puede expresarse como combinación cónica de ellos.

Tercera cuestión: ¿tiene algún nombre este número? Pues sí, lo tiene. Como supongo que ya habréis intuido, este número se denomina número de Frobenius.

O sea, que el mayor número que no puede formarse con los a_i con los que estemos trabajando se llama número de Frobenius, que se suele representar por g(a_1, \ldots a_n). ¿Cómo se calcula? Veamos cómo calcularlo según la cantidad de números que tengamos inicialmente:

  • Si n=1, entonces a_1=1, ya que el máximo común divisor debe ser 1. Por tanto no hay número de Frobenius en este caso.
  • Si n=2, se conoce una sencilla fórmula para calcular el número de Frobenius. Si los números iniciales son a_1,a_2, entonces:

    g(a_1,a_2)=a_1 \cdot a_2 -a_1-a_2

    Por ello, en el ejemplo inicial el 39 era el mayor número que no puede formarse con los números 5 y 11:

    g(5,11)=5 \cdot 11 -5-11=39

    Y por ello, por poner otro ejemplo, combinando estos dos sellos en los que aparecen Euler y Lagrange (supongamos que las dos cantidades representan céntimos)

    no se podría enviar carta que necesitara 27 céntimos, pero sí una que necesitara cualquier cantidad mayor.

  • Para n=3 y superiores no se conoce una fórmula que calcule explícitamente el número de Frobenius. Existen cotas o fórmulas para conjunto de números que cumplen ciertas propiedades, de hecho existen algoritmos que resuelven el problema de las monedas en tiempo polinomial, pero no tenemos una fórmula tipo la del caso n=2.

Lo que sí tenemos es un interesante resultado sobre este tema debido al matemático indio Ravi Kannan, que dice que para n fijo existe un algoritmo en tiempo polinomial que resuelve el problema del número de Frobenius. El documento en concreto se denomina Lattice translates of a polytope and the Frobenius problem, y puede encontrarse junto con otros trabajos suyos en su página web.

Por cierto, hace poco Ravi Kannan ha sido galardonado con el premio Knuth, y bien merecido que lo tiene.

Frobenius y los McNuggets

Una de las aplicaciones más conocidas de este problema es la conocida como números McNugget (que, como podéis imaginar, trata sobre los McNuggets de McDonalds), que se le ocurrió a Henri Picciotto mientras cenaba con su hijo en un McDonalds.

La cuestión es que (al menos antes) los McNugget se servían en cajas de 6, 9 y 20 unidades. Si decimos que un número entero positivo es un número McNugget si corresponde a una cantidad de McNuggets que se puede formar con un determinado número de cajas de cada uno de los tipos, ¿podremos obtener cualquier cantidad de McNuggets? Al ser mcd(6,9,20)=1 se tiene que cuando la cantidad es suficientemente grande siempre se podrá conseguir con estas cajas. Pero también habrá una cantidad que será la mayor que no se puede conseguir. Ese mayor número que no es un número de McNugget es el número de Frobenius de este problema, que en este caso es 43.

Antonio Roldán nos habló en su blog (muy bien, como siempre) sobre Frobenius y los McNuggets para la primera edición del Carnaval de Matemáticas.

Fuentes:

Este artículo es mi primera aportación a la Edición 2.4 del Carnaval de Matemáticas, cuya anfitriona es ClaraGrima.

Print Friendly, PDF & Email
0 0 votes
Article Rating

¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉


Comparte: