Problema de la moneda

El problema de la moneda (también conocido como el problema de la moneda de Frobenius o el problema de Frobenius, en honor al matemático Ferdinand Frobenius) es un problema matemático que consiste en averiguar cuál es la mayor cantidad de dinero que no puede obtenerse, utilizando solo monedas de denominaciones específicas. Por ejemplo, la cantidad más grande de dinero que no se puede obtener usando solo monedas de 3 y de 5 unidades es 7 unidades. La solución a este problema para un conjunto dado de denominaciones de moneda se le denomina el número Frobenius de dicho conjunto. El número de Frobenius existe siempre que el máximo común divisor del conjunto de las denominaciones de moneda no sea mayor que 1.

Con solo monedas de 2 peniques y 5 peniques, uno no puede obtener 3 peniques, pero puede obtener una cantidad integral mayor.

Hay una fórmula explícita para el número Frobenius cuando sólo hay monedas de dos denominaciones diferentes, x y y : xy − x − y. Si el número de denominaciones de moneda es tres o más, no se conoce ninguna fórmula explícita; pero, para cualquier número fijo de denominaciones de monedas, hay un algoritmo que calcula el número de Frobenius en tiempo polinomial (en los logaritmos de las denominaciones de monedas que forman la entrada). No se conoce ningún algoritmo de tiempo polinomial en el número de denominaciones de monedas, y es NP-Hard el problema general en el cual el número de denominaciones de monedas puede ser tan grande como se desee.

Definición

En términos matemáticos, el problema puede ser establecido de la siguiente manera:

Dados enteros positivos a₁, a₂, …, a_n tal que MCD (a₁, a₂, …, a_n) = 1, encuentre el mayor entero que no puede ser expresado como una combinación cónica entera de estos números, es decir, como una suma:

k₁a₁ + k₂a₂ + ··· + k_na_n,

Donde k₁, k₂, …, k_n son enteros no negativos(positivos o 0).

A este número se le llama el Número Frobenius del conjunto { a₁, a₂, …, a_n }, y generalmente se denota por g(a₁, a₂, …, a_n).

El requisito de que el máximo divisor común (MCD) sea igual a 1, es necesario para que exista el número de Frobenius. Si el MCD no fuera 1, cada entero que no sea un múltiplo del MCD sería inexpresable como una combinación lineal, y mucho menos cónica del conjunto, y por lo tanto no habría un número mayor. Por ejemplo, si tuviera dos tipos de monedas valoradas en 4 centavos y 6 centavos, el MCD sería 2, y no habría forma de combinar cualquier cantidad de tales monedas para producir una suma que era un número impar. Por el contrario, siempre que el MCD sea igual a 1, el conjunto de enteros que no se pueden expresar como una combinación lineal de { a₁, a₂, …, a_n } está definido según el teorema de Schur , y por lo tanto el número de Frobenius existirá.

Número de Frobenius para pequeños n

Solo existe una solución cerrada para el problema de la moneda donde n = 1 o 2. No se conoce ninguna solución cerrada para n > 2.

n = 1

Si n = 1, entonces a₁ = 1 y todos los números naturales podrán formarse. Por lo tanto, no existe ningún número Frobenius para la variable 1.

n = 2

Si n = 2, el número de Frobenius se puede encontrar a partir de la fórmula ${\displaystyle g(a_{1},a_{2})=a_{1}a_{2}-a_{1}-a_{2}}$ . Esta fórmula fue descubierta por James Joseph Sylvester en 1884. Sylvester también demostró en este caso que hay un total de ${\displaystyle N(a_{1},a_{2})=(a_{1}-1)(a_{2}-1)/2}$  números enteros no representables.

Otra forma de la ecuación para ${\displaystyle g(a_{1},a_{2})}$  es dada por Skupień en esta proposición: Si ${\displaystyle a_{1},a_{2}\in \mathbb {N} }$  y MCD(a_1, a_2) = 1 entonces, para cada ${\displaystyle n\geq (a_{1}-1)(a_{2}-1)}$ , hay exactamente un par de enteros no negativos ${\displaystyle \rho }$  y ${\displaystyle \sigma }$  tal que ${\displaystyle \sigma <a_{1}}$  y ${\displaystyle n=\rho a_{1}+\sigma a_{2}}$ .

La fórmula se prueba de la siguiente manera. Supongamos que deseamos construir el número ${\displaystyle m\geq (a_{1}-1)(a_{2}-1)}$ . Tenga en cuenta que, desde MCD(a_1, a_2) = 1<, todos los enteros ${\displaystyle m-ja_{2}}$  para ${\displaystyle j=0,1,\ldots ,a_{1}-1}$  son mutuamente distintos a ${\displaystyle a_{1}}$ . Por lo tanto hay un valor único de ${\displaystyle j}$ , es decir ${\displaystyle j=\sigma }$ , y entero no negativo ${\displaystyle \rho }$ , tal que ${\displaystyle m=\rho a_{1}+\sigma a_{2}}$ : Por lo tanto, ${\displaystyle \rho \geq 0}$  porque ${\displaystyle \rho a_{1}=m-\sigma a_{2}\geq (a_{1}-1)(a_{2}-1)-(a_{1}-1)a_{2}=-a_{1}+1}$ .

n = 3

Para desarrollar un algoritmo voraz se conocen los tres números (ver Numerical semigroup para conocer los detalles de tales algoritmos) aunque los cálculos pueden ser muy tediosos si se hacen a mano. Además, se han determinado los límites inferior y superior para los números de Frobenius de n = 3. El límite inferior propuesto por Davison tiene la formula siguiente

${\displaystyle g(a_{1},a_{2},a_{3})\geq {\sqrt {3a_{1}a_{2}a_{3}}}-a_{1}-a_{2}-a_{3}}$ 

la cual es relativamente aproximada.

Números de Frobenius para conjuntos especiales

Secuencias Aritméticas

Existe una fórmula simple para el número de Frobenius de un conjunto de enteros en una secuencia aritmética. Dados los enteros a, d, s con MCD(a, d) = 1:

${\displaystyle g(a,a+d,a+2d,\dots ,a+sd)=\left(\left\lfloor {\frac {a-2}{s}}\right\rfloor +1\right)a+(d-1)(a-1)-1.}$ 

Secuencias Geométrica

Existe también una solución de forma cerrada para el número de Frobenius de un conjunto en una secuencia geométrica. Dados los enteros m, n, k con MCD(m, n) = 1:

${\displaystyle g(m^{k},m^{k-1}n,m^{k-2}n^{2},\dots ,n^{k})=n^{k-1}(mn-m-n)+{\frac {m^{2}(n-1)(m^{k-1}-n^{k-1})}{m-n}}.}$ 

Una fórmula más simple que también muestra la simetría entre las variables es la siguiente. Dados los enteros ${\displaystyle a,b,k}$ , con MCD(a,b)=1, tal que ${\displaystyle A_{k}(a,b)=\{a^{k},a^{k-1}b,\ldots ,b^{k}\}}$ . Entonces

${\displaystyle g(A_{k}(a,b))={\sigma }_{k+1}(a,b)-{\sigma }_{k}(a,b)-(a^{k+1}+b^{k+1}),}$ 

Donde ${\displaystyle {\sigma }_{k}(a,b)}$  denota la suma de todos los enteros en ${\displaystyle A_{k}(a,b).}$ 

Ejemplos

Números de McNugget

 

Una caja de 20 McDonald's Chicken McNuggets.

Un caso especial del problema de la moneda a veces también se conoce como los números de McNugget. La versión McNuggets del problema de la moneda fue presentada por Henri Picciotto, quien la incluyó en su libro de texto de álgebra en coautoría con Anita Wah. Picciotto pensó en la aplicación en la década de 1980 mientras cenaba con su hijo en McDonald's, resolviendo el problema en una servilleta. Un número de McNugget es la cantidad total de McDonald's Chicken McNuggets en cualquier cantidad de cajas. En el Reino Unido, las cajas originales (antes de la introducción de las cajas de pepitas del tamaño de Happy Meal) tenían 6, 9 y 20 nuggets.

Según el teorema de Schur, dado que 6, 9 y 20 son relativamente primos, cualquier entero suficientemente grande se puede expresar como una combinación lineal de estos tres. Por lo tanto, existe un número mayor que no es McNugget, y todos los enteros son más grandes que los números de McNugget. A saber, cada entero positivo es un número de McNugget, con el número finito de excepciones:

1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, y 43.

Por lo tanto, el número más grande que no es McNugget es 43. El hecho de que cualquier entero mayor que 43 sea un número de McNugget se puede ver considerando las siguientes particiones enteras

${\displaystyle 44=6+9+9+20}$ 

${\displaystyle 45=9+9+9+9+9}$ 

${\displaystyle 46=6+20+20}$ 

${\displaystyle 47=9+9+9+20}$ 

${\displaystyle 48=6+6+9+9+9+9}$ 

${\displaystyle 49=9+20+20}$ 

Se puede obtener cualquier número entero más grande agregando un número de 6 a la partición apropiada anterior.

Alternativamente, desde ${\displaystyle {\textrm {MCM}}(9,20)=180}$  y ${\displaystyle 6|180}$ , la solución puede también ser obtenida aplicando una formula presentada para ${\displaystyle n=3}$ .

${\displaystyle g(6,9,20)={\textrm {MCM}}(6,9)+{\textrm {MCM}}(6,20)-6-9-20=18+60-35=43}$ 

Además, una verificación directa demuestra que 43 McNuggets no pueden comprarse, ya que:

1. Las cajas de 6 y 9 por sí solas no pueden formar 43 ya que solo pueden crear múltiplos de 3 (a excepción de 3 en sí);
2. Incluir una sola caja de 20 no ayuda, ya que el resto requerido (23) tampoco es un múltiplo de 3; y
3. Más de una caja de 20, complementada con cajas de tamaño 6 o mayor, obviamente no puede conducir a un total de 43 McNuggets.

Desde la introducción de las cajas de pepitas Happy Meal de 4 piezas, el número más grande que no es McNugget es 11. En los países donde el tamaño de 9 piezas se reemplaza por el tamaño de 10 piezas, no existe el número más grande que no sea McNugget como cualquier número impar no se puede hacer.

Otros ejemplos

En rugby union, hay cuatro tipos de puntaje: objetivo de penalización (3 puntos), gol de caída (3 puntos), try (5 puntos) y try convertido (7 puntos). Al combinar estos puntos, es posible un total de puntos, excepto 1, 2 o 4. En rugby sevens, aunque se permiten los cuatro tipos de puntaje, los intentos de penalización son raros y los objetivos son casi desconocidos. Esto significa que las puntuaciones de los equipos casi siempre consisten en múltiplos de try (5 puntos) y tries convertidos (7 puntos). Los puntajes siguientes (además de 1, 2 y 4) no se pueden hacer a partir de múltiplos de 5 y 7, por lo que casi nunca se ven en siete: 3, 6, 8, 9, 11, 13, 16, 18 y 23. A modo de ejemplo, ninguno de estos puntajes fue registrado en ningún juego en la 2014-15 Sevens World Series.

De manera similar, en el fútbol americano (reglas de la NFL), cualquier puntaje es posible en un juego sin pérdida excepto 1. Las únicas formas de ganar 1 punto son por conversión después de un touchdown de 6 puntos, o para ganar por pérdida, donde el puntaje se registrará como 1-0 o 0-1. Como se otorgan 2 puntos por safety y 3 puntos por un field goal, todos los demás puntajes, aparte de 1, son posibles.

Véase también

• Problema de cambio de monedas

Referencias

Enlaces externos

• How to order 43 Chicken McNuggets – Numberphile

•   Datos: Q2295746