Re: [obm-l] Quanto Apostar ?
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 (beem) 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_nG_{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
Re: [obm-l] Quanto Apostar ?
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 (beem) 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
Re: [obm-l] Quanto Apostar ?
Bom, eu fiquei contente de adivinhar qual era a magica do problema, mas fiquei encucado com a soluçao... porque eu acho que a sua maquina ganha sempre se for B^2... mas perde se for B. Seria legal que ela devolvesse phi^2 / (1 - phi) = 1 phi ao todo, em vez de phi^4/(1 - phi^2) = phi^3 phi ... Mas muito bom o problema (e mais uma excelente ocasiao de provar que um programinha pode ajudar a estudar uma conjectura :)) 2009/4/28 Paulo Santa Rita paulo.santar...@gmail.com: Ola a todos ! IMAGINEM um pais no qual para todo real X, 0 X 1, cunham moedas de valor X. Neste pais ha uma maquina de apostas que opera recebendo, a principio, uma moeda de valor X (a aposta) , podendo devolver zero, uma ou diversas moedas, segundo o algoritmo : Passo 1) Faz A = 1 Passo 2) Calcula B = A - X Passo 3) Se B X, faz : * Entrega ao apostador (cospe) uma moeda valendo B^2 * Faz : A = X * Faz : X = B * Volta a executar o algoritmo a partir do passo 2 Senao ( Se B = X) , a maquina PARA. Para qual(is) valor(es) de X e vantajoso apostar ? Um Abraco a Todos ! PSR, 22704092032 = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html = -- 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 =
[obm-l] Quanto Apostar ?
Ola a todos ! IMAGINEM um pais no qual para todo real X, 0 X 1, cunham moedas de valor X. Neste pais ha uma maquina de apostas que opera recebendo, a principio, uma moeda de valor X (a aposta) , podendo devolver zero, uma ou diversas moedas, segundo o algoritmo : Passo 1) Faz A = 1 Passo 2) Calcula B = A - X Passo 3) Se B X, faz : * Entrega ao apostador (cospe) uma moeda valendo B^2 * Faz : A = X * Faz : X = B * Volta a executar o algoritmo a partir do passo 2 Senao ( Se B = X) , a maquina PARA. Para qual(is) valor(es) de X e vantajoso apostar ? Um Abraco a Todos ! PSR, 22704092032 = Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
