Haga$n$% centavos con$1$ - ciento,$2$ - ciento, y$3$ - monedas de centavo

Question

Me encontré con el siguiente problema en Herber Wilf del libro Generatingfunctionology:

Demostrar que, en un país que ha $1$ -%, $2$- % y $3$-% monedas sólo, el número de maneras de cambiar $n$ centavos es exactamente el entero más cercano a $ \frac{(n+3)^2}{12} $.

Por supuesto, la solución siempre fue uno de los que hace uso de una generación de función. Sin embargo, es increíblemente tedioso. Es allí una manera de hacer esto sin necesidad de hacer uso de una función de generación?

---

Para referencia, aquí está la solución dada en el libro.

Si $f(n)$ es que el número, entonces $$ \begin {gather*} \sum_{n\ge 0} f(n) x^n = \frac {1}{(1-x)(1-x^2)(1-x^3)}\qquad\qquad\qquad\qquad \\ = \frac{1}{6(1-x)^3} + \frac{1 }{4(1-x)^2} + \frac {17}{72(1-x)} + \frac {1}{8(1+x)} + \frac {1}{9(1-\omega x)} + \frac {1}{9(1-\overline{\omega}x)}. \end {reunir*} $$ Si ampliamos cada uno de las fracciones de la derecha, nos encontramos con la fórmula de $$ f(n) = \frac {1}{6} \dbinom {n+2}{2} + \frac {1}{4} (n+1) + \frac {17}{72} + \frac {(-1)^n}{8} + \frac {2}{9} \cos \left( \frac {2n \pi}{3} \right), $$ la cual puede escribirse como $$ f(n) = \frac {(n+3)^2}{12} + \frac {-7 + 9 (-1)^n + 16 \cos \left( \frac {2n\pi}{3} \right)}{72}. $$ El segundo la fracción no exceda $ \frac {32}{72} < \frac {1}{2} $ en absoluto valor, por lo $f(n)$ es el único número entero que la distancia de $ \frac {(n+3)^2}{12} $ es de menos de $\frac{1}{2}$, según se requiera. $\Box$

Answer 1

Sólo te voy a mostrar cómo obtener un lineal de la recurrente respecto del problema, se ha explicado en varios lugares de cómo resolver estos.

Vamos a:

• $a(n)$ soluciones (maneras de cómo cambiar $n$) con sólo $1$c,
• $b(n)$ soluciones mediante el uso de sólo $1,2$c y al menos uno de los $2$c,
• $c(n)$ soluciones mediante el uso de todas las tres monedas y al menos uno de los $3$c.

Claramente cada solución se ajusta exactamente a una de las 3 categorías, por lo $f(n)=a(n)+b(n)+c(n)$.

Tenemos $a(n)=1$. Para $b(n)$, eliminamos una $2$c, y tenemos algo con otro $2$c a la izquierda o no. Por lo tanto,$b(n)=b(n-2)+a(n-2)$. Del mismo modo $c(n)=c(n-3)+b(n-3)+a(n-3)$. Por supuesto, esto sólo funciona para $n>3$, por lo que tenemos que añadir que $a(1)=a(2)=a(3)=b(2)=b(3)=c(3)=1$$b(1)=c(1)=c(2)=0$. Esta recurrencia lineal debe tener la solución deseada.

Sin embargo, como se puede ver, es mucho más simple de usar sólo OGF para este tipo de problemas.

Answer 2

El siguiente método puede ser explicado a cualquier estudiante, que comprende las ecuaciones de las líneas y sabe como suma de una progresión aritmética. Sin embargo, usted puede encontrar que es al menos tan difícil como el método que ya tiene!

La Idea

Pensar en puntos de $(x,y)$ en el avión como la representación de "$x$ 2 céntimos y $y$ 3 céntimos". Ahora, los puntos de la cuadrícula en el primer cuadrante o por debajo de la línea de $\mathcal L_N$ dada por $$2x+3y=N$$ are in one-to-one correspondence with ways of changing $N$ centavos.

Desde el área de esta región triangular es $\frac 12\frac N2 \frac N3=\frac{N^2}{12}$, ya podemos ver que el número de puntos que deben estar en el orden de $\frac{N^2}{12}$. Tan lejos, tan bueno.

Un Cálculo Exacto

Para averiguar el número exacto de puntos, se tendrá en cuenta el número de $k_N$ del primer cuadrante de los puntos que se encuentran en $\mathcal L_N$, para cada valor de $N$. (Sí, estamos dando el primer cuadrante para incluir en sus límites.) Desde cada punto de la cuadrícula $(x,y)$ se encuentra en algunos $\mathcal L_N$ (es decir,$\mathcal L_{2x+3y}$), el número total $A_N$ del primer cuadrante los puntos de cuadrícula en o por debajo de $\mathcal L_N$ está dado por $A_N = \sum_{n=0}^{N} \mathcal k_n$.

Podemos ver que cada una de las $\mathcal L_N$ cumple con los puntos de cuadrícula en intervalos regulares, es decir, con un inter-la separación entre los puntos de $\overrightarrow{(3,-2)}$. Ya que esto es exactamente la cantidad por la cual el primer cuadrante parte de $\mathcal L_N$ alarga al $N$ aumenta por $6$, y cada punto de la cuadrícula en $\mathcal L_N$ es tanto directamente por debajo de ($2$unidades) y directamente a la izquierda de ($3$unidades) un punto de la rejilla en $\mathcal L_{N+6}$, podemos ver que $k_{n+6}=k_n+1$. Por lo tanto, es suficiente para encontrar $k_0$ a través de $k_5$, y por la inspección vemos que son todos iguales a $1$ a excepción de$k_1$$0$.

$$\begin{eqnarray}(k_0,k_1,k_2,\ldots) = & 1,0,1,1,1,1, \\ & 2,1,2,2,2,2, \\ & 3,2,3,3,3,3, \\ & etc. \end{eqnarray}$$

Esta regularidad que nos permite encontrar fórmulas exactas para $A_N$ dependiendo $N$ mod $6$.

$$\begin{eqnarray} (A_0,\ A_6,\ A_{12},\ \ldots) &=& (1,\ 1+6,\ 1+6+12,\ \ldots) & \\ \mbox{So }\ \ \ \ A_{n=0+6m} &=& 1+6m(m+1)/2 &=& (n^2+6n+12)\;/\;12 \\ \mbox{Similarly, }\ \ \ \ A_{n=1+6m} &=& 1+6m(m+1)/2+m &=& (n^2+6n+5)\;/\;12 \\ A_{n=2+6m} &=& 1+6m(m+1)/2+2m+1 &=& (n^2+6n+8)\;/\;12 \\ A_{n=3+6m} &=& 1+6m(m+1)/2+3m+2 &=& (n^2+6n+9)\;/\;12 \\ A_{n=4+6m} &=& 1+6m(m+1)/2+4m+3 &=& (n^2+6n+8)\;/\;12 \\ A_{n=5+6m} &=& 1+6m(m+1)/2+5m+4 &=& (n^2+6n+5)\;/\;12 \\ \end{eqnarray}$$

Podemos ver que esto es siempre dentro de $\left[\,\frac{\!\!-4}{12}, \frac{3}{12}\right]$$(n+3)^2\,/\,12$.

Esto significa que $A_n$ siempre es el entero más cercano a $(n+3)^2\,/\,12$.

Answer 3

Es posible acortar un poco el argumento al notar que$$\operatorname{Res}\left(\frac{1}{(1-z)(1-z^2)(1-z^3)},z=1\right)=-\frac{17}{72},$ $, por lo tanto, la contribución dada por los polos simples$-1,\omega,\omega^2$ que se encuentran en el círculo unitario no puede exceder$\frac{17}{72}$, y es exactamente igual a$\frac{17}{72}$ cuando $6\mid n$. El polo en$z=1$ es un polo triple, por lo tanto,$f(n)$ crece como un polinomio de segundo grado. Al interpolar los valores de$f(n)$ en$n=0,n=6,n=12$, podemos derivar nuestra fórmula.

Answer 4

Esta es una solución de la forma del libro "los retos MATEMÁTICOS, PROOLEMS CON PRIMARIA SOLUCIONES VOL 1", por A. M. Yaglom y I. M. Yaglom :

En la preparación de $n$ centavos de 1-, 2-y 3-ciento sellos, se puede utilizar cualquiera de los 3 centavos sellos en todos, o uno de 3% de cupones, o 2 de ellos, etc., hasta un máximo de $q = \left[n/3\right]$ de ellos. En el primer caso el $n$ centavos de dólar tendría que estar compuesta enteramente de 1 y 2 céntimos de sellos, que puede ser hecho en $\left[n/2\right] + 1$ formas (por Favor vea las notas). En el segundo caso debemos formar a $n-3$ centavos con 1 y 2 céntimos de sellos, que se puede hacer en $\left[(n-3)/2\right] + l$ maneras. En el tercer caso debemos formar a $n-6$ centavos, que se puede hacer en $\left[(n-6)/2\right] + 1$ maneras. En general, en la $(k+1)^{th}$ de los casos, debemos formar a $n-3k$ centavos con 1 y 2 céntimos de sellos, que se puede hacer en $\left[(n-3k)/2\right] + l$ maneras.

Deje $n = 3q + r$ donde $q = \left[n/3\right]$ es el cociente obtenido al dividir 3 en $n$, e $r$ es el resto (por lo tanto $r = 0, l$ o $2$). Vemos entonces que en el último caso (donde $q$ 3 centavos sellos se utilizan), el resto de las $r$ centavos debe ser hecha hasta de 1 y 2 céntimos de sellos. Esto se puede hacer en $[r/2] + 1$ formas, por lo que tenemos un total de $$ S = \left(\left[\frac{n}{2}+1 \right] \right) + \left(\left[\frac{n-3}{2}+1 \right] \right) + \left(\left[\frac{n-6}{2}+1 \right] \right) + \ldots +\left(\left[\frac{r}{2}+1 \right] \right) $$ Ahora, tomamos nota de que para cualquier entero $m$, $\left[\frac{m}{2} \right] = \frac{m}{2} - \frac{1}{4} + \frac{(-1)^m}{4}$. Utilizamos este hecho simplemente la expresión de la $S$. $$ \begin{aligned} S = & \left(\frac{n}{2}+\frac{3}{4}+\frac{(-1)^{n}}{4} \right) + \left(\frac{n-3}{2}+\frac{3}{4}+\frac{(-1)^{n-3}}{} \right) \\ + & \left(\frac{n-6}{2}+\frac{3}{4}+\frac{(-1)^{n-6}}{4} \right) + \ldots + \left(\frac{r}{2}+\frac{3}{4}+\frac{(-1)^{r}}{4} \right) \end{aligned} $$ Desde allí se $q + 1$ paréntesis que contienen cada una un $\frac{3}{4}$, tenemos $$ \begin{aligned} S = & \frac{3(q+1)}{4} + \left( \frac{(-1)^n}{2}+\frac{(-1)^{n-3}}{2}+\frac{(-1)^{n-6}}{2}+\ldots+\frac{(-1)^r}{2} \right) \\ + & \left(\frac{n}{2}+\frac{n-3}{2}+\frac{n-6}{2}+\ldots+\frac{r}{2} \right) \end{aligned} $$ Los términos en el primer paréntesis se alternan en signo. Por lo tanto, esta entre paréntesis es igual a $\frac{1}{4}$ si ambos $n$ $r$ son incluso, $\frac{-1}{4}$ si ambos son impares, y $0$ lo contrario. Vamos a denotar su valor por $\epsilon$, y la nota para más tarde, a los efectos de que $\epsilon \geq 0$ al $r$ es incluso. Los términos del segundo paréntesis están en progresión aritmética. Así, $$ \begin{aligned} S & = \frac{3(q+1)}{4} + \epsilon + \frac{q+1}{2}\left(\frac{n}{2}+\frac{r}{2} \right) \\ & = \frac{q+1}{4} \left( 3+n+r \right) + \epsilon \\ & = \frac{3q+3}{12} \left( 3+n+r \right) + \epsilon \\ & = \frac{(n+3+r)(n+3-r)}{12} + \epsilon \\ & = \frac{\left(n+3) \right)^2}{12} - \frac{r^2}{12} + \epsilon \end{aligned} $$ El resto es para mostrar que $\left| - \frac{r^2}{12} + \epsilon \right| \leq \frac{1}{2}$$r=0, 1, 2$. Por lo tanto $S$, que es un entero, difiere de la de $(n +3)^2/12$ por una cantidad cuyo valor absoluto es menor que $\frac{1}{2}$· por lo Tanto, $S$ es el entero más cercano a $(n+3)^2/12$.

Nota : por Favor, consulte el problema 22 del mismo libro acerca de un argumento que para hacer $n$ centavos con sólo unos centavos y otra de la moneda que tiene el valor de $k$ centavos, entonces el número de maneras tendría que ser $\left[\frac{n}{k}\right]+1$ .