¿De cuántas maneras se puede pagar 1000 céntimos utilizando

Question

El problema consiste en determinar el número de maneras en que se puede pagar $1000$ cientes utilizando trozos de $10$ centavos y $20$ centes.

Mi planteamiento fue el siguiente:

El número buscado no es sino el número de parejas de naturales $(x,y)$ Satisfaciendo a

$$10x+20y=1000$$

o $$x + 2y = 100$$

Este número es la forma de escribir $100$ como la suma de un número par y otro natural por lo que es $51$ .

He leído en algún sitio que esto depende de si el orden de elección de las piezas importa o no (este último es el caso que yo traté)

¿Es correcto mi planteamiento? y ¿Qué pasa con el caso en el que el orden importa?

Gracias.

Answer 1

Su planteamiento es correcto; normalmente, cuando se cuenta el número de formas de dar el cambio, sólo importa el número de monedas de cada tipo presentes, no el orden en que se entregan al cajero. Y el número de $2$ las monedas pueden estar entre $0$ y $50$ inclusive, que determina el número de $1$ monedas.

Si el orden es importante, resulta que el número de formas de hacer el cambio para $1000$ utilizando $10$ s y $20$ s, o de manera equivalente hacer el cambio para $100$ utilizando $1$ s y $2$ s, es $F_{101}$ El $101^{st}$ Número de Fibonacci. Dejando $a_n$ sea el número de secuencias ordenadas de $1$ s y $2$ s añadiendo a $n$ se puede demostrar que $a_n=a_{n-1}+a_{n-2}$ condicionando a que la última moneda sea una $1$ o un $2$ . Esto es lo mismo que la recurrencia de Fibonacci, así que una rápida verificación de los dos casos base $a_0=1$ , $a_1=1$ demuestra que $a_n=F_{n+1}$ .