Problema de la moneda

Si${\displaystyle n=1}$, entonces debemos tener${\displaystyle a_{1}=1}$para que se puedan formar todos los números naturales.

Si${\displaystyle n=2}$El número de Frobenius se puede obtener a partir de la fórmula${\displaystyle g(a_{1},a_{2})=a_{1}a_{2}-a_{1}-a_{2}}$, que fue descubierto por James Joseph Sylvester en 1882. ^{[ 5 ] [ nb 1 ]} Sylvester también demostró para este caso que hay un total de${\displaystyle N(a_{1},a_{2})=(a_{1}-1)(a_{2}-1)/2}$enteros (positivos) no representables.

Otra forma de la ecuación para${\displaystyle g(a_{1},a_{2})}$Skupień ^{[ 7 ]} lo da en esta proposición: Si${\displaystyle a_{1},a_{2}\in \mathbb {N} }$y${\displaystyle \gcd(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 }$de tal manera que${\displaystyle \sigma <a_{1}}$y${\displaystyle n=\rho a_{1}+\sigma a_{2}}$.

La fórmula se demuestra de la siguiente manera. Supongamos que deseamos construir el número${\displaystyle n\geq (a_{1}-1)(a_{2}-1)}$. Desde${\displaystyle \gcd(a_{1},a_{2})=1}$, todos los números enteros${\displaystyle n-ja_{2}}$para${\displaystyle j=0,1,\ldots ,a_{1}-1}$son mutuamente distintos módulo${\displaystyle a_{1}}$Por lo tanto, cualquier número entero${\displaystyle m}$debe ser congruente módulo${\displaystyle a_{1}}$a uno de estos residuos; en particular, tomando${\displaystyle m=a_{1}}$existe un valor único de${\displaystyle j=\sigma \geq 0}$y un número entero único${\displaystyle t}$, de tal manera que${\displaystyle a_{1}=n-\sigma a_{2}+ta_{1}}$Reordenando, tenemos un número entero no negativo.${\displaystyle \rho =1-t}$de modo que${\displaystyle n=\rho a_{1}+\sigma a_{2}}$. En efecto,${\displaystyle \rho \geq 0}$porque${\displaystyle \rho a_{1}=n-\sigma a_{2}\geq (a_{1}-1)(a_{2}-1)-(a_{1}-1)a_{2}=-a_{1}+1>(-1)a_{1}}$.

Para demostrar que exactamente la mitad de los enteros${\displaystyle 0,1,\ldots ,ab-ab}$son representables como combinaciones lineales de enteros no negativos, primero se muestra que si el entero${\displaystyle k\in [0,ab-ab]}$es representable, entonces${\displaystyle Nk}$no es representable, donde${\displaystyle N=ab-ab}$.

Entonces se demuestra que lo contrario también es cierto: si${\displaystyle k}$no es representable, entonces${\displaystyle Nk}$es representable. Para demostrar esto, utilice el hecho de que${\displaystyle \gcd(a,b)=1}$, lo que nos permite escribir${\displaystyle k=xa+yb}$. Reduciendo y reorganizando los coeficientes mediante la suma de múltiplos de${\displaystyle ab}$Según sea necesario, podemos asumir${\displaystyle 0\leq x<b}$(de hecho, esto${\displaystyle x}$es único tal${\displaystyle x}$que satisfacen la ecuación y las desigualdades).

De manera similar tomamos${\displaystyle u,v}$satisfactorio${\displaystyle Nk=ua+vb}$ y${\displaystyle 0\leq u<b}$Ahora podemos agregar estas ecuaciones para escribir${\displaystyle N=(u+x)a+(y+v)b}$que, usando${\displaystyle N=ab-ab}$rendimientos${\displaystyle ab-b(1+y+v)=a(x+u+1)}$. El número entero${\displaystyle x+u+1}$es positivo, porque${\displaystyle x,u\geq 0}$. De hecho, dado que el lado izquierdo de${\displaystyle ab-b(1+y+v)=a(x+u+1)}$es divisible por${\displaystyle b}$, y${\displaystyle (a,b)=1}$, debemos tener eso${\displaystyle x+u+1}$es divisible por${\displaystyle b}$. Todavía${\displaystyle x,u\leq b-1}$, entonces${\displaystyle x+u+1\leq 2b-1}$, de modo que${\displaystyle x+u+1=b}$. Sustituyendo esto en${\displaystyle ab-b(1+y+v)=a(x+u+1)}$y restando${\displaystyle ab}$de ambos lados rinde${\displaystyle b(1+y+v)=0}$. Entonces${\displaystyle 1+y+v=0}$Esto implica que${\displaystyle y+v=-1}$, lo que significa que exactamente uno de${\displaystyle y}$o${\displaystyle v}$es negativo. Si${\displaystyle y}$es negativo, entonces${\displaystyle v\geq 0}$, lo que significa que${\displaystyle Nk=ua+vb}$es representable; el caso cuando${\displaystyle v}$es negativo implica que${\displaystyle k}$es representable.

Por lo tanto, para cualquier entero no negativo${\displaystyle k\in [0,ab-ab]}$, sabemos que exactamente uno de${\displaystyle k}$o${\displaystyle (ab-ab)-k}$es representable (y estos son distintos, porque${\displaystyle ab-ab}$debe ser impar como los números enteros${\displaystyle a,b}$son primos relativos). Esto demuestra que la mitad de los enteros en el rango dado son representables; puesto que hay${\displaystyle (ab-a-b+1)=(a-1)(b-1)}$números enteros en el rango${\displaystyle [0,ab-ab]}$Esto da el resultado deseado.

Se conocen fórmulas ^{[ 8 ]} y algoritmos rápidos ^{[ 9 ] para tres números, aunque los cálculos pueden ser muy tediosos si se hacen a mano.}

También se han determinado cotas inferiores y superiores más sencillas para los números de Frobenius para n = 3. La cota inferior asintótica debida a Davison

${\displaystyle f(a_{1},a_{2},a_{3})\equiv g(a_{1},a_{2},a_{3})+a_{1}+a_{2}+a_{3}\geq {\sqrt {3a_{1}a_{2}a_{3}}}}$

es relativamente afilado. ^{[ 10 ]} (${\displaystyle f}$Aquí está el número de Frobenius modificado, que es el mayor entero no representable por combinaciones lineales de enteros positivos de${\displaystyle a_{1},a_{2},a_{3}}$.)

El comportamiento promedio asintótico de${\displaystyle f}$para tres variables también se conoce como: ^{[ 11 ]}

${\displaystyle f(a_{1},a_{2},a_{3})\sim {\frac {8}{\pi }}{\sqrt {a_{1}a_{2}a_{3}}},}$

Existe una fórmula simple para el número de Frobenius de un conjunto de enteros en una sucesión aritmética . ^{[ 1 ] : 59-60} Dados los enteros a , d , w con mcd( a , d ) = 1:   

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

El${\displaystyle n=2}$El caso anterior puede expresarse como un caso especial de esta fórmula.

En caso de que${\displaystyle a>w^{2}-3w+1}$, podemos omitir cualquier subconjunto de los elementos${\displaystyle a+2d,a+3d,...,a+(w-3)d,a+(w-2)d}$a partir de nuestra sucesión aritmética y la fórmula para el número de Frobenius permanece igual. ^{[ 14 ]}

También existe una solución en forma cerrada para el número de Frobenius de un conjunto en una sucesión geométrica . ^{[ 15 ]} 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 simetría entre las variables es la siguiente. Dados los enteros positivos${\displaystyle a,b,k}$, con${\displaystyle \gcd(a,b)=1,}$dejar${\displaystyle A_{k}(a,b)=\{a^{k},a^{k-1}b,\ldots ,b^{k}\}}$. Entonces ^{[ 16 ]}

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

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

Un caso especial del problema de la moneda también se conoce a veces como los números McNugget . La versión McNuggets del problema de la moneda fue introducida por Henri Picciotto, quien la publicó como un acertijo en Games Magazine en 1987, ^{[ 17 ]} y la incluyó en su libro de texto de álgebra del que fue coautor con Anita Wah. ^{[ 18 ]} 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 McNugget es el número total de McNuggets de pollo de McDonald's en cualquier número de cajas. En el Reino Unido , las cajas originales (antes de la introducción de las cajas de nuggets del tamaño de la Cajita Feliz ) eran de 6, 9 y 20 nuggets.

Según el teorema de Schur , dado que 6, 9 y 20 son primos relativos (en conjunto) , cualquier entero suficientemente grande puede expresarse como una combinación lineal (entera y no negativa) de estos tres. Por lo tanto, existe un número no McNugget máximo, y todos los enteros mayores que él son números McNugget. Es decir, todo entero positivo es un número McNugget, con un 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 (secuencia A065003 en el OEIS ) .

Por lo tanto, el mayor número que no es un número McNugget es 43. ^{[ 19 ]} El hecho de que cualquier entero mayor que 43 sea un número McNugget se puede ver al considerar las siguientes particiones de enteros.

${\displaystyle 44=6+6+6+6+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}$

Cualquier número entero mayor se puede obtener sumando cierta cantidad de 6 a la partición correspondiente anterior. Una simple comprobación demuestra que, efectivamente, no se pueden comprar 43 McNuggets, 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 (con la excepción del 3 mismo);
2. Incluir una sola caja de 20 no ayuda, ya que el resto requerido (23) tampoco es múltiplo de 3; y
3. Más de una caja de 20, complementada con cajas de tamaño 6 o más grandes, obviamente no puede dar como resultado un total de 43 McNuggets.

Desde la introducción de las cajas de nuggets de 4 piezas del tamaño de la Cajita Feliz, el número más grande que no es un McNugget es 11. En los países donde el tamaño de 9 piezas se reemplaza por el de 10 piezas, no hay un número más grande que no sea un McNugget, ya que no se puede fabricar ningún número impar.

En el rugby union , existen cuatro tipos de puntuación: penal (3 puntos), drop goal (3 puntos), try (5 puntos) y try convertido (7 puntos). Al combinarlos, es posible cualquier total de puntos excepto 1, 2 o 4. En el rugby seven , aunque se permiten los cuatro tipos de puntuación, los intentos de penal son raros y los drop goals son casi desconocidos. Esto significa que las puntuaciones de los equipos casi siempre consisten en múltiplos de tries (5 puntos) y tries convertidos (7 puntos). Las siguientes puntuaciones (además de 1, 2 y 4) no se pueden obtener a partir de múltiplos de 5 y 7 y, por lo tanto, casi nunca se ven en el rugby seven: 3, 6, 8, 9, 11, 13, 16, 18 y 23. A modo de ejemplo, ninguna de estas puntuaciones se registró en ningún partido de las Series Mundiales de Rugby Seven 2014-15 .

De manera similar, en el fútbol americano , la única forma de que un equipo anote exactamente un punto es si se otorga un safety al equipo contrario cuando intentan convertir después de un touchdown (que en este caso tiene un valor de 6). Como se otorgan 2 puntos por safeties en juego regular, y 3 puntos por goles de campo , todos los resultados excepto 1-0, 1-1, 2-1, 3-1, 4-1, 5-1 y 7-1 son posibles. Esto está directamente relacionado con el concepto de Scorigami .

El algoritmo Shellsort es un algoritmo de ordenación cuya complejidad temporal es actualmente un problema abierto . La complejidad en el peor de los casos tiene un límite superior que se puede expresar en términos del número de Frobenius de una secuencia dada de enteros positivos.

Las redes de Petri son útiles para modelar problemas en computación distribuida . Para tipos específicos de redes de Petri, concretamente los circuitos ponderados conservativos, se busca determinar qué "estados" o "marcas" posibles con un peso dado están "activos". El problema de determinar el peso mínimo activo es equivalente al problema de Frobenius.

Cuando un polinomio univariado se eleva a alguna potencia, se pueden tratar los exponentes del polinomio como un conjunto de números enteros. El polinomio expandido contendrá potencias de${\displaystyle x}$mayor que el número de Frobenius para algún exponente (cuando MCD=1), por ejemplo, para${\displaystyle (1+x^{6}+x^{7})^{n}}$el conjunto es {6, 7} que tiene un número de Frobenius de 29, por lo que un término con${\displaystyle x^{29}}$nunca aparecerá por ningún valor de${\displaystyle n}$pero algún valor de${\displaystyle n}$dará términos que tengan algún poder de${\displaystyle x}$mayor que 29. Cuando el MCD de los exponentes no es 1, entonces las potencias mayores que algún valor solo aparecerán si son un múltiplo del MCD, por ejemplo,${\displaystyle (1+x^{9}+x^{15})^{n}}$, potencias de 24, 27,... aparecerán para algún valor(es) de${\displaystyle n}$pero nunca valores mayores que 24 que no sean múltiplos de 3 (ni los valores más pequeños, 1-8, 10-14, 16, 17, 19-23).