5 votos

¿Cuántas formas existen para agregar los números en el conjunto$k$ para que sea igual a$n$?

De cuántas maneras existen para agregar los números en el conjunto de $k$ a la igualdad de $n$?

Para un ejemplo específico, considere la siguiente: tengo infinitas monedas de un centavo, cinco centavos, diez centavos, cuartos, y loony (equivalente a 0.01, 0.05, 0.1, 0.25, y 1, para aquellos que no son Canadienses). Cuántos caminos hay para agregar estos números para obtener un dólar?

Algunas combinaciones serían:

$1 = 1$

$1 = 0.25 + 0.25 + 0.25 + 0.25$

$1 = 0.25 + 0.25 + 0.25 + 0.1 + 0.1 + 0.05$

Y así sucesivamente.

Varias personas han sugerido que el problema de monedas, aunque todavía tengo que encontrar una fuente que explica esta lo suficientemente bien como para que yo lo entienda.

10voto

rschwieb Puntos 60669

Tendrá suerte en Google para esto con la frase "problema de la moneda".

Tengo algunos enlaces en esta solución que llevarán al método general. Hay un problema del Proyecto Euler (o tal vez varios de ellos) que te piden que computes tantas formas de maneras absurdas, pero los programas (descubrí) pueden ser solo un puñado de líneas.

6voto

vadim123 Puntos 54128

La generación de la función de enfoque es buscar el coeficiente de $x^{100}$ $(1+x+x^2+x^3+\cdots)(1+x^5+x^{10}+x^{15}+\cdots)(1+x^{10}+x^{20}+x^{30}+\cdots)(1+x^{25}+x^{50}+x^{75}+\cdots)(1+x^{100}+x^{200}+x^{300}+\cdots)$

Más detalles, como se solicitó.

Vamos a imaginar que la multiplicación de estos (infinito) polinomios, y la recopilación de términos. Vamos a hacer esto de bajo grado alto grado. El término constante es $1$, la cual sólo puede obtenerse mediante la elección de $1$ a partir de cada uno de los cinco productos. El $x$ plazo es sólo $x$, que sólo puede obtenerse mediante la elección de $x$ desde el primer producto y $1$ de cada uno de los otros. El $x^2$ plazo es sólo $x^2$, que sólo puede obtenerse mediante la elección de $x^2$ desde el primer producto y $1$ de cada uno de los otros. Del mismo modo $x^3, x^4$.

Pero ahora el $x^5$ plazo es $2x^5$ -- una pieza proviene de la elección de $x^5$ desde el primer producto y $1$ de cada uno de los otros, y otra pieza proviene de la elección de $x^5$ a partir del segundo producto y $1$ de cada uno de los otros. Esto corresponde directamente a las dos formas en que podemos hacer cinco centavos, con cinco centavos (y cero, cinco, cero dimes, etc.) o con uno de níquel. De pasar, el coeficiente de $x^{10}$ es de 4, que viene de $x^{10}\cdot 1\cdot 1\cdot 1\cdot 1 + x^{5}\cdot x^{5}\cdot 1\cdot 1\cdot 1+1\cdot x^{10}\cdot 1\cdot 1\cdot 1+1\cdot 1\cdot x^{10}\cdot 1\cdot 1$. Esto corresponde a las cuatro posibilidades de diez centavos (el décimo término de la moneda de un centavo de producto), cinco centavos y uno de níquel (el quinto término de la moneda de un centavo de producto y el segundo término del níquel producto), dos monedas de cinco centavos (el segundo término del níquel del producto), y una moneda de diez centavos (el primer término de la moneda de diez centavos de producto).

En todos los casos la elección de $1$ a partir de un producto es la misma que la elección de $x^0$, o el cero-ésimo término de ese producto, o ninguno de la moneda.

De hecho podemos simplificar los productos porque son series geométricas, así que queremos que el coeficiente de $x^{100}$ $$\frac{1}{1-x}\frac{1}{1-x^5}\frac{1}{1-x^{10}}\frac{1}{1-x^{25}}\frac{1}{1-x^{100}}$$

Podemos alimentar esta en wolframalpha (buscar por "la expansión en cero" y haga clic en "más términos" un par de veces) para encontrar la respuesta es $243$.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X