BMO2 2001 la Pregunta 1 de la Recurrencia de la Relación

Question

Ahmed y Beth han respectivamente $p$ $q$ a las canicas, con $p > q$. Comenzando con Ahmed, de las que cada una da a la otra como muchos canicas como los otros que ya posee. Se encontró que después de $2n$ tales transferencias, Ahmed ha $q$ mármoles y Beth ha $p$ a las canicas. Encontrar $\frac{p}{q}$ en términos de $n$.

El número de canicas tiene cada persona parece seguir un patrón, por ejemplo: Ahmed tiene inicialmente $p$ a las canicas, a continuación, $p-q$ y, a continuación,$2p-2q$, con un coeficiente de $p$ inicialmente $1$ y el coeficiente de $q$ inicialmente $0$, que siguen el patrón que se $a_{m+1}=2a_{m}$ si $m$ es impar y $a_{m+1}=2a_{m}-1$ si $m$ es incluso (donde $m$ es el número de intercambios), un resultado similar es cierto para Beth. Yo, sin embargo, si pudiera encontrar una fórmula para $a_{m}$ en términos de $n$ la pude conjunto es igual a $q$ Ahmed el caso y encontrar a $\frac{p}{q}$ en términos de $n$, pero no puedo encontrar la manera de hacer esto. También he considerado trigonométricas sustitución, pero yo realmente no sé qué sustituto.

Si alguien pudiera dar una respuesta, que sería muy apreciada.

Answer 1

Usted ya tiene una buena respuesta, esto es sólo otra manera de resolver la recurrencia. Deje $p+q = S$ y denotan $a(n)$ de los mármoles Ahmed tiene. Claramente $a(0) = p$.

Así que vamos a $a(2k)$ denotar las canicas Ahmed tiene después de $2k$ transferencias. Entonces Beth debe tener $S-a(2k)$ canicas por la Ley de la Conservación de los Mármoles. la siguiente transferencia debe conducir a $a(2k+1) = a(2k)-(S-a(2k))= 2a(2k)-S$, y después de que hayamos $a(2k+2) = 4a(2k)-2S$.

Podemos ahora definir $f(k) = a(2k)$ a simplificar las cosas, y obtener la recursividad $$f(k+1) = 4f(k)-2S$$
con $f(0)=p$. La solución de este daría $$f(k) = \frac13\left((4^k+2)p-2(4^k-1)q \right)$$

Establecimiento $f(n)=q$, $3q = (4^k+2)p-2(4k-1)q \implies \dfrac{p}q = \dfrac{2\cdot4^n+1}{4^n+2}$...

Answer 2

Un álgebra lineal enfoque.

Deje $(p_k,q_k)$ ser la pareja después de $2k$ transferencias. Por lo $(p_0,q_0)=(p,q)$.

A continuación, después de $2n+1$ transferencias, tienen $(p_k-q_k,2q_k)$. Después de $2k+2$ transferencias, se tiene: $$(p_{k+1},q_{k+1})=(2p_k-2q_k, 3q_k-p_k)$$

Por lo que $$\begin{pmatrix}q\\p\end{pmatrix}=\begin{pmatrix}p_{n}\\q_{n}\end{pmatrix}= \begin{pmatrix}2&-2\\-1&3\end{pmatrix} \begin{pmatrix}p_{n-1}\\q_{n-1}\end{pmatrix} = \begin{pmatrix}2&-2\\-1&3\end{pmatrix}^{n} \begin{pmatrix}p\\q\end{pmatrix} $$

Así pues, usted desea analizar $A=\begin{pmatrix}2&-2\\-1&3\end{pmatrix}$.

El polinomio característico de a$A$$(x-2)(x-3)-1\cdot2=x^2-5x+4=(x-1)(x-4)$. Un vector propio de valor propio $1$$v_1=(2,1)^T$, un vector propio de valor propio $4$$v_4=(1,-1)^T$. Por lo $$\begin{pmatrix}p\\q\end{pmatrix}=\frac{p+q}{3}v_1 + \frac{p-2q}{3}v_4$$ y por lo tanto:

$$\begin{align}A^n \begin{pmatrix}p\\q\end{pmatrix} &= \frac{p+q}{3}v_1 + 4^n\frac{p-2q}{3}v_4\\ y=\begin{pmatrix}2\frac{p+q}{3}+4^n\frac{p-2q}{3}\\ \frac{p+q}{3} - 4^n\frac{p-2q}{3} \end{pmatrix} \end{align}$$

Así que usted necesite $$3q=(4^n+2)p+2(1-4^n)q\\3p=(1-4^n)p +(1+2\cdot4^n)q$$

Resolver. Llego $$\frac{p}{q}=\frac{1+2\cdot 4^n}{4^n+2}=2-\frac{3}{4^n+2}$$

Desde $4^n+2$ es divisible por $3$, podemos dejar que la $q=\frac{4^n+2}{3}$ y deje $p=2q-1$.

No estoy seguro acerca de todo mi aritmética de los pasos, así que vamos a tratar algunos ejemplos.

Da el resultado correcto para $n=1$, $q=2,p=3$. También funciona para $n=0$ - $q=1,p=1$.

Para $n=2$, $q=6,p=11$. A continuación, $$(11,6)\to (5,12)\to (10,7)\to (3,14)\to (6,11).$$

Parece que funciona.

Si cada persona en cada turno de dar $\alpha$ multiplicado por el número que la otra persona tiene el mismo enfoque funciona, con los autovalores $1,(\alpha+1)^2$, y el valor:

$$\frac{p}{q}=\frac{(\alpha+1)^{2n+1}+1}{(\alpha+1)^{2n}+\alpha+1}$$

Así, por ejemplo, con $\alpha=2$$n=3$$\frac{p}{q}=\frac{3^7+1}{3^6+3}=\frac{547}{183}$.

$$(547,183) \(181,549) \(543,187) \(169,561) \(507,223) \(61,669) \(183,547) $$

Al $\alpha=\frac{1}{2}$ $n=2$ obtener $(p,q)=(55,42)$ y el: $$(55,42) \(34,63) \(51,46) \(28,69) \(42,55) $$

Curiosamente, si usted juega el juego con tres personas de rotación, y cada jugador en su turno de dobles, tanto de los demás jugadores de dinero, a continuación, obtener de $(p,q,r)$ $(r,q,p)$ $3n$turnos, tendría que empezar con algún múltiplo de $(4\cdot8^n+1,2\cdot 8^n + 2,8^n+4)$. Por ejemplo, la secuencia de al $n=2$ es:

$$\begin{align}(257,130,68) &\to(59,260,136) &\to(118,65,272) &\to(236,130,89)\\ &\to(17,260,178) &\to(34,65,356) &\to(68,130,257)\\ \end{align} $$

El que parece funcionar con $k$ jugadores y $n$ turnos. Si $(p_1,p_2,\dots,p_k)$ son las posiciones de partida, de modo que después de $kn$ turnos, llegar a la posición$(p_k,p_{k-1},\dots,p_1)$, entonces:

$$p_i=2^{(n+1)k-i} + 2^{i-1}$$

es una solución general. No tengo explicación para eso...

Answer 3

Un método podría ser explorar en busca de una solución.

Por ejemplo, es fácil encontrar que para $n=1$ la solución es $\frac{p}{q}=\frac{3}{2}$ y no es difícil encontrar que para $n=2$ la solución es $\frac{p}{q}=\frac{11}{6}$. Así se puede deducir que, en general,$p=q+1$. Esto conduce muy rápidamente a la búsqueda de $n=3$ que $\frac{p}{q}=\frac{43}{22}$, con un patrón que parece:

43  22
21  44
42  23
19  46
38  27
11  54
22  43

Ahora considere los cambios después de cada par de Ahmed en tener $43, 42, 38, 22$, que son la reducción de $1,4,16$, con aspecto de poderes de $4$, y como una serie geométrica se suman a $p-q = (4^n-1)/3$ que se pueden combinar con $p=2q-1$ dar $q=(4^n+2)/3$$p=(2\times4^n+1)/3$, por lo que una proporción de $\dfrac{p}{q}=\dfrac{2\times4^n+1}{4^n+2}$ a responder a la pregunta.

Usted todavía necesita para demostrar que esto funciona. Pero la única parte difícil es demostrar que si después de $k$ pares de swaps de Ahmed ha $\dfrac{2\times4^n+1}{3} - \dfrac{4^k-1}{3}$ y Beth ha $\dfrac{4^n+2}{3} + \dfrac{4^k-1}{3}$, después de que el siguiente intercambio de Ahmed ha $\dfrac{4^n-1}{3} - 2\times \dfrac{4^k-1}{3}$ y después de la siguiente swap $\dfrac{2\times4^n-1}{3} - 4\times \dfrac{4^k-1}{3} = \dfrac{2\times4^n+1}{3} - \dfrac{4^{k+1}-1}{3}$, y así Beth tiene el resto, es decir,$\dfrac{4^n+2}{3} + \dfrac{4^{k+1}-1}{3}$, y la prueba seguirá por inducción. Como un punto más, Ahmed y Beth canicas puede ser multiplicada por un común entero sin afectar las proporciones.