Ola Bernardo e demais colegas
desta lista ... OBM-L,
Parabens pela sua mensagem ! Muito boa ! Ela se coaduna perfeitamente
ao espirito original desta lista !
Quanto ao "B", eu usei "B^2" porque assim era no problema original :
eu apenas traduzi para uma linguagem elementar, adeguada para ser
publicada aqui. O fato de nunca haver encontro significa para mim que
as orbitas nunca atingem um ponto de equilibrio, mas isso e outra
historia ...
O caminho que eu segui foi diferente. Apos caracterizar - como voce
fez - os intervalos In eu passei a caracterizacao do formato das
moedas cuspidas. Descobri que a N-esima moeda cuspida tem o formato :
Mn = (Fn)^2 - 2*Fn*Fn+1*X + ((Fn+1)^2)*(X^2)
onde Fn e o N-esimo termo da sequencia de Fibonacci. Daqui,
considerando que nesta sequencia (F1)^2 + (F2)^2 + ... + (Fn)^2 =
(Fn)*(Fn+1), a soma M1 + ... + Mn fica calculavel
e passivel de ser comparda com os valores presentes em In.
Vamos trabalhar para subir o nivel das discussoes.
Um abracao pra voce, tambem.
PSR, 42904091432
2009/4/29 Bernardo Freitas Paulo da Costa <bernardo...@gmail.com>:
> 2009/4/28 Paulo Santa Rita <paulo.santar...@gmail.com>:
>> 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
> =========================================================================
>
=========================================================================
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================
