Con un poco de retraso, dejo un nuevo problema, pero esta vez de combinatoria, digamos de Álgebra I.

Supongamos que tenemos monedas de 1, 5, 10, 25 y 50 centavos, y queremos cambiar 1 peso. ¿De cuantas maneras diferentes podemos hacerlo? ¿Pueden generalizarlo a cambiar centavos, por ejemplo dando una formula recursiva para obtener el resultado para de los anteriores?

Supongamos ahora que tenemos que poner las estampillas de un correo en una fila de cuatro, y podemos usar estampillas de 2, 4, 6 y 8 centavos. ¿De cuantas maneras diferentes podemos hacerlo, si el monto a pagar es de centavos?

Para la o el interesado, los problemas (y muchisimos mas!) son del libro "Problemas y Teoremas en Analisis" de Pólya y Szegö.

Esta claro que estamos contando la cantidad de soluciones en enteros no negativos a la ecuación

De la ecuación se desprende que tiene que ser divisible por , porque todos los demás numeros de la ecuación lo son. Podemos poner entonces , luego es lo mismo que resolvamos (divimos todo por ). La variable puede tomar solo los valores . Si toma el último valor, nos vemos forzados a tomar . Contamos entonces una solución, y podemos suponer entonces que toma los valores . Sucede que podemos resolver, entonces, dos ecuaciones: , o .

Repetimos la misma lógica anterior para la primera ecuación: si , la unica solución es . Sumamos una solución, y resolvemos y . Ahora, una ecuacion de la forma tiene soluciones en enteros no negativos, son los pares para . En la penúltima ecuacion, para tenemos que da soluciones. En la ultima ecuación, tenemos , que da soluciones. Esto suma un total de soluciones a

Pasamos a . Podemos hacer que recorra , y nos da ecuaciones con . Ya vimos que en los tres primos casos sumamos soluciones. Nos alcanza con mirar solamente y . En el primer caso, puede recorrer que nos da ecuaciones con , para un total de soluciones. En la segunda, tenemos que nos da soluciones. En total, juntamos

Esto nos da un total de soluciones.

Pasamos al segundo problema. Fíjense que ahora el orden de los números en cuestión es relevante. Estamos resolviendo, entonces, el siguiente problema: calcular la cantidad de tiras ordenadas de números 2,4,6,8 cuya suma es 10. Si la tira contiene un , lo unico que podemos hacer es agregar un , antes o después. Asi hay soluciones que contienen un . Podemos considerar solo tiras con . Si contiene un , podemos a bien agregar un cuatro antes o después, o dos , de tres maneras diferentes. Así, hay soluciones que contienen un . Resta el caso en que usamos solo . Si colocamos dos , resta agregar un , en tres lugares distintos. Esto da tres soluciones más. Finalmente, podemos considerar el caso que usamos un solo , que es lo mismo que insertar un en la tira , hay formas de hacerlo. La última tira posible es . En total, hay tiras posibles.