2009/4/28 Paulo Santa Rita <[email protected]>:
> Ola Bernardo e demais
> colegas desta lista ... OBM-L,
> ( escreverei sem acentos)
>
> Voce gostou do problema ? Que bom ! Fico contente por isso. Vou ficar
> aguardando que voce publique aqui nesta nossa lista a sua solucao.
Bom, aí vai uma idéia do problema. Está bem (beeeeeem) desorganizado,
mas eu acho que é a melhor coisa a fazer para mostrar como a gente
pode pensar no problema :)
Comece vendo que, para a máquina te devolver alguma coisa, você tem
que apostar suficientemente alto. Afinal de contas, se você der só
0.1, a máquina calcula B = 0.9 > X, e paf, você perdeu. Resultado,
aposte pelo menos 0.5 + um pouquinho (repare que, da forma como o
Paulo escreveu, dar 0.5 exatamente faz B = 0.5 que não é estritamente
menor do que X = 0.5).
O Paulo ajudou bastante escrevendo o algoritmo pra nós todos de forma
extremamente clara, o que permite montar uma recorrência :
a_{n+1} = x_n
x_{n+1} = a_n - x_n
e a coisa continua se b_n = a_n - x_n < x_n, ou seja, a_n < 2 * x_n
(repare que aqui temos de novo o primeiro resultado do 0.5 !)
Bom, recorrências de segunda ordem cheiram sempre a Fibonacci,
principalmente quando os coeficientes são sempre 1 ou -1. Bom, daí eu
montei a matriz de mudança de índices :
0 1
1 -1
e calculei algumas potências:
1 -1
-1 2
-1 2
2 -3
2 -3
-3 5
Bom, aqui estava claro que a solução era uma sequência de Fibonacci,
com sinais trocados. Um jeito de provar é fazer por indução, mas um
modo muito mais legal é ver que essa sequência em questão também
satisfaz uma recorrência de segunda ordem (multiplicar por um (-1)^n
só muda o sinal das raízes !) e portanto, se duas recorrências de 2a
ordem coincidem em dois termos, elas coincidem *sempre*. Ou seja,
provamos sem precisar fazer contas. Legal. Os coeficientes da matriz
de passagem para n termos adiante é, portanto :
G_{n-1} G_n
G_n G_{n+1}
onde G_n = -(-1)^n F_n, F_n a sequência de Fibonnaci clássica F_0 = 0,
F_1 = 1, F_2 = 1, F_3 = 2 e assim por diante, e a gente tem (por
exemplo, pra verificar o (-1)^n) G_3 = 2 = F_3, portanto coincide para
n ímpar, por isso o -(-1)^n.
> Esse problema surgiu como uma questao secundaria na abordagem de um
> tema bastante distante do tipo habitual de problemas tratados aqui. A
> roupagem original, formal, era muito sisuda. Foi entao que eu lhe dei
> esta apresentacao contextualizada em uma maquina de apostas.
>
> Vou falar um pouquinho sobre o problema :
>
> Seja 1, 1, 2, 3, 5, ..., Fn, ... a sequencia de Fibonacci. Para n par
> considere o intervalo In=(Fn/Fn+1, Fn-1/Fn). Se n for impar, considere
> In=(Fn-1/Fn,Fn/Fn+1). Usando as propriedades conhecidas desta
> sequencia, e facil ver que I1 C I2 C I3 C ... C In C In+1 C ..., onde
> "C" significa ESTA CONTIDO. Alem disso, e possivel provar o seguinte :
Daí, eu pensei nos intervalos encaixados do Paulo (mas "a posteriori")
e resolvendo a recorrência e impondo condição de continuar (a_n <
2x_n), a gente obtém
(a_n, x_n) = (-1)^n (F_{n-1} - F_n * x , F_{n+1} x - F_n)
logo
(-1)^n (F_{n-1} - F_n * x ) < (-1)^n 2(F_{n+1}x - F_n)
(-1)^n (F_{n-1} + 2 F_n) < (-1)^n (2F_{n+1} + F_n) x
e lembrando da definição dos fibonacci :
(-1)^n (F_n + F_{n+1}) < (-1)^n (F_{n+1} + F_{n+2}) x
(-1)^n F_{n+2} < (-1)^n F_{n+3}x
que dá, pra n=0, realmente 1 < 2x, e depois para n=1, 3x < 2. Ufa, deu
certo! E ainda mais, coincide com o que faz o Paulo :
para n par, é x > F_{n+2}/F_{n+3}, para n ímpar, é x < F_{n+2}/F_{n+3}
(basta subtrair dois e juntar as equações em pares)
> Se X esta em In entao a maquima cospe ao menos N moedas
Daí, eu fui pro computador :) Um programinha rapidinho em C me
permitiu implementar o algoritmo (não com precisão infinita, o que é
ainda melhor para ele terminar, já que vai cair cedo ou tarde fora do
intervalo que converge pra phi =( \sqrt(5) - 1 )/ 2 o número de ouro
!) e ver que nunca ia dar positivo... Porque para valores como 0.618
(que já é bem perto do valor certo) ele dá um prejuízo de -0.381940.
Calcular o retorno não é algo fácil (tem que saber em qual intervalo o
x está), mas eu esperava que, quando a máquina desse infinitas moedas
(ou seja, se a gente fornecesse uma de valor = phi) fosse um dos
possíveis casos de funcionar. De volta ao papel :
Como a_0 = 1, x_0 = phi, b_0 = 1 - phi = phi^2 (isso é muito bom pra
facilitar as contas) e daí a_1 = phi, x_1 = phi^2 e portanto b_1 = phi
* b_0 (já que a_1 e x_1 são respectivamente phi*a_0 e phi*x_0), logo
b_1 = phi^3, e daí dá pra ver que b_n = phi^{n+2}. Agora, é só somar a
PG :
soma phi^{n+2}^2 = phi^4 / (1 - phi^2) = phi^4 / phi (já que 1 = phi +
phi^2 !) = phi^3. Mas phi^3 < phi < 1, logo a máquina cospe menos do
que a gente botou, exceto que ela cospe infinitamente.
Daí a minha resposta querendo que a máquina cuspa "B" e não "B^2",
porque se ela cuspisse B, a soma da PG seria
soma phi^{n+2} = phi^2 / (1 - phi) = phi^2 / phi^2 = 1
(já que muda o termo inicial e a razão também !)
e neste caso, temos que a máquina devolve realmente mais grana.
Reparem agora que, estando no primeiro intervalo rejeitado (ou seja,
(0, 0.5]), perdemos exatamente X. No segundo intervalo rejeitado
([0.6666..., 1)) perdemos sempre 1 - 2(1-X). No terceiro intervalo
((0.5, 0.6]), saímos em igualdade. E no resto, ganhamos sempre, e
ganhamos mais para x = phi. (Note que, neste caso, é fácil ver que a
máquina nunca cospe mais do que 1 no total, já que ela começa com A =
1 e dá sempre uma parte "que falta" para completar 1, e continua com o
resto, e dá "uma outra parte que falta", e assim por diante).
Daí, a gente pode concluir que a máquina do Paulo (a que dá B^2) com
certeza devolve *menos* do que a máquina que dá B (já que B < 1).
Portanto, basta analisar os casos de X dentro de 0.6 a 2/3, que são os
casos em que a gente ganha com a máquina "boazinha". Mas para estes, a
primeira rodada a máquina dá em duas rodadas (1-x)^2 + (2x-1)^2 que é
no máximo 0.4^2 + 0.2^2 = 0.16 + 0.04 = 0.2, e ficamos no intervalo
limitado em 1-x, que é, na melhor das hipóteses, igual a 0.4. Aqui,
podemos fingir de novo que trocamos de máquina e estamos com a máquina
boazinha, que devolve no máximo o comprimento total do intervalo. Mas
como 0.2 + 0.4 < 0.6 < X (lembre, a gente apostou X no intervalo (0.6,
2/3), pra poder ganhar com a máquina malvada do B^2), nunca poderemos
ganhar.
> Assim, podemos obrigar a maquina a cuspir tantas moedas quanto
> quisermos, bastando tomar um intervalo In suficientemente fino. Isto
> significa que X vai ficando cada vez mais limitado e o numero de
> moedas cuspidas vai crescendo ...
>
> Um Abraco a Todos
> PSR,32804091458
Um abração, e meus parabéns pelo problema !
--
Bernardo Freitas Paulo da Costa
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================
