Opta-Fun!

Uma Competição Optativa

Veja aqui os Resultados!!!

O jogo é muito simples. Dois jogadores, A e B, escolhem cada um um padrão de Hs e Ts, de mesmo comprimento. Daí, joga-se uma moeda honesta até um dos padrões aparecer (H significa cara, T significa coroa). Por exemplo: suponha que o padrão de A é HTHH e o padrão de B é THHT. Suponha que ao lançarmos a nossa moeda várias vezes, obtemos

HTTHTTHHHTTHTHTHTTHHT...

(Isto é, cara, coroa, coroa, cara, coroa, etc.) Então o jogador B ganhou, já que o padrão dele apareceu antes do padrão de A. Nesta página, você pode jogar contra o meu agente secreto, o prof. Teoria. Para tanto, basta você eviar uma mensagem para

"Opta-Fun!" <yoshi-fun@ime.usp.br>

com o seu padrão predileto no Subject. A sua mensagem será automaticamente incorporada na página

http://www.ime.usp.br/~yoshi/opta-fun/threads.html

O meu agente secreto, prof. Teoria, lerá o seu padrão no subject de sua mensagem, pensará um pouco, e então irá pôr na mesma página o padrão dele, que ele afirma ser melhor que o seu.

Este esquema estará aberto até o fim da quinta-feira, dia 8/10/98. [Observação. Este esquema estava quebrado até recentemente, mas foi consertado. Experimente!]

Na sexta-feira, divulgarei os resultados. Passarei a noite de quinta para sexta gerando seqüências de Hs e Ts usando o gerador de números aleatórios do Stanford GraphBase de Knuth. Mais especificamente, usarei a rotina gb_unif_rand() (do módulo GB_FLIP). Usarei as sementes guardadas pelo prof. Carlinhos. Para decidir qual entre dois padrões é melhor, gerarei 101 seqüências de Hs e Ts. O padrão que vencer na maioria das seqüências será o padrão vencedor. Gostaria de conseguir, portanto, 101 sementes, mas se o público não for tão paciente, usarei o Carlinhos.

Observações

Um padrão é uma seqüência de Hs e Ts (maiúsculas).
Por simplicidade, vamos jogar com padrões de pelo menos 4 e no máximo 16 caracteres.
Se seu padrão não estiver de acordo com as restrições acima, o prof. Teoria ignorará a sua mensagem (mas não vai falar nem fazer nada grosseiro).
As sementes são inteiros long quaisquer.
Pediria que vocês enviassem apenas 3 mensagens por pessoa. Portanto, pensem bem antes de decidir quais são seus padrões prediletos!
Já tem exemplos na página acima. Dê uma olhada!

Observação final. Bem, o que tem a ver isto com MAC310, MAC338, MAC430, e MAC436? Todas estas disciplinas falam de aspectos teóricos da computação (mais matemáticos ou mais computacionais, dependendo de qual delas a gente está falando mais especificamente). O estudo deste problema de padrões e o estudo de certos problemas matemáticos ou algorítmicos nas matérias acima baseiam-se, surpreendentemente, nas mesmas técnicas. Naturalmente, as disciplinas acima envolvem outras coisas, mas o objetivo é, sempre, "ter fun."

Páginas das disciplinas acimas de anos anteriores:

MAC310 - Matemática Concreta
Algo parecido com MAC430: MAC722 - Introdução à Teoria da Complexidade de Algoritmos

Y. Kohayakawa <yoshi@ime.usp.br>

Last modified: Tue Oct 26 16:22:49 EDT 1999