Lançando Moedas

Carla e Daniel decidiram jogar cara-ou-coroa para decidir quem vai lavar os pratos hoje. Eles vão jogar com uma das moedas antigas da coleção de Carla. Isso deixa Daniel preocupado, pois essas moedas são tortas e desbalanceadas: no lançamento de uma moeda, as probabilidades da obtenção de cara e de coroa não são necessariamente iguais.

Carla conhece bem suas moedas, e pode escolher uma que maximize suas chances de vencer. Por isso, Daniel inventou um esquema para fazer com que o sorteio seja completamente justo, independentemente da moeda escolhida. Primeiro, a cada um deles será atribuído um conjunto não-vazio de cadeias binárias de tamanho N. Nenhuma cadeia pode pertencer a ambos, e algumas cadeias podem não ser incluídas no conjunto de nenhum dos dois. Por exemplo, para N = 3, uma forma válida de dividir as cadeias seria:

• "010" e "110" para Carla;

• "001" e "011" para Daniel;

• "000", "100", "101" e "111" para nenhum dos dois.

Após a divisão das cadeias, Carla e Daniel vão jogar a mesma moeda N vezes e anotar a sequência de resultados, onde cada cara equivale a um 0 e cada coroa equivale a um 1. Se a cadeia binária resultante pertencer ao conjunto de Carla, ela é a vencedora. Se pertencer ao conjunto de Daniel, ele é o vencedor. Se a cadeia não pertencer a nenhum dos dois, a moeda é jogada mais N vezes para gerar uma nova cadeia. O processo é repetido tantas vezes quanto necessário, até conseguirem um vencedor.

O justo funcionamento desse esquema depende da repartição das cadeias entre Carla e Daniel: é preciso que a probabilidade de gerar uma cadeia do conjunto de Carla seja igual à probabilidade de gerar uma cadeia do conjunto de Daniel. Em outras palavras, seja P(S) a probabilidade de que uma cadeia binária S de comprimento N seja gerada por uma sequência de N lançamentos de uma mesma moeda, possivelmente desbalanceada. O total de P para todas as cadeias do conjunto de Carla deve ser o mesmo que o total de P para todas as cadeias do conjunto de Daniel.

Além de repartir as cadeias de forma justa, Carla e Daniel querem evitar ao máximo ter que repetir os lançamentos da moeda, e por isso querem minimizar a quantidade de cadeias que não pertençam a nenhum dos dois. Dado o valor de N, determine o menor número possível de cadeias não atribuídas.