Autor Tema: Conteo de cambio de billetes

0 Usuarios y 1 Visitante están viendo este tema.

25 Septiembre, 2008, 12:09 am
Leído 1680 veces

Eleal

  • Experto
  • Mensajes: 548
  • Karma: +0/-0
  • Sexo: Masculino
He tratado con el siguiente problema:

Contar de cuántas formas puede cambiarse un billete de 100 en billetes de 1, 2, 5, 10, 20, 50.

, pero hasta ahora no se me ha ocurrido una buena idea para resolverlo. Necesito por favor una pequeña pista para comenzar.

Saludos,

25 Septiembre, 2008, 12:33 am
Respuesta #1

zeo

  • Junior
  • Mensajes: 66
  • Karma: +0/-0
  • Sexo: Masculino
Hola

A ver si recuerdo, puede que me equivoque.

Se me ocurre que podrías contar el número de soluciones de la ecuación:

\( 1x_1+2x_2+5x_3+10x_4+20x_5+50x_6=100 \)
Con la condición de que \( x_i\geq{0}\ \forall{i=1,2,...,6}  \) 
                                 \( x_i\in{\mathbb{N}}  \)

Recuerdo que había que hallar una función generatriz... ¿te suena esto?

Saludos.

25 Septiembre, 2008, 12:38 am
Respuesta #2

Eleal

  • Experto
  • Mensajes: 548
  • Karma: +0/-0
  • Sexo: Masculino

Recuerdo que había que hallar una función generatriz... ¿te suena esto?


No, no conozco de funciones generatrices... 

25 Septiembre, 2008, 09:52 am
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 46,792
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola

 En lenguaje de funciones generatrices, el problema es equivalente a calcular el coeficiente de grado \( 100 \) del polinomio:

\( p(x)=(1+x+x^2+\ldots)(1+x^2+x^4+\ldots)(1+x^5+x^{10}+\ldots)(1+x^{10}+x^{20}+\ldots)(1+x^{20}+x^{40}+\ldots)(1+x^{50}+\ldots) \)

 Teniendo en cuenta que el número de billetes de cada tipo que cogemos equivale a tomar en ese producto la correspondiente potencia de \( x \); por ejemplo si tomamos \( 8 \) de un euro,\( 1 \) de dos euros, \( 0  \) de cinco euros, \( 0 \) de diez euros, \( 2 \) de veinte euros y \( 1 \) de cincuenta, equivale a tomar cuando hacemos el producto \( x^8 \) en el primer polinomio, \( x^{1\cdot 2} \) en el segundo, \( x^0=1 \), en tercero y cuarto, \( x^{2\cdot 20} \) en le quinto y \( x^{50} \) en el último.

 Ese polinomio puede escribirse como:

\( p(x)=\dfrac{1}{(1-x)(1-x^2)(1-x^5)(1-x^{10})(1-x^{20})(1-x^{50})} \)

 y el coeficiente del monomio de grado \( 100 \), es:

\(  \dfrac{p^{100)}(0)}{n!} \)

 Problema: ese cálculo no es fácil.

 No se me ocurre otra forma sistemática que no sea demasaido artesanal, de resolver el problema.

 Hecho ese cálculo por ordenador da: 4562

Saludos.

02 Octubre, 2008, 01:24 am
Respuesta #4

Eleal

  • Experto
  • Mensajes: 548
  • Karma: +0/-0
  • Sexo: Masculino
Muchas gracias por sus respuestas el_manco y zeo.

Tengo algunas dudas, pero creo que debo trabajarlas un poco más antes de escribirlas.

Saludos,