Ola carissimo Luis Lopes e demais
colegas desta lista ... OBM-L,
( escreverei sem acentos )
Vamos IMAGINAR que os possiveis totais acumulados apos o N-esimo lancamento
da moeda estao dispostos ao longo de uma coluna, numerados de cima para baixo,
de 1 ate 2^N. Represetaremos por Tn o total de resultados possiveis distintos;
por Tni um particular resultado.
Exemplos
1) coluna 1 : 0,1
T1=2, T11=0 e T12=1
2) coluna 2 : 0,1,0.5,2
T2=4, T21=0, T22=1, T23=0.5 e T24=2
3) coluna 3 : 0, 1, 0.5, 2, 0.25, 1.5, 1, 3
T3=7, T31=0,T32=1, T33=0.5, T34=2, T35=0.25, T36=1.5, T37=1 e T38=3
Note que estou convencionando que os Tni com i impar promanam da fortuna
acumulada anteriormente pela multiplicacao por 0.5; com i par, pela adicao
de 1.
Agora vou introduzir uma representacao para os possiveis totais acumulados
Representarei por "A" o ato de multiplicar por 0.5; O ato de somar 1 sera
representado por "B". Os exemplos anteriores ficarao assim :
Exemplos
1) coluna 1 : A,B
T1=2, T11=A e T12=B
2) coluna 2 : AA,AB,BA,BB
T2=4, T21=AA, T22=AB, T23=BA e T24=BB
3) coluna 3 : AAA,AAB,ABA,ABB,BAA,BAB,BBA,BBB
T3=7, T31=AAA,T32=AAB,...,T37=BBA e T38=BBB
E facilver que a N-esima coluna sera representada por TODOS os arranjos de
comprimento N que podemos fazer dispondo de 2 letras ... E igualmente
claro que metade dos arranjos da N-esima coluna iniciam com "A", a outra metade
iniciando com "B". Ora, e obvio que podemos descartar os A's iniciais
dos arranjos
iniciados com A, pois eles equivalem a multiplicar por 0.5 o valor inicial zero.
Exemplo
AABB = 0*(0.5)*(0.5) + 1 + 1 = 1 + 1 = BB
ABABB=(((0*(0.5)+1)*(0.5))+1)+1=1*(0.5)+1+1=BABB
Assim, se tomarmos todos os arranjos da coluna N iniciados com A ( a
metade superior
da coluna N ) e descartarmos o primeiro A de cada um, restara,
claramente, TODOS OS
ARRANJOS DA COLUNA n-1, cujo numero de elementos distintos ja
convencionamos designar
por Tn-1. portanto :
Tn = Tn-1 + VALORES INEDITOS DA METADE INFERIOR DA COLUNA N (1)
Os valores ineditos surgem na metade inferior da coluna N, sao todos
eles arranjos
iniciados com a letra B. Todavia, e claro que nem todo arranjo
iniciado com a letra
B representa um valor inetido. Por exemplo, na coluna 3 temos que T37=BBA=1 e um
valor que nao e inedito.
Vamos portanto introduzir um novo conceito. Para ver a motivacao para
ele considere
os exemplos abaixo :
Exemplos
1) BBA = (1+1)*(0.5)=2*(0.5)=1 => BBA=B
2) BBBA=(1+1+1)*(0.5) = 1*(0.5)+1 = 1.5 => BBBA=BAB
3) BABBA=((0.5)+2)*(0.5)=(0.25)+1 = 1.25 => BABBA=BAAB
Pensando um pouco sobre os exemplos acima e facil perceber que quando A ESQUERDA
DE ALGUM "A" HA DOIS OU MAIS "B" CONSECUTIVOS, o valor numerico
representado pelo
arranjo pode ser representado por um arranjo de comprimento menor. Isso motiva a
seguinte definicao :
DEFINICAO : Um arranjo e dito ser IRREDUTIVEL se a esquerda de qualquer de suas
letras A nao existe duas ou mais letras B consecutivas. Um arranjo que nao e
IRREDUTIVEL e dito ser REDUTIVEL
Os arranjos redutiveis, cujo valor numerico intrinseco pode ser
representado por um
arranjo de comprimento menor, nao nos interessam, pois, pela relacao
(1) deduzida acima,
eles ja foram computados. Interessa-nos os arranjos irredutiveis, pois
sao deles
que promanam valores ineditos. Ora, os arranjos irredutiveis iniciam sempre com
um unico B e a esqueda de qualquer A que porventura nele exista ha, no
maximo, um B.
Sao portanto exemplos de arranjos irretudiveis :
Exemplos :
1) BABABA, BAAAAAAA, BABABBBBBBBBB, BAAABAABA, BBBBBB
Os arranjos irredutiveis permitem uma representacao mista interessante
: todos as
letras B que estao a direita da letra A mais a direita representam um
numero natural,
nomeadamente igual ao numero de letras B que lá existam; a parte
restante do arranjo
(a esquerda da letra A mais a direita, inclusive esta letra A )
representa um numero
binario decimal.
Exemplos
1) BABABBB = BABA + BBB = BABA + 3 = ((1*(0.5)+1)*0.5) + 3 = 3 + [0.11],
onde a parte entre colchetes e um numero real em sua representacao na base dois.
2) BAABA = (1*((0.5)^2)+1)*(0.5) = [0.101]
Assim, toda arranjo irredutivel R pode ser colocado na forma R = I +
[D], onde "I" e a
PARTE INTEIRA e "D" a PARTE DECIMAL - em base 2- da representacao
mista. Considerando
esta representacao mista, fica facil ver que :
LEMA 1 - Todo arranjo irredutivel representa um valor inedito, vale
dizer, um valor que
nao surgiu em qualquer das colunas anteriores
LEMA 2 - Dois arranjos irredutiveis distintos de mesmo comprimento
representam valores
distintos
Os fenomenos 1) e 2) acima nos permitem melhorar a relacao (1)
deduzida acima, colocando-a
como :
Tn = Tn-1 + TOTAL DE ARRANJOS IRREDUTIVEIS da coluna N (2)
Vejam que agora este despretencioso problema nos conduzia a
consideracao de um belo
problema de Analise Combinatoria, nomeadamente o calculo do numero de
arranjos irredutiveis
de comprimento N :
PROBLEMA : "Usando duas letras, quantos arranjos distintos - de
comprimento N - podemos
fazer de maneira que a esquerda de qualquer ocorrencia de uma das
letras nao exista duas
ou mais ocorencias consecutivas da outra letra ?"
Vou, a principio, considerar um caso particular para que o meu
raciocinio fique claro. Vamos
calcular o total de arranjos irredutiveis de comprimento 8.
O primeiro grupo arranjos irredutiveis de comprimento 8 serao aqueles
que dispoe de uma
unica letra B. Esse grupo, qualquer que seja o comprimento N, sempre
tera um unico exemplar,
a saber : BAAAAAAA. Logo
GRUPO 1 ( aqueles com 1 B ) -> um exemplar
O segundo grupo sera formado por aqueles arranjos irredutiveis que
dispoe de duas letras
B. Vamos dividir este grupo em 2 sub-grupos.
GRUPO 2, SUBGRUPO 1 ( parte inteira igual a 1 )
Um unico exemplar : BAAAAAAB
GRUPO 2, SUBGRUPO 2 ( parte inteira igual a 0 )
exemplos : BABAAAAA, BAABAAAA.
Para calcular o total de exemplares deste grupo basta ver que fixamos
no inicio as letras
BA (pois os arranjos sao irredutiveis ) e a seguir permutamos 1 BA,
tratando-o como se
fosse uma letra nova, digamos X (X=BA) com 4 letras A's. Isso vai dar : 5!/4!
O terceiro grupo sera formado por aqueles arranjos irredutiveis que
dispoe de tres letras
B. Vamos dividir este grupo em 3 sub-grupos.
GRUPO 3, SUBGRUPO 1 ( parte inteira igual a 2)
um unico exemplar : BAAAAABB
GRUPO 3, SUBGRUPO 2 ( parte inteira igual a 1 )
exemplos : BABAAAAB, BAABAAAB
Para calcular o total de exemplares deste grupo basta ver que fixamos
no inicio as letras
BA (pois os arranjos sao irredutiveis ), no fim a letra B e a seguir
permutamos 1 BA,
tratando-o como se fosse uma letra nova, digamos X (X=BA) com 3 letras
A's. Isso vai nos dar
o seguinte : 4!/3!
GRUPO 3, SUBGRUPO 3 ( parte inteira igual a 0 )
exemplo : BABABAAA
Para calcular o total de exemplares deste grupo basta ver que fixamos
no inicio as letras
BA (pois os arranjos sao irredutiveis ) e a seguir permutamos 2 BA's,
tratando-os como se
fossem uma letra nova, digamos X (X=BA) com 2 letras A's. Isso vai nos dar
o seguinte : 4!/(2!*2!)
O quarto grupo sera formado por queles arranjos irredutiveis que
dispoe de quatro letras
B. Vamos dividir este grupo em 4 sub-grupos,
GRUPO 4, SUBGRUPO 1 ( parte inteira igual a 3 )
um unico exemplar : BAAAABBB
GRUPO 4, SUBGRUPO 2 ( parte inteira igual a 2 )
Para calcular o total de exemplares deste grupo basta ver que fixamos
no inicio as letras
BA (pois os arranjos sao irredutiveis ), no final as letras BB e a
seguir permutamos 1 BA,
tratando-os como se fossem uma letra nova, digamos X (X=BA) com 3
letras A's. Isso vai nos dar
o seguinte : 3!/2!
GRUPO 4, SUBGRUPO 3 ( parte inteira igual a 1)
Para calcular o total de exemplares deste grupo basta ver que fixamos
no inicio as letras
BA (pois os arranjos sao irredutiveis ), no final a letra B e a seguir
permutamos 2 BA's,
tratando-os como se fossem uma letra nova, digamos X (X=BA) com 2
letras A's. Isso vai nos dar
o seguinte : 3!/2!
GRUPO 4, SUBGRUPO 4 (parte inteira igual a 0)
Obviamente so ha um exemplar : BABABABA
GRUPO 5, SUBGRUPO 1 (parte inteira igual a 4): BAAABBBB
GRUPO 5, SUBGRUPO 2 (parte inteira igual a 3): BABAABBB, BAABABBB
GRUPO 5, SUBGRUPO 3 (parte inteira igual a 2): BABABABB
GRUPO 5, SUBGRUPO 4 (parte inteira igual a 1): nao ha exemplar
GRUPO 5, SUBGRUPO 5 (parte inteira igual a 0): nao ha exemplar
GRUPO 6, SUBGRUPO 1 (parte inteira igual a 5) : BAABBBBB
GRUPO 6, SUBGRUPO 2 (parte inteira igual a 4) : BABABBBB
Nao ha mais possibilidade no grupo 6
GRUPO 7, SUBGRUPO 1 (parte inteira igual a 6) : BABBBBBB
Nao ha mais possibilidades no grupo 7
GRUPO 8, SUBGRUPO 1 (parte inteira igual a 7) : BBBBBBBB
Nao ha mais possibilidades no grupo 8
Representando por Bi(N,P) o numero binomial de numerador N e
denominador P, vale dizer,
o numero natural N!/(P!*(N-P)!) e dispondo os resultados acima do
grupo 8 para cima,
teremos a seguinte disposicao :
GRUPO 8 : 1
GRUPO 7 : Bi(0,0)
GRUPO 6 : Bi(1,0) + Bi(1,1)
GRUPO 5 : Bi(2,0) + Bi(2,1) + Bi(2,2)
GRUPO 4 : Bi(3,0) + Bi(3,1) + Bi(3,2) + Bi(3,3)
GRUPO 3 : Bi(4,0) + Bi(4,1) + Bi(4,2)
GRUPO 2 : Bi(5,0) + Bi(5,1)
GRUPO 1 : Bi(6,0)
Fiat Luz !
Representarei por Fi o i-esimo termo da sequencia de Fibonaci. Somando
segundo as
diagonais, temos :
Bi(0,0) = 1 = F1
Bi(1,0) = 1 = F2
Bi(2,0) + Bi(1,2) = 2 = F3
Bi(3,0) + Bi(2,1) = 3 = F4
Bi(4,0) + Bi(3,1) + Bi(2,2) = 5 = F5
Bi(5,0) + Bi(4,1) + Bi(3,2) = 8 = F6
Bi(6,0) + Bi(5,1) + Bi(4,2) + Bi(3,3) = 13 = F7
F1 + F2 + F3 + F4 + F5 + F6 + F7 = F9 - 1
Somando o GRUPO 8, temos : 1 + F1 + F2 + F3 + F4 + F5 + F6 + F7 = F9
Ou seja :
TOTAL DE ARRANJOS IRREDUTIVEIS DE COMPRIMENTO 8 = NONO NUMERO DA
SEQUENCIA DE FIBONACI
Este resultado de forma alguma e incidental. Vejamos :
ARRANJOS IRREDUTIVEIS DE COMPRIMENTO N
GRUPO N : 1 ( BBB...B, A letra B repetida N vezes )
GRUPO N-1,SUBRUPO 1 (parte inteira igual a N-2) : BABBB...B
Nao ha mais possibilidades no grupo N-1
GRUPO N-2,SUBGRUPO 1 (parte inteira igual a N-3) : BAABBB..B
GRUPO N-2, SUBGRUPO 2 (parte inteira igual a N-4) : BABABBB...B
Nao ha mais possibilidades no grupo N-2
GRUPO N-3,SUBGRUPO 1 (parte inteira igual a N-4) : BAAABBB...B
GRUPO N-3,SUBGRUPO 2 (parte inteira igual a N-5) : BABAABBB...B, BAABABBB...B
GRUPO N-3,SUBGRUPO 3 (parte inteira igual a N-6) : BABABABBB...B
Nao ha mais possibilidades no grupo N-2
...
GRUPO 3, SUBGRUPO 1 (parte inteira igual a 2) :
um unico exemplar : BAAA...AAAABB
GRUPO 3, SUBGRUPO 2 (parte inteira igual a 1)
(N-4)!/(N-5)!
GRUPO 3, SUBGRUPO 3 (parte inteira igual a 0)
(N-4)!/(2!*(N-6)!)
GRUPO 2, SUBGRUPO 1 (parte inteira igual a 1) :
um unico exemplar : BAAA...AAAB
GRUPO 2,SUBGRUPO 2 (parte inteira igual a 0 ) :
(N-3)!/(N-4)!
GRUPO 1, SUBGRUPO 1 :
um unico exemplar BAAA...AAAA
Dispondo como no exemplo :
GRUPO N : 1
GRUPO N-1 : Bi(0,0)
GRUPO N-2 : Bi(1,0) + Bi(1,1)
GRUPO N-3 : Bi(2,0) + Bi(2,1) + Bi(2,2)
...
GRUPO 3 : Bi(N-4,0) + Bi(N-4,1) + Bi(N-4,2)
GRUPO 2 : Bi(N-3,0) + Bi(N-3,1)
GRUPO 1 : Bi(N-2,0)
Se somarmos segundo as diagonais chegaremos ao resultado geral, vale dizer,
o TOTAL DE ARRANJOS IRREDUTIVEIS da coluna N e o (N+1)-esimo numero
de Fibonaci. Logo :
Tn = Tn-1 + Fn+1
Agora :
Tn = Tn-1 + Fn+1
Tn-1=Tn-2 + Fn
...
T3=T2 + F4
T2=T1 + F3
T1=2
somando tudo :
Tn = 2 + F3+F4 +F5 + ... + Fn+1
Tn = F1 + F2 + F3 + F4 + ... + Fn+1
Tn = Fn+3 - 1
Isto prova que a conjectura do amigo do carissimo Luis Lopes esta correta.
Bom, agora vou me permitir uma leve digressao ... O que foi bonito aqui foi
a descoberta da importancia dos ARRANJOS IRREDUTIVEIS. A caracterizacao
correta deles implicou num problema combinmatorio nao usual. Alem disso, saber
que para um comprimento N a quantidade deles e o (N+1)-esimo termo da sequencia
de fibonaci foi uma revelacao. Isso mostra que mesmo em problemas triviais e
elementares como este a beleza esta presente, como diria Goeth :
Trink, o auge, was die wimper haelt, von dem goldnen eueberfluss der welt !
Voltando ao problema. Em geral, ao longo de um caminho de solucao, surgem novas
maneiras de abordar o mesmo problema. Nao foi diferente aqui. Descobri uma outra
forma, mais elegante e poderosa e que permite uma generalizacao da questao.
Para ver isso, note que um particular valor Tni da N-esima coluna PODE
SER OLHADO
como o valor de um polinomio no ponto X=0.5.
Exemplo :
BABAABB = (1*(0.5) + 1)*((0.5)^2) + 2= (0.5)^3 + (0.5)^2 + 2
O polinomio P(X) = X^3 + X^2 + 2 e tal que P(0.5)=BABAABB
Eu vi isso enquanto escrevia esta solucao. Descobri o que caracteriza
os polinomio
pertencentes a uma particular coluna Tn
"Um polinomio a coeficientes positivos de grau P esta na coluna N se, e somente
se, o grau deste polinomio adicionado a soma dos coeficientes e menor que N"
Assim, para cana N temos uma familia de polinomios tais que os seus valores
numericos em X=0.5 fornece todos os Tni que estavamos considerando. Ha porem uma
vantagem : podemos considerar os casos em que o fator multiplicativo
nao se restringe
a 1/2 ( por exemplo, somar +1 ou multiplicar por 1/3 de acordo com o
resultado da
moeda ).
Fica a ideia para quem resolver explorar
Um Abraco a Todos
PSR, 32104092020
> Sauda,c~oes,
>
> Numa troca recente de mensagens com o
> prof. Rousseau ele me mandou o problema
> abaixo:
>
>
> I have a problem for you. This was communicated to me by
>
> Marko Riedel about a week ago, and I still haven’t found a solution.
>
> A coin-tossing game is played as follows. The player starts with a
>
> fortune of 0 and tosses a coin repeatedly. On each toss, his
>
> fortune is increased by 1 if he gets “heads” and is reduced by a
>
> factor of ½ if he gets a “tail.” After the nth toss, what is the number
>
> of possible values for his fortune? Thus
>
>
>
> Coin toss Set of fortunes and its cardinality
>
> 0 {0}, || = 1 = 2-1
>
> 1 {0,1}, ||=2 = 3-1
>
> 2 {0,1/2,1,2}, ||=4=5-1
>
> 3 {0,1/4,1/2,1,3/2,2,3},||=7=8-1
>
>
>
> It is conjectured that the number of possible fortunes is F_{n+3}-1.
>
> Let A_n denote the set of possible fortunes after n tosses, and
>
> let B_n = A_n + 1 and C_n = ½ A_n (using what I hope is obvious notation).
>
> Then A_{n+1} = B_n \cup C_n so |A_{n+1}| =|B_n|+|C_n|-|B_n \cap C_n|,
>
> and if the conjecture is true then F_{n+4}-1 = 2(F_{n+3}-1)-|B_n \cap C_n|,
>
> so |B_n \cap C_n| = 2(F_{n+3}-1)-F_{n+4} + 1 = F_{n+1}-1 .
>
> Thus it would suffice to exhibit a bijection from A_{n-1} to B_n \cap C_n.
>
>
>
> Example (n=1): |A_0|= 1 = |B_2 \cap C_2| (I hope the indices are OK;
>
> I am writing this without the benefit of any source.)
>
>
>
> Eu acho que ele quis dizer
>
> to exhibit a bijection from A_{n-2} to B_n \cap C_n.
>
> Alguém sabe como fazer? A conjectura é verdadeira?
>
>
>
> []'s
>
> Luís
=========================================================================
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================
