Игра

[wpoms.]

Ахмед и Бет имеют, соответственно, `p` и `q` шариков (`p > q`). Начиная с Ахмета, каждый во время своего хода дает другому столько шариков, сколько тот уже имеет. После `2n` таких передач шариков оказалось, что у Ахмета стало `q` шариков, а Бет, соответственно, их стало `p`. Выразите `p/q` в виде выражения, зависящего только от `n`.

@темы: Олимпиадные задачи

Comments

[Adjirranirr]

Сразу предположим, что игроки ходят по очереди и каждый сделанный ход был допустимым.
Пусть после `2k,\ k < n` передач у Ахмета стало `p(2k)`, а у Бет `q(2k)` шариков. Тогда, `p(0) = p,\ q(0) = q;\ p(2k) > q(2k)`, и
`p(2k + 1) = p(2k) - q(2k),\ q(2k + 1) = 2*q(2k)`
`p(2k + 2) = 2p(2k + 1) = 2*p(2k) - 2*q(2k),\ q(2k + 2) = q(2k + 1) - p(2k + 1) = 2*q(2k) - (p(2k) - q(2k)) = 3*q(2k) - p(2k)`. Обозначая `p(2k) = a(k),\ q(2k) = b(k)` получим
`a(k + 1) = 2*a(k) - 2*b(k),\ b(k + 1) = 3*b(k) - a(k)`, или `((a(k+1)), (b(k+1))) = ((2,-2),(-1,3)) ((a(k)),(b(k)))`. Отсюда, очевидно, `((a(k)),(b(k))) = A^k ((a(0)), (b(0)))`, где `A = ((2,-2),(-1,3))`.
Лемма. `A^k = ((\frac {2^(2k) + 2}{3}, 1 - \frac {2^(2k + 1) + 1} {3}),(1 -\frac {2^(2k) + 2}{3}, \frac {2^(2k + 1) + 1} {3}))`.
Доказательство.
`A^1 = A = ((2, -2),(-1,3)) = ((\frac {4 + 2}{3}, 1-\frac {8 + 1} {3}),(1-\frac {4 + 2}{3}, \frac {8 + 1} {3}))`.
Предположим, что `A^k = ((\frac {2^(2k) + 2}{3}, 1 - \frac {2^(2k + 1) + 1} {3}),(1 -\frac {2^(2k) + 2}{3}, \frac {2^(2k + 1) + 1} {3}))`. Тогда `A^{k + 1} = A^k * A = ((\frac {2^(2k) + 2}{3}, 1 - \frac {2^(2k + 1) + 1} {3}),(1 -\frac {2^(2k) + 2}{3}, \frac {2^(2k + 1) + 1} {3})) * ((2,-2),(-1,3)) =`
`= ((2/3 + 2/3 2^(2k) + 1/3 2^(2k + 1),2/3-2/3 2^(2k) -2^(2k + 1)),(1/3-2/3 2^(2k) - 1/3 2^(2k +1),1/3 +2/3 2^(2k) + 2^(2k + 1)) ) = ((1/3 2^(2k + 2) + 2/3, 2/3 - 1/3 2^(2k + 3)),(1/3 - 1/3 2^(2k + 2),1/3 2^(2k + 3) + 1/3))`.
По теореме об индукции, `A^k = ((\frac {2^(2k) + 2}{3}, 1 - \frac {2^(2k + 1) + 1} {3}),(1 -\frac {2^(2k) + 2}{3}, \frac {2^(2k + 1) + 1} {3}))`.

Таким образом, `a(k) = \frac {2^(2k) + 2}{3} p + (1 - \frac {2^(2k + 1) + 1}{3}) q,\ b(k) = (1 -\frac {2^(2k) + 2}{3}) p + \frac {2^(2k + 1) + 1} {3} q`. По условию, `a(n) = q,\ b(n) = p`, или `{(\frac {2^(2k) + 2}{3} p + (1 - \frac {2^(2k + 1) + 1}{3}) q = q),( (1 -\frac {2^(2k) + 2}{3}) p + \frac {2^(2k + 1) + 1} {3} q = p) :}`. Решая систему, получим `p = q * \frac {2^(2n + 1) + 1}{2^(2n) + 2}`, или `p/q = \frac {2^(2n + 1) + 1}{2^(2n) + 2}`.

[All_ex]

Adjirranirr, красиво...
Мда... бедные школьники-олимпиадники... ...