[obm-l] Numero esperado de movimentos?
Caros colegas, Uma sequencia (bloco) de 5 digitos binarios, por exemplo, (1 0 1 0 1), e gerada aleatoriamente com iqual probabilidade (50%) de se gerar 1 ou 0. Sequencias que contem um unico digito igual a 1 ou exatamente cinco digitos iguais a 1 sao dominantes e tem valor 1. Todos os outros casos valem 0. Isto e, os 6 casos de valor 1 sao: (1 0 0 0 0) = 1, (0 1 0 0 0) = 1, (0 0 1 0 0) = 1, (0 0 0 1 0) = 1, (0 0 0 0 1) = 1 e (1 1 1 1 1) = 1. Todos os outros casos valem ZERO. Depois de gerada a sequencia, um dos cinco digitos e escolhido ao acaso e seu valor trocado (se for 1 passa a ser 0 ou vice-versa). Todos os 5 digitos ou posicoes tem a mesma probabilidade de serem escolhidos para troca. O processo e repetido ate que uma sequencia de valor 1 seja encontrada (um dos 6 casos acima seja gerado). Se a primeira sequencia gerada tiver valor 1 nenhuma troca e feita e o processo acaba, pois, uma sequencia de valor 1 foi gerada. Suponha agora que tenhamos um numero inteiro positivo de N sequencias iguais a esta compondo uma sequencia maior com 5*N digitos binarios gerada aleatoriamente. Cada um dos 5*N digitos sera escolhido com igual probabilidade e seu valor trocado como no processo anterior. O valor desta sequencia completa e baseada no valor de cada um dos blocos de 5 digitos contidos nela. Os blocos sao considerados da esquerda para a direita (de 5 em 5 digitos). Desta forma o maior valor possivel para a sequencia completa com 5*N digitos sera N quando todos os N blocos contidos nela valerem 1. Quando um bloco dentro da sequencia 5*N vale 1 ou passa a valer 1 depois de uma troca, mudancas neste bloco nao sao mais aceitas, mas, posicoes dentro deste(s) bloco(s) continua(m) podendo ser selecionadas mas sao trocas perdidos. A pergunta e: Qual e o numero esperado de trocas para se obter todos os blocos iguais a 1 dentro da sequencia maior com 5*N digitos. Ou seja qual o numero esperado de movimentos (trocas) para se obter o valor N para a sequencia maior? ESC Yahoo! Messenger - Communicate instantly...Ping your friends today! Download Messenger Now http://uk.messenger.yahoo.com/download/index.html = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
RES: [obm-l] probleminha de geometria - escolher resposta
É imediato que a = 2p - b - c (I) c^2 = a^2 - b^2 + 2*b*sqrt(c^2 - h^2) Bem, preciso resolver essa equacao em c [...] (vou reproduzir apenas as solucoes com raizes positivas): c = sqrt(a^2 + b^2 - 2*sqrt((a^2)*(b^2) - (b^2)*(h^2))) ou c = sqrt(a^2 + b^2 + 2*sqrt((a^2)*(b^2) - (b^2)*(h^2))) E agora, qual eu escolho!? Hmmm... Nenhuma delas. Note que, do jeito que voce fez, a depende de c, entao nenhuma dah uma resposta explicita para c, voce ia ter que continuar resolvendo Eu substituiria (I) lah em cima logo: c^2=(2p-b-c)^2-b^2+2b.sqrt(c^2-h^2) 0=-4pb-4pc+2bc+4p^2+2b.sqrt(c^2-h^2) b.sqrt(c^2-h^2)=(2p-b).c-2p.(p-b) b^2.(c^2-h^2)=(2p-b)^2.c^2-4p.(b-p).(2p-b).c+p^2.(p-b)^2 4p.(p-b).c^2-4p.(p-b).(2p-b).c+[p^2.(p-b)^2+h^2]=0 Ou seja, queremos as raizes da equação t^2-(2p-b).t+[p(p-b)+h^2/p(p-b)]/4=0 Espero que esta contalhada esteja certa... Esta eh uma quadratica feia em c com duas raizes, cuja soma eh 2p-b=a+c. Isto eh, as duas raizes serao a e c (até porque o problema é simétrico com relação a *a* e *c*, qualquer equação que você enontrar para um servirá para o outro). Abraço, Ralph winmail.dat
[obm-l] x^x
Oi Pessoal, qual é a derivada de f(x)=x^x? []s
[obm-l] limites superiores e inferiores de sequencias
Boa tarde a todos. Diversas vezes eu vi a seguinte afirmacao, mas nunca vi a demosnstracao: Se (a_n) eh uma seqüência de números reais não negativos, entao lim inf (a(n+1)/a(n)) = lim inf (a(n)^(1/n) = lim sup (a(n)^(1/n) = lim sup (a(n+1)//(a(n)). (A desigualdade do meio vale, eh claro, para toda seqüência de números reais) Vou apresentar minha propria prova. esperando que esteja certa. Inicialmente, vamosprovar que lim sup (a(n)^(1/n) = lim sup (a(n+1)/a(n). Seja L = = lim sup (a(n+1)/a(n). Para todo pL, existe entao um natural k (dependente de p) tal que a(n+1)/a(n) p para todo n=k. Temos entao que a(k+1) p * a(k); a(k+2) p* a(k+1) p^2 * a(k)De modo geral, temos a(n) p^(n-k) * a(k) = (p^n)/(p^k) * a(k) = M *p^n, para n=k+1 e sendo M= a(k)/p^k. .. Logo, a(n)^(1/n) p* M^(1/n), também para n= k+1. Com possível exceção de um numero finito de termos (os k primeiros), esta desigualdade vale para todos os termos das duas seqüências que aparecem na ultima desigualdade. Logo, lim sup a(n)^(1/n) = lim sup p* M^(1/n). Como M eh independente de n, a seqüência do membro direito desta ultima desigualdade converge para p, pois lim M^(1/n) = 1. Logo lim sup (p * M^(1/n)). = lim (p * M)^(1/n)) = p, do que concluímos que lim sup (a(n)^(1/n) = p. Como esta desigualdade vale para todo pL, temos entao, necessariamente, que lim sup (a(n)^(1/n) = L lim sup (a(n+1)/a(n). Através de um raciocínio análogo, provamos que lim inf (a(n+1)/a(n)) = lim inf (a(n)^(1/n). Como corolário, temos que (a(n+1)/a(n) for convergente, entao lim (a(n+1)/a(n) = lim (a(n)^(1/n). Estas conclusões são muito usadas nos testes da raiz e da razão para convergência absoluta de series O teste da razão eh mais conclusivo, pois Soma (|a(n)|) pode convergir e, entretanto, termos lim sup (|a(n+1)|/|a(n)| ) 1. AbraçosArtur OPEN Internet @ Primeiro provedor do DF com anti-vírus no servidor de e-mails @ = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] x^x
Temos que f(x) = x^x = e^(x*Ln(x)), para x0. Logo (regra da cadeia) f´(x) =e^(x*Ln(x)) * ( x*Ln(x)´ = x^x *(x/x + 1* Ln(x)) = (x^x *(1+ Ln(x)), para x0. Artur Oi Pessoal, qual é a derivada de f(x)=x^x? []s OPEN Internet @ Primeiro provedor do DF com anti-vírus no servidor de e-mails @ = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] x^x
Claro! ehheeh... barbada... depois que se descobre...:-) Brigadão Arthur! - Original Message - From: Artur Costa Steiner [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Friday, January 23, 2004 12:25 PM Subject: Re: [obm-l] x^x Temos que f(x) = x^x = e^(x*Ln(x)), para x0. Logo (regra da cadeia) f´(x) =e^(x*Ln(x)) * ( x*Ln(x)´ = x^x *(x/x + 1* Ln(x)) = (x^x *(1+ Ln(x)), para x0. Artur Oi Pessoal, qual é a derivada de f(x)=x^x? []s OPEN Internet @ Primeiro provedor do DF com anti-vírus no servidor de e-mails @ = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html = = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: RES: [obm-l] probleminha de geometria - escolher resposta
Ralph Teixeira wrote: É imediato que a = 2p - b - c (I) c^2 = a^2 - b^2 + 2*b*sqrt(c^2 - h^2) Bem, preciso resolver essa equacao em c [...] (vou reproduzir apenas as solucoes com raizes positivas): c = sqrt(a^2 + b^2 - 2*sqrt((a^2)*(b^2) - (b^2)*(h^2))) ou c = sqrt(a^2 + b^2 + 2*sqrt((a^2)*(b^2) - (b^2)*(h^2))) E agora, qual eu escolho!? Hmmm... Nenhuma delas. Note que, do jeito que voce fez, a depende de c, entao nenhuma dah uma resposta explicita para c, voce ia ter que continuar resolvendo Eu substituiria (I) lah em cima logo: Como a depende de c Ralph? Ora, a = 2p - b - c (I) e c = sqrt(a^2 + b^2 - 2*sqrt((a^2)*(b^2) - (b^2)*(h^2))) (II) , por exemplo. Se eu subistituir II em I, a nao vai depender de c, o problema é qual expressao de c escolher. Deixa eu ver o que voce fez. c^2=(2p-b-c)^2-b^2+2b.sqrt(c^2-h^2) 0=-4pb-4pc+2bc+4p^2+2b.sqrt(c^2-h^2) ai vc dividiu por 2, fatorou e b.sqrt(c^2-h^2)=(2p-b).c-2p.(p-b) elevou os dois lados ao quadrado (mas c-2p nao é negativo?, tem problema?) b^2.(c^2-h^2)=(2p-b)^2.c^2-4p.(b-p).(2p-b).c+p^2.(p-b)^2 4p.(p-b).c^2-4p.(p-b).(2p-b).c+[p^2.(p-b)^2+h^2]=0 nao entendi o que voce fez nessa passagem, infelizmente nao estou podendo escrever agora (no papel) para conferir melhor, nao sei o que t representa mas tudo bem. t^2-(2p-b).t+[p(p-b)+h^2/p(p-b)]/4=0 Espero que esta contalhada esteja certa... Esta eh uma quadratica feia em c com duas raizes, cuja soma eh 2p-b=a+c. eh verdade Isto eh, as duas raizes serao a e c (até porque o problema é simétrico com relação a *a* e *c*, qualquer equação que você enontrar para um servirá para o outro). nao entendi o q c representa. -- Niski - http://www.linux.ime.usp.br/~niski When we ask advice, we are usually looking for an accomplice. Joseph Louis LaGrange = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] x^x
Oi Kara, voce tambem pode usar a derivada logaritmica, para esses casos, e assim : y=x^x, aplique log neperiano em ambos os lados; Lny=Ln(x^x) dai fica assim: Lny=x*Lnx; agora derivamos; y`/y=x*1/x+ 1* Lnx, agora e so fazer as contas. y`=y(1+Lnx)ou y`=x^x(1+Lnx), para x0. Um abra;o. Amurpe. Claro! ehheeh... barbada... depois que se descobre...:-) Brigadão Arthur! - Original Message - From: Artur Costa Steiner [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Friday, January 23, 2004 12:25 PM Subject: Re: [obm-l] x^x Temos que f(x) = x^x = e^(x*Ln (x)), para x0. Logo (regra da cadeia) f´(x) =e^(x*Ln(x)) * ( x*Ln(x)´ = x^x *(x/x + 1* Ln (x)) = (x^x *(1+ Ln(x)), para x0. Artur Oi Pessoal, qual é a derivada de f(x)=x^x? []s OPEN Internet @ Primeiro provedor do DF com anti- vírus no servidor de e-mails @ == === Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html == === = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html = __ Acabe com aquelas janelinhas que pulam na sua tela. AntiPop-up UOL - É grátis! http://antipopup.uol.com.br/ = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Numero esperado de movimentos?
On Fri, Jan 23, 2004 at 12:44:16PM +, Elon Correa wrote: Caros colegas, Uma sequencia (bloco) de 5 digitos binarios, por exemplo, (1 0 1 0 1), e gerada aleatoriamente com iqual probabilidade (50%) de se gerar 1 ou 0. ... (cortando fora um longo enunciado) sequencia maior com 5*N digitos. Ou seja qual o numero esperado de movimentos (trocas) para se obter o valor N para a sequencia maior? Se eu bem entendi o problema é o seguinte: começamos com uma seqüência de 5 bits, dos quais k = k0 são iguais a 1. Sorteamos um dos 5 bits e invertemos, assim alterando o valor de k para k1. Repetimos o processo. Seja n o menor inteiro para o qual kn = 1 ou 5: encontre f(k0), o valor esperado de n em função de k0. Trivialmente f(1) = f(5) = 0. Também é fácil ver que f(0) = 1 pois qualquer que seja o bit sorteado no próximo passo teremos uma seqüência com 1 bit igual a 1. Falta calcular x2 = f(2), x3 = f(3) e x4 = f(4). A cada passo sorteamos um bit e temos probabilidade k/5 de escolhermos um 1 e portanto diminuirmos em 1 o valor de k e probabilidade 1-(k/5) de escolhermos um 0 e portanto aumentarmos em 1 o valor de k. Assim x2 = (2/5) + (3/5)*(1 + x3) x3 = (3/5)*(1 + x2) + (2/5)*(1 + x4) x4 = (4/5)*(1 + x3) + (1/5) A primeira equação tem a seguinte justificativa: a partir de uma seq com 2 bits iguais a 1, temos 2/5 de probabilidade de irmos parar em uma seq com 1 bit e neste caso o processo acaba em tempo 1 e temos 3/5 de probabilidade de irmos parar em uma seq com 3 bits iguais a 1, neste caso o processo acaba, em média, em tempo (1 + x3). Assim x2 = (2/5) + (3/5)*(1 + x3), como queríamos. As outras duas equações são análogas. Resolvendo o sistema temos f(2) = 19/4, f(3) = 25/4, f(4) = 6. Mas talvez eu não tenha interpretado corretamente. Talvez a pergunta seja: começando com uma seqüência tomada ao acaso, qual o valor esperado de n? Neste caso a resposta seria (1/32)*f(0) + (5/32)*f(1) + (10/32)*f(2) + + (10/32)*f(3) + (5/32)*f(4) + (1/32)*f(5) = 141/32 ~= 4.4. []s, N. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] probleminha de geometria - escolher resposta
Sauda,c~oes, Esses dados (a,h_a,2p) permitem uma construcao com regua e comp. do triangulo. r, r_a, R = raios dos circulos inscrito, exinscrito e circunscrito. Como S = ah_a/2 = pr, obtemos r. 2p/a = h_a/r. Com h_a e r obtemos r_a: (h_a-2r)/r = h_a/r_a. Com a e (r_a-r) obtemos R: a^2 = (r_a-r)(4R - (r_a-r)). Com a,h_a,R a construccao do triangulo eh facil. O problema possui no máximo uma soluccao. []'s Luis -Mensagem Original- De: niski [EMAIL PROTECTED] Para: [EMAIL PROTECTED] Enviada em: quinta-feira, 22 de janeiro de 2004 18:53 Assunto: [obm-l] probleminha de geometria - escolher resposta Pessoal, tentando resolver o seguinte problema, cheguei em uma duvida, se possivel acompanhem meu raciocinio na resolucao do problema, acredito que seja simples de seguir. Dados a altura, base e o perimetro de um triangulo, determine o triangulo. Notacao: b : base h : altura a+b+c = 2p : perimetro. Esboço rudimentar do triangulo: B /\ a/ \c /\ C b A A altura em relacao ao lado AC determina dois segmentos de reta, que vao medir b-m e m. Com m b Bom, pede-se para determinar os outros lados (a e c) do triangulo em funcao de b,h e 2p. É imediato que a = 2p - b - c (I) Por Pitagoras: c^2 = h^2 + m^2 m = sqrt(c^2 - h^2) (II) Pela lei dos cossenos: c^2 = b^2 + a^2 - 2*a*b*cos(BCA) c^2 = b^2 + a^2 - 2*a*b*((b-m)/a)) c^2 = a^2 - b^2 + 2*b*m (III) Subistituindo II em III vem: c^2 = a^2 - b^2 + 2*b*sqrt(c^2 - h^2) Bem, preciso resolver essa equacao em c, e assim posso subistituir em (I) determinando um lado. O problema é que essa equação biquadrada não é nada simpática de resolver, apelei ao Mathematica e ele me apresentou as seguintes solucoes (vou reproduzir apenas as solucoes com raizes positivas): c = sqrt(a^2 + b^2 - 2*sqrt((a^2)*(b^2) - (b^2)*(h^2))) ou c = sqrt(a^2 + b^2 + 2*sqrt((a^2)*(b^2) - (b^2)*(h^2))) E agora, qual eu escolho!? Obrigado a todos, um abraço. -- Niski - http://www.linux.ime.usp.br/~niski When we ask advice, we are usually looking for an accomplice. Joseph Louis LaGrange = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html = = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
[obm-l] Impossibilidade do movimento
Entre dois números reais há infinitos outros. Considere um segmento de reta com o número 0 assinalado em uma ponta e o número 1 marcado na outra. Considere também que esse segmento de reta foi representado no chão com um risco de um metro de comprimento. Para cada número entre 0 e 1 há um ponto correspondente no segmento de reta. Como eu consigo caminhar do ponto 0 até o ponto 1, se para chegar de 0 até 1 eu tenho que passar por infinitos pontos?
[obm-l] Impossibilidade do movimento
Entre dois números reais há infinitos outros. Considere um segmento de reta com o número 0 assinalado em uma ponta e o número 1 marcado na outra. Considere também que esse segmento de reta foi representado no chão com um risco de um metro de comprimento. Para cada número entre 0 e 1 há um ponto correspondente no segmento de reta e, conseqüentemente, no risco marcado no chão. Como eu consigo caminhar do ponto 0 até o ponto 1, se para chegar de 0 até 1 eu tenho que passar por infinitos pontos? = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Impossibilidade do movimento
Caro Marcelo, Achei interessante o seu raciocinio , pois na Fisica hah um problema semelhante : um certo filosofo de nome Zenao (escrito com til no "a"),na Grecia clássica, afirmou que o movimento deveria ser impossivel por a pessoa ter que passar por infinitos pontos entre um ponto "A" e um ponto "B". Fisicamente, a explicacao desse problema deve ser feito pensando no conceito de movimento instantaneo (detalhe que o filosfo em questao nem sabia por nao existir na matematica daquele tempo a derivada), que eh dado pela formula lim.dx/dt.Matematicamente, talvez haja semelhança com esse problema. ___Marcelo Augusto Pereira [EMAIL PROTECTED] wrote: Entre dois números reais há infinitos outros. Considere um segmento de reta com o número 0 assinalado em uma ponta e o número 1 marcado na outra. Considere também que esse segmento de reta foi representado no chão com um risco de um metro de comprimento. Para cada número entre 0 e 1 há um ponto correspondente no segmento de reta. Como eu consigo caminhar do ponto 0 até o ponto 1, se para chegar de 0 até 1 eu tenho que passar por infinitos pontos?Yahoo! GeoCities: a maneira mais fácil de criar seu web site grátis!
[obm-l] Re:[obm-l] Re: [obm-l] polinômios
On Thu, Jan 22, 2004 at 07:41:00PM -0200, André Martin Timpanaro wrote: Se n é um número impar e a é um real qualquer, quando a equação abaixo pode ser resolvida por radicais? x^n + a(x+1)=0 Se for possível, quais são as raízes reais dessa equação? Não entendi pq n ímpar; talvez para garantir que existe raiz real, mas isto não tem muito a ver, tem? Isto é um problema de teoria de Galois e não sei se entendi bem a pergunta. Acho que você quer a resposta em função de n e não em função de n e a, certo? Ou seja, você quer saber para quais valores de n existe uma fórmula com radicais que dê a raiz em termos de a. É isso? Se for isso você quer saber para que valores de n o grupo de Galois de x^n + a*x + a é solúvel, onde os coeficientes estão no corpo Q(a), sendo a um transcendente que pode igualmente bem ser tratado como outra viariável desde que entendamos que o grupo é em relação à variável x. Eu *acho* que este grupo de Galois é sempre o grupo simétrico S_n. Eu sei que o grupo de Galois de x^n + a_{n-1} x^{n-1} + ... + a_1 x + a_0 é S_n (onde a_{n-1}, ..., a_0 são algebricamente independentes, ou, se você preferir, são outras variáveis). O grupo de Galois de um polinômio de grau n em geral é S_n e acho que este polinômio é bem geral (as aspas marcam que isto não é uma afirmação das mais precisas). Eu verifiquei no maple para n = 9 e deu certo (isto é, para n = 9 o grupo é mesmo S_n). Se isto estiver certo a resposta é que a equação pode ser resolvida por radicais apenas para n = 4. []s, N. Percebi que esqueci de alguns detalhes (que não achei serem importantes): Na verdade a era uma função de n, consegui fazer uma simplificação e percebi que basta que x^n - nx +1 - n seja solúvel por radicais (no caso do meu problema e não se a for um real qualquer) André T. _ MSN Hotmail, o maior webmail do Brasil. http://www.hotmail.com = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
RE: [obm-l] Impossibilidade do movimento
Essencialmente esse problema é ujm dos paradoxos de Zenão, um grego antigo que usava a idéia de infinito para chegar a conclusões aparentemente absurdas, tais como a impossibilidade do movimento, por exemplo. Agora vou dar uma de Dirichlet, o da lista é claro: Pense no seguinte, uma soma de infinitas parcelas positivas é sempre infinito, ou não necessariamente? Para ajudar nessa resposta, pense em calcular, por exemplo: 1/10 + 1/100 + 1/1000 + ... . Bom e agora, o que tudo isto tem a ver com sua pergunta? Espero ter ajudado, apesar dessa resposta meio enigmática, mas acho que assim auxilio mais! Frederico. From: Marcelo Augusto Pereira [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: [obm-l] Impossibilidade do movimento Date: Fri, 23 Jan 2004 19:05:25 -0200 Entre dois números reais há infinitos outros. Considere um segmento de reta com o número 0 assinalado em uma ponta e o número 1 marcado na outra. Considere também que esse segmento de reta foi representado no chão com um risco de um metro de comprimento. Para cada número entre 0 e 1 há um ponto correspondente no segmento de reta e, conseqüentemente, no risco marcado no chão. Como eu consigo caminhar do ponto 0 até o ponto 1, se para chegar de 0 até 1 eu tenho que passar por infinitos pontos? = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html = _ MSN Hotmail, o maior webmail do Brasil. http://www.hotmail.com = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Impossibilidade do movimento
O fato de essa soma ser calculável(1/9) não indica que existe um número de valor muito pequeno e que esse número seria o valor mínimo que possa existir? Assim todos os outros números seriam múltiplos desse menor valor possível, ou seja, esse número seria algo como um valor quântico. Dessa forma, também existiria uma unidade quântica de deslocamento linear, o que faria com que a quantidade de pontos em um segmento de reta não fosse infinita e o movimento fosse possível. Se para cada número existisse um menor, a soma teria que ser infinita, e o resultado infinito. - Original Message - From: Frederico Reis Marques de Brito [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Friday, January 23, 2004 9:27 PM Subject: RE: [obm-l] Impossibilidade do movimento Essencialmente esse problema é ujm dos paradoxos de Zenão, um grego antigo que usava a idéia de infinito para chegar a conclusões aparentemente absurdas, tais como a impossibilidade do movimento, por exemplo. Agora vou dar uma de Dirichlet, o da lista é claro: Pense no seguinte, uma soma de infinitas parcelas positivas é sempre infinito, ou não necessariamente? Para ajudar nessa resposta, pense em calcular, por exemplo: 1/10 + 1/100 + 1/1000 + ... . Bom e agora, o que tudo isto tem a ver com sua pergunta? Espero ter ajudado, apesar dessa resposta meio enigmática, mas acho que assim auxilio mais! Frederico. From: Marcelo Augusto Pereira [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: [obm-l] Impossibilidade do movimento Date: Fri, 23 Jan 2004 19:05:25 -0200 Entre dois números reais há infinitos outros. Considere um segmento de reta com o número 0 assinalado em uma ponta e o número 1 marcado na outra. Considere também que esse segmento de reta foi representado no chão com um risco de um metro de comprimento. Para cada número entre 0 e 1 há um ponto correspondente no segmento de reta e, conseqüentemente, no risco marcado no chão. Como eu consigo caminhar do ponto 0 até o ponto 1, se para chegar de 0 até 1 eu tenho que passar por infinitos pontos? = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html = _ MSN Hotmail, o maior webmail do Brasil. http://www.hotmail.com = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html = = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Numero esperado de movimentos?
Caro Nicolau, Obrigado pela sua resposta. A sua segunda interpretacao do problema eh a correta. Por favor, veja a mesmae tambemo email anterior abaixo. No entanto, o problema completo nao eh composto apenas por um bloco com 5 digitos e sim por varios. Utilizando a sua notacao, seja f(k0) o problema com um bloco; qual seria o menor numero inteiro N(numero esperado de trocas) para se ter f1(k0)+f2(k0)+...+fn(k0)=n?Ou seja, f1(k0)=1, f2(k0)=1, ..., fn(k0)=1? Observe que: 1) Neste caso a sequencia tomada ao acasotera 5*B digitos; Por exemplo, para tres blocos (B=3)a sequencia inicial teria 15 digitos e poderia ser: (1 00 11 0 0 1 1 0 1 0 1 0 1). Vou utilizar colchetes para facilitar a visualizacao dos blocos ([1 00 11][0 0 1 1 0] [1 0 1 0 1]). 2) A cada passo, cada um dos 5*B digitos da sequencia tem sempre a mesma probabilidade 1/(5*B) de ser sorteado. Isto eh, a posicao a ser invertida eh tomada ao acaso. 3) A cada inversaoo valor da sequencia eh avaliado. Se o valor dasequencia apos a inversao for igual ou maior que o valor anterior,a inversao e aceita. Caso contrario a sequencia permanece inalterada. Exemplo, suponha queuma sequencia com tres blocos B=3 esteja no seguinte estado: ([1 0100][1][0 00 0 1]). Pode observar-se que o primeiro bloco vale 0 masosegundo e o terceiro bloco valem 1 cada. Portantoo valor da sequencia toda eh 0+1+1=2. Suponha que o sexto digito da sequencia acima seja escohlido para troca; entao teriamos: ([1 0100][0][0 00 0 1]).O valor da sequencia passaria a ser 0+0+1=1. Como este valor eh menor que o valor da configuracao anterior a troca nao e aceita.Portanto, aconfiguracao anterior ([1 0100][1][0 00 0 1]) eh mantida. No entanto a troca feitano sexto digitoconta para o numero esperado de trocas - embora a troca nao seja aceita. 4) O processo acaba somente quando todos os blocos valem 1. Ou seja, quando a sequencia toda vale B. Por exemplo, na sequenci acima poderiamos ter: ([0 0100][1][0 00 0 1]),ou o valor da sequencia = 3. Obrigado, Elon Nicolau escreveu: Mas talvez eu não tenha interpretado corretamente.Talvez a pergunta seja: começando com uma seqüência tomada ao acaso, qual o valor esperado de n? Neste caso a resposta seria (1/32)*f(0) + (5/32)*f(1) + (10/32)*f(2) ++ (10/32)*f(3) + (5/32)*f(4) + (1/32)*f(5) = 141/32 ~= 4.4."Nicolau C. Saldanha" [EMAIL PROTECTED] wrote: On Fri, Jan 23, 2004 at 12:44:16PM +, Elon Correa wrote: Caros colegas, Uma sequencia (bloco) de 5 digitos binarios, por exemplo, (1 0 1 0 1), e gerada aleatoriamente com iqual probabilidade (50%) de se gerar 1 ou 0 (cortando fora um longo enunciado) sequencia maior com 5*N digitos. Ou seja qual o numero esperado de movimentos (trocas) para se obter o valor N para a sequencia maior?Se eu bem entendi o problema é o seguinte:começamos com uma seqüência de 5 bits, dos quais k = k0 são iguais a 1.Sorteamos um dos 5 bits e invertemos, assim alterando o valor de k para k1.Repetimos o processo. Seja n o menor inteiro para o qual kn = 1 ou 5:encontre f(k0), o valor esperado de n em função de k0.Trivialmente f(1) = f(5) = 0.Também é fácil ver que f(0) = 1 pois qualquer que seja o bit sorteado nopróximo passo teremos uma seqüência com 1 bit igual a 1.Falta calcular x2 = f(2), x3 = f(3) e x4 = f(4).A cada passo sorteamos um bit e temos probabilidade k/5 de escolhermosum 1 e portanto diminuirmos em 1 o valor de k e probabilidade 1-(k/5)de escolhermos um 0 e portanto aumentarmos em 1 o valor de k.Assimx2 = (2/5) + (3/5)*(1 + x3)x3 = (3/5)*(1 + x2) + (2/5)*(1 + x4)x4 = (4/5)*(1 + x3) + (1/5)A primeira equação tem a seguinte justificativa:a partir de uma seq com 2 bits iguais a 1, temos 2/5 de probabilidadede irmos parar em uma seq com 1 bit e neste caso o processo acaba em tempo 1e temos 3/5 de probabilidade de irmos parar em uma seq com 3 bits iguais a 1,neste caso o processo acaba, em média, em tempo (1 + x3).Assim x2 = (2/5) + (3/5)*(1 + x3), como queríamos.As outras duas equações são análogas.Resolvendo o sistema temos f(2) = 19/4, f(3) = 25/4, f(4) = 6.Mas talvez eu não tenha interpretado corretamente.Talvez a pergunta seja: começando com uma seqüência tomada ao acaso,qual o valor esperado de n? Neste caso a resposta seria(1/32)*f(0) + (5/32)*f(1) + (10/32)*f(2) ++ (10/32)*f(3) + (5/32)*f(4) + (1/32)*f(5) = 141/32 ~= 4.4.[]s, N.=Instruções para entrar na lista, sair da lista e usar a lista emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html= Yahoo! Messenger - Communicate instantly..."Ping" your friends today! Download Messenger Now
[obm-l] Cubo Rubick R^n
Ola pessoal, No endereco (http://superliminal.com/cube/cube.htm) ha um cubo rubik em 4-D. Pelo que parece, em sua representacao ha 7 cubos 3-D interdependentes. O que quero dizer com interdependentes ? Quero dizer que se alterarmos um cubo 3-D (dos 7 cubos presentes) iremos alterar outros cubos 3-D e consequentemento o Hyper-Cubo...Ex: Se alterarmos o laranja nos cubiculos medianos, entao ira se alterar o verde e o azul, ou seja, 3 modificados incluindo o laranja !!! Poderiamos tbem provocar 4 modificacoes (alterando o roxo, marrom, rosa e azul ). Esta eh a maneira como entendi este cubo rubick 4-D. Se me equivoquei me corrijam...Minha duvida eh: Como ficaria um cubo rubick 5-D ? Pensei na recorrencia: 1 cubo rubick 3-D para gerar um cubo rubick 4-D multiplicou-se em 7 entao: 1 cubo rubick 4-D para gerar um cubo rubick 5-D multiplicou-se em 7*7 = 49 Por que digo 49 ? O cubo 4-D apresenta cuboS 3-D, entao um cubo 5-D apresentarah cubosS 4-D. Logo cada cubo 3-D da figura ira se multiplicar formando um cubo 4-D (com 7 cubos 3-D), como ha 7 cubos 3-D teremos 48 cubos 3-D que sao INTERDEPENDENTES E INTER-RELACIONADOS. Se nao for esta a aparencia de um cubo 5-D, como seria entao ?