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 =========================================================================