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 \(n\) centavos, por ejemplo dando una formula recursiva para obtener el resultado para \(n+1\) 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 \(10\) 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 \(x+5y+10z+25u+50w=100\)
De la ecuación se desprende que \(x\) tiene que ser divisible por \(5\), porque todos los demás numeros de la ecuación lo son. Podemos poner entonces \(x=5x'\), luego es lo mismo que resolvamos \(x'+y+2z+5u+10w=20\) (divimos todo por \(5\)). La variable \(w\) puede tomar solo los valores \(0,1,2\). Si toma el último valor, nos vemos forzados a tomar \(x'=y=z=u=0\). Contamos entonces una solución, y podemos suponer entonces que \(w\) toma los valores \(0,1\). Sucede que podemos resolver, entonces, dos ecuaciones: \(x'+y+2z+5u=10\), o \(x'+y+2z+5u=20\).
Repetimos la misma lógica anterior para la primera ecuación: si \(u=2\), la unica solución es \(x'=y=z=u=0\). Sumamos una solución, y resolvemos \(x'+y+2z=5\) y \(x'+y+2z=10\). Ahora, una ecuacion de la forma \(x+y=n\) tiene \(n+1\) soluciones en enteros no negativos, son los pares \((x,n-x)\) para \(x=0,1,\ldots,n\). En la penúltima ecuacion, para \(z=0,1,2\) tenemos \(n=1,3,5\) que da \(2+4+6=12\) soluciones. En la ultima ecuación, tenemos \(0,2,4,6,8,10\), que da \(1+3+5+7+9+11=36\) soluciones. Esto suma un total de \(1+12+36=49\) soluciones a \(x+y+2z+5u=10\)
Pasamos a \(x+y+2z+5u=20\). Podemos hacer que \(u\) recorra \(0,1,2,3,4\), y nos da ecuaciones \(x+y+2z=n\) con \(n=0,5,10,15,20\). Ya vimos que en los tres primos casos sumamos \(49\) soluciones. Nos alcanza con mirar solamente \(x+y+2z=15\) y \(x+y+2z=20\). En el primer caso, \(z\) puede recorrer \(0,1,\ldots,7\) que nos da ecuaciones \(x+y=n\) con \(n=1,3,5,\ldots,15\), para un total de \(2+4+\cdots+16=72\) soluciones. En la segunda, tenemos \(n=0,2,4,\ldots,20\) que nos da \(1+3+\cdots+21=121\) soluciones. En total, juntamos \(49+72+121=242\)
Esto nos da un total de \(1+49+242=292\) 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 \(8\), lo unico que podemos hacer es agregar un \(2\), antes o después. Asi hay \(2\) soluciones que contienen un \(8\). Podemos considerar solo tiras con \(2,4,6\). Si contiene un \(6\), podemos a bien agregar un cuatro antes o después, o dos \(2\), de tres maneras diferentes. Así, hay \(5\) soluciones que contienen un \(6\). Resta el caso en que usamos solo \(2,4\). Si colocamos dos \(4\), resta agregar un \(2\), en tres lugares distintos. Esto da tres soluciones más. Finalmente, podemos considerar el caso que usamos un solo \(4\), que es lo mismo que insertar un \(4\) en la tira \(222\), hay \(4\) formas de hacerlo. La última tira posible es \(22222\). En total, hay\(2+5+3+4+1=15\) tiras posibles.