sábado, 28 de outubro de 2017

HEART ou EARTH

Este problema apareceu no site brilliant.org.
Uma máquina de escrever está a gerar aleatoriamente uma sequência de caracteres de A a Z, todos com igual probabilidade de ocorrência. Dada uma palavra qualquer, essa palavra deverá eventualmente surgir escrita pela máquina, ao fim da geração de um número suficiente de caracteres.
Uma palavra de 5 letras, requererá em média a geração de 26^5 = 11881376 caracteres.
A questão é a seguinte: das duas palavras HEART e EARTH, haverá uma com maior probabilidade de ser escrita em primeiro lugar, ou as probabilidades são idênticas?
Eu acho que sim, que há uma, mais especificamente a palavra HEART, mas este problema desencadeou discussões muito interessantes no meu Facebook, com a maior parte dos intervenientes a achar que as probabilidades são idênticas. Curiosamente, alguns alunos de Informática corroboraram a minha opinião, e chegaram mesmo a produzir simulações que o evidenciavam.
A razão para esta assimetria resulta do facto de as duas palavras dadas diferirem apenas da posição da letra H, e de uma tentativa para formar a palavra EARTH exigir que antes da letra E não esteja a letra H, enquanto que uma tentativa para formar a palavra HEART não tem qualquer restrição na letra que antecede o H.
Em média, em cada 26 tentativas para formar a palavra EARTH, há uma que acaba por formar a palavra HEART, que fica assim mais provável.
Acabo de fazer eu próprio uma pequena simulação com 100 jogos, tendo gerado 637431406 caracteres e tendo a palavra HEART ganho 52 vezes.
Deixo aqui o código mesmo muito elementar que usei

Espero que se divirtam...

2 comentários:

  1. Código-fonte da minha simulação:

    import java.util.Random;

    public class Test {

    private static final char[] letters = {'A','B','C','D','E','F','G',
    'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
    'U', 'V', 'W', 'X', 'Y', 'Z'};

    private static final Random random = new java.util.Random();

    public static void main(String[] args){
    char[] buffer = {' ',' ',' ',' ',' '};
    int heartCount = 0;
    int earthCount = 0;
    for(long i=0; i < Long.MAX_VALUE; i++){
    char letter = drawLetter();
    push(buffer, letter);
    if(isEarth(buffer)){
    earthCount++;
    endGame(buffer, earthCount, heartCount, i);
    }
    if(isHeart(buffer)){
    heartCount++;
    endGame(buffer, earthCount, heartCount, i);
    }

    if(earthCount == 500 || heartCount == 500){
    break;
    }
    }
    }

    private static void endGame(char[] buffer, int earthCount, int heartCount, long letters) {
    System.out.println("Earth: " + earthCount + "\t Heart: " + heartCount + "\tLetters: " + letters);
    buffer[0] = ' ';
    buffer[1] = ' ';
    buffer[2] = ' ';
    buffer[3] = ' ';
    buffer[4] = ' ';
    }

    private static boolean isHeart(char[] buffer) {
    return buffer[0] == 'H' &&
    buffer[1] == 'E' &&
    buffer[2] == 'A' &&
    buffer[3] == 'R' &&
    buffer[4] == 'T';
    }

    private static boolean isEarth(char[] buffer) {
    return buffer[0] == 'E' &&
    buffer[1] == 'A' &&
    buffer[2] == 'R' &&
    buffer[3] == 'T' &&
    buffer[4] == 'H';
    }

    private static void push(char[] buffer, char letter) {
    buffer[0] = buffer[1];
    buffer[1] = buffer[2];
    buffer[2] = buffer[3];
    buffer[3] = buffer[4];
    buffer[4] = letter;
    }

    private static char drawLetter() {
    int index = random.nextInt(letters.length);
    return letters[index];
    }

    }

    ResponderEliminar
  2. Obrigado.
    Deve despachar-se mais depressa que o meu Python...
    :)

    ResponderEliminar