knikkers
Opgave - BrMO 2 2001 vraag 1
Ahmed en Beth hebben respectievelijk $p$ en $q$ knikkers, met $p>q$.
Startend met Ahmed, geeft elk op beurt evenveel knikkers aan de ander als hij of zij al bezit. Na $2n$ zo'n overdragingen zien we dat Ahmed $q$ knikkers heeft, en Beth $p$.
Vind $\frac pq$ in termen van $n$.
- login om te reageren
Oplossing
Zeg pipo, $2n$ is altijd even! :grin: Ik ging er toch vanuit dat je het over de pariteit van $n$ had... dan klopt de formule inderdaad.
Een algemene oplossing voor dit type problemen (hoewel eens je de formule hebt het natuurlijk korter kan met inductie): noteer het aantal knikkers bij Ahmed en Beth na $n$ stappen als $p_n$ en $q_n$ respectievelijk. We gaan van $(p_n,q_n)\to (p_n-q_n,2q_n)\to (2p_n-2q_n,3q_n-p_n)$, dus hebben we recursief dat $\left(\begin{smallmatrix} p_{n+1} \\ q_{n+1}\end{smallmatrix}\right) = \left(\begin{smallmatrix} 2 & -2 \\ -1 & 3 \end{smallmatrix}\right)\left(\begin{smallmatrix}p_n \\ q_n\end{smallmatrix}\right)$,
en het op te lossen stelsel is dus $\left(\begin{smallmatrix} q \\ p\end{smallmatrix}\right) = A^n \left(\begin{smallmatrix}p \\ q\end{smallmatrix}\right)$ of $\left(\begin{smallmatrix} p \\ q\end{smallmatrix}\right) =\left(\begin{smallmatrix} 0 & 1 \\ 1 & 0 \end{smallmatrix}\right)A^n=\left(\begin{smallmatrix} p \\ q\end{smallmatrix}\right) $, met $A=\left(\begin{smallmatrix} 2 & -2 \\ -1 & 3 \end{smallmatrix}\right)$. Of nog: de eigenvector vinden bij de eigenwaarde $1$ van de matrix $\left(\begin{smallmatrix} 0 & 1 \\ 1 & 0 \end{smallmatrix}\right)A^n$.
Via diagonalisatie vinden we dat die laatste matrix $\frac13\left(\begin{smallmatrix} 1-2^{2n} & 2^{2n+1}+1 \\ 2^{2n}+2 & 2-2^{2n+1} \end{smallmatrix}\right)$ is, met als eigenvector $\left(\begin{smallmatrix}2^{2n+1}+1\\2^{2n}+2 \end{smallmatrix} \right)$ bij $\lambda=1$. Dus na $2n$ stappen is $$\frac pq = \frac{2^{2n+1}+1}{2^{2n}+2}.$$
Zeg pipo, $2n$ is altijd even! :grin:
Haha! :grin:
Ik werk ook via recursie, maar dan wel zonder die lineaire algebra die gij erbij haalt :razz: Ik definieer $a_n$ als het aantal knikkers dat Ahmed na $2n$ stappen heeft en $b_n$ op analoge wijze voor Beth. Het is dan niet moeilijk in te zien dat $a_0 = p$, $b_0 = q$, $a_k+b_k = p+q$, $a_{k+1} = a_k-b_k+(a_k-b_k) = 2(a_k-b_k)$ en $b_{k+1} = b_k+b_k-(a_k-b_k) = 3b_k-a_k$. Bijgevolg zal dan $b_{k+1} = 3b_k-(p+q-b_k) = 4b_k-(p+q)$. Definieer nu dus de rij $c_n= \frac{b_n}{4^n(p+q)}$. Er is gegeven dat $c_n = c_{n-1}-4^{-n}$, dus $$c_n = c_0 - \sum_{i=1}^n 4^{-i} = \frac{q}{p+q} - \frac{1}{4}\cdot\frac{1-4^{-n}}{1-4^{-1}} = \frac{q}{p+q} - \frac{4^n-1}{3\cdot 4^n}$$Bijgevolg is $b_n = 4^n(p+q)c_n = q4^n - \frac{1}{3}(p+q)(4^n-1)$.
Nu is er gegeven dat $b_n = p$, voor een zekere $n$, dus moet $3p = 3b_n = 3q4^n - (p+q)(4^n-1) = (2\cdot 4^n +1)q - (4^n-1)p$, i.e. $(4^n+2)p = (2^{2n+1}+1)q$, i.e. $\frac{p}{q} = \frac{2^{2n+1}+1}{2^{2n}+2}$.