Nota: Aquí se utiliza la generación de funciones para facilitar algunos cálculos. Para conveniencia solamente se omite la escritura del símbolo de la moneda.
Antes de empezar a contestar las preguntas, nos fijamos en OPs ejemplos y derivar las correspondientes funciones de generación.
Ejemplo 1: Nueve monedas de $\mathcal{A}=\{1,1,1,1,5,10,10,25,50\}$
Podemos usar hasta a $4$ monedas de un centavo a cambio de dinero. Esto puede ser escrito como $$x^0+x^1+x^2+x^3+x^4$$ The exponent $k$ of $x^k$ indica el número de monedas de un centavo utilizados para el intercambio. Del mismo modo que nos dan para todas las monedas
\begin{array}{rrl}
1,1,1,1\qquad&\qquad 1+x+x^2+x^3+x^4=&(1-x^5)/(1-x)\\
5\qquad&\qquad1+x^5=&(1-x^{10})/(1-x^5)\\
10,10\qquad&\qquad1+x^{10}+x^{20}=&(1-x^{30})/(1-x^{10})\\
25\qquad&\qquad1+x^{25}=&(1-x^{50})/(1-x^{25})\\
50\qquad&\qquad1+x^{50}=&(1-x^{100})/(1-x^{50})
\end{array}
Llegamos a la conclusión: La generación de la función $A(x)$ para las diferentes cantidades que pueden ser obtenidos por los números del conjunto múltiple $\mathcal{A}$ es
\begin{align*}
\frac{1-x^5}{1-x}&\cdot\frac{1-x^{10}}{1-x^{5}}\cdot\frac{1-x^{30}}{1-x^{10}}\cdot\frac{1-x^{50}}{1-x^{25}}\cdot\frac{1-x^{100}}{1-x^{50}}\\
&=\frac{1-x^{30}}{1-x}\cdot\frac{1-x^{100}}{1-x^{25}}\\
&=(1+x+x^2+\cdots+x^{29})(1+x^{25}+x^{50}+x^{75})\tag{2}
\end{align*}
Vemos que algunos de los factores que cancelar y obtener una representación (2), que muestra muy bien las cantidades que se pueden obtener.
Comentario: La izquierda factor de $1+x+\cdots+x^{29}$ (2) multiplicada por el término de $1$ desde la derecha factor muestra que los montos $\{0,1,\ldots,29\}$ puede ser generado. La multiplicación con el segundo término $x^{25}$ da $\{25,26,\ldots,54\}$, etc. Por lo tanto, obtener
\begin{align*}
\{0,1,\ldots,29\}\cup\{25,26,\ldots,54\}\cup\{50,51,\ldots,79\}\cup\{75,76,\ldots,104\}
\end{align*}
Vamos a ver, que todos los importes de $1$ $104$ puede ser generado y de acuerdo a la no-vacío intersección de los conjuntos de los números
\begin{align*}
\{25,26,27,28,29\}\cup\{50,51,52,53,54\}\cup\{75,76,77,78,79\}
\end{align*}
pueden ser generados en dos diferentes maneras, por ejemplo,$26=25+1=10+10+5+1$.
Ejemplo 2: Nueve monedas de $\mathcal{B}=\{1,1,1,1,5,5,10,25,50\}$
De forma análoga al ejemplo 1, obtenemos la generación de la función $B(x)$ para las diferentes cantidades que pueden ser obtenidos por los números del conjunto múltiple $\mathcal{B}$ es
\begin{align*}
\frac{1-x^5}{1-x}&\cdot\frac{1-x^{15}}{1-x^{5}}\cdot\frac{1-x^{20}}{1-x^{10}}\cdot\frac{1-x^{50}}{1-x^{25}}\cdot\frac{1-x^{100}}{1-x^{50}}\\
&=\frac{1-x^{15}}{1-x}\cdot\frac{1-x^{20}}{1-x^{10}}\cdot\frac{1-x^{100}}{1-x^{25}}\\
&=(1+x+x^2+\cdots+x^{14})(1+x^{10})(1+x^{25}+x^{50}+x^{75})\tag{3}
\end{align*}
Llegamos a la conclusión de que: El producto de los dos de la izquierda factores en (3) da todas las cantidades de$0$$24$. Algunos de ellos $\{10,11,12,13,14\}$ se pueden generar de dos maneras diferentes. Multiplicación con el resto de términos $x^{25},x^{50}$ $x^{75}$ de los de más a la derecha factor da todos los números hasta el $99$.
\begin{align*}
\{0,1,\ldots,24\}\cup\{25,26,\ldots,49\}\cup\{50,51,\ldots,74\}\cup\{75,76,\ldots,99\}
\end{align*}
Con la ayuda de funciones de generación de responder a las dos primeras preguntas y considerar algunos aspectos de la tercera pregunta.
Primera pregunta: Puede que todas las cantidades de $1$ $99$ ser generado por un conjunto múltiple $\mathcal{C}$ que contengan menos de nueve monedas?
Tenga en cuenta, que necesitamos en cualquier caso, las cuatro monedas de a $\{1,1,1,1\}\subset \mathcal{C}$ a generar las cantidades $\{1,2,3,4\}$. Obtenemos
\begin{align*}
\{1,1,1,1\}\subset \mathcal{C}\qquad\rightarrow\qquad \{1,2,3,4\}\qquad\rightarrow\qquad\frac{1-x^5}{1-x}
\end{align*}
Para mantener el número de monedas pequeñas y para generar los importes $\{5,6,7,8,9\}$ también tenemos que poner $5$$\mathcal{C}$.
\begin{align*}
\{1,1,1,1,5\}\subset \mathcal{C}\qquad\rightarrow\qquad \{1,2,\ldots,9\}\qquad\rightarrow\qquad\frac{1-x^{10}}{1-x}
\end{align*}
Con el fin de obtener el importe $10$ y para mantener el número de monedas tan pequeñas como sea posible, le tiene que agregar $5$ o $10$.
\begin{align*}
\{1,1,1,1,5,5\}\subset \mathcal{C}\qquad\rightarrow\qquad \{1,2,\ldots,14\}\qquad\rightarrow\qquad\frac{1-x^{15}}{1-x}\tag{4}\\
\{1,1,1,1,5,10\}\subset \mathcal{C}\qquad\rightarrow\qquad \{1,2,\ldots,19\}\qquad\rightarrow\qquad\frac{1-x^{20}}{1-x}\tag{5}
\end{align*}
Aquí vemos que necesitamos al menos seis monedas para obtener las cantidades de la $1$ $14$resp. $19$. Por el camino, tenga en cuenta que los polinomios en (4) que tiene la forma
\begin{align*}
\frac{1-x^{n}}{1-x}=1+x+x^2+\cdots+x^{n-1}
\end{align*}
lo que implica, que los coeficientes de $x^k, 0\leq k\leq n-1$ siempre son iguales a $1$ y la representación de las cantidades que hasta ahora es en ambos casos únicos.
Ya que queremos tomar sólo hasta ocho monedas y tenemos que obtener las cantidades a a $99$ necesitamos que $25$ $50$ monedas de centavo o dos $50$ monedas de centavo. Pero vemos a simple vista que ninguno de los resultados posibles de generar el importe $20$ (además de otras cantidades que no se generan).
\begin{align*}
&\{1,1,1,1,5,5,25,50\}&\{1,1,1,1,5,10,25,50\}\\
&\{1,1,1,1,5,5,50,50\}&\{1,1,1,1,5,10,50,50\}\\
\end{align*}
Conclusión: necesitamos al menos nueve monedas con el fin de generar todas las cantidades de$1$$99$.
Segunda pregunta: ¿Podemos encontrar un conjunto de cinco denominaciones de monedas que maximiza el rango de valores cubiertos con el cambio exacto mediante una óptima bolsa de nueve monedas?
Podemos proceder con (5), que proporciona una configuración necesaria para poder obtener todas las cantidades de$1$$19$.
Se observa, se puede agregar un $25$ o $50$ ciento de la moneda, desde luego que no llegaría todas las cantidades de $1$ $19+25$ resp. $1$ $19+50$ . Añadimos $10$ para no perder ningún número y obtener como muchos de los nuevos números como sea posible.
\begin{align*}
\{1,1,1,1,5,10,10\}\qquad\rightarrow\qquad&\frac{1-x^{5}}{1-x}\cdot\frac{1-x^{10}}{1-x^{5}}\cdot\frac{1-x^{30}}{1-x^{10}}\\
&=\frac{1-x^{30}}{1-x}\tag{6}
\end{align*}
Podemos observar, que todos los importes de $1$ $29$ puede ser únicamente obtenida debido a la representación (6). Así, esta constelación representa el máximo de todas las configuraciones para llegar a montos de hasta $29$ $7$ monedas.
El siguiente paso es con el fin de evitar vacíos y obtener cantidades tan grandes como sea posible para anexar un $25$ ciento de la moneda, que da a todas las cantidades hasta el $29+25=54$ (no siempre es único). Ya tenemos cantidades tan grandes como sea posible y ya podemos obtener todos los valores de $1$ $54$podemos anexar un $50$ ciento de la moneda en el siguiente paso.
Obtenemos de esta manera el conjunto múltiple $\mathcal{A}$.
Conclusión: Ejemplo 1 ya ofrece la máxima constelación de un conjunto de nueve monedas, dando todas las cantidades de$1$$104$.
Tercera pregunta: ¿Podemos generalizar estas preguntas anteriores para valores arbitrarios (es decir, un número arbitrario de denominaciones de monedas y/o un objetivo arbitrario de valor)?
Cuando se utilizan funciones de generación, un arbitray valor objetivo $N$ y un número arbitrario de denominaciones de moneda, restringido a la norma de la moneda set $(1,5,10,25,50)$ con multiplicidades $(m_1,m_2,m_3,m_4,m_5)$ es un polinomio $P(x)$ de la forma
\begin{align*}
P(x)&=\sum_{j=0}^{N}a_jx^j\\
&=\frac{\left(1-x^{m_1+1}\right)\left(1-x^{5(m_2+1)}\right)\left(1-x^{10(m_3+1)}\right)
\left(1-x^{25(m_4+1)}\right)\left(1-x^{50(m_5+1)}\right)}
{(1-x)\left(1-x^{5}\right)\left(1-x^{10}\right)\left(1-x^{25}\right)\left(1-x^{50}\right)}\\
\end{align*}
con $a_j>0, 0\leq j \leq N$.
Supongo que, al menos para algunos casos específicos de información que se puede deducir de la teoría de la cyclotomic polinomios.
