sábado, 31 de março de 2012

O Problema de Monty Hall

Convido você a participar de um jogo (fictício) em que, ao final, você pode ganhar ou bem um carro 0km ou um bode velho e magro. O jogo é o seguinte:

Atrás das portas abaixo há um carro 0km e dois bodes velhos e magros,


ou seja, o carro está atrás de uma das portas acima e atrás de cada uma das outras duas portas há um bode velho e magro.

Como informação importantíssima sobre esse jogo, eu sei o que há atrás de cada uma das portas.

Início do Jogo

Primeiro movimento: você escolhe uma das portas

Segundo movimento: uma vez que você escolheu uma porta eu abro uma das outras duas portas que restaram, e revelo para você um bode (Ressalto que eu não abro essa porta aleatoriamente, pois, como informei, eu sei exatamente o que há atrás de cada porta)


Terceiro movimento: você escolhe permanecer com a porta que escolheu no primeiro movimento ou trocar pela outra porta que restou fechada 

Final do jogo

Você ganha o que tiver atrás da porta que você escolheu no terceiro movimento.


Problema. Partindo do pressuposto que você está interessado em ganhar o carro 0km e não um bode velho e magro, qual seria a melhor estrategia a seguir no terceiro movimento, permanecer com a porta escolhida no primeiro movimento ou efetuar a troca?

O problema acima é conhecido como o Problema de Monty Hall. Monte Halperin (Monty Hall) foi apresentador do game show norte-americano Let's Make a Deal onde ele propunha o jogo acima para seus convidados 
(Fonte: Wikipedia "The Monty Hall Problem").

Solução do Problema. É fato que a decisão que você deve tomar está no terceiro movimento. Agora, observe o que ocorre no primeiro movimento. Você escolhe uma entre três portas, portanto a probabilidade de você ter escolhido a porta que esconde o carro é de 1/3 e, portanto, a probabilidade do carro está comigo é de 2/3. No segundo movimento, quando eu abro uma porta que está em meu poder, revelando um bode, eu não mudo as probabilidades acima, pois, como informei, eu não abro essa porta aleatoriamente. Assim, no terceiro movimento, você tem a oportunidade de permanecer com a probabilidade de 1/3 (de estar com o carro) ou trocar pela probabilidade de 2/3. Logicamente, do ponto de vista probabilístico, a melhor estrategia é trocar de portas no terceiro movimento.
Final da solução.

Abaixo segue uma cena do filme 21 (traduzido por: Quebrando a banca) em que o Problema de Monty Hall é discutido e solucionado. 


Ah! Vale a pena ver esse filme.




segunda-feira, 12 de março de 2012

... múltiplos irados...


por Bill Bastos e Breno Sampaio


Ao final de mais uma tarde de verão, três amigos se reúnem em uma refrigerada cafeteria de um shopping Center de Fortaleza para tomar algumas xícaras de café, falar de matemática e outros assuntos correlatos. Antes da primeira rodada de café, um problema sobre múltiplos irados, o qual foi proposto na revista RPM 77, veio à mesa. 

Aqui, faz-se necessaria a apresentação do conceito de número irado. Dizemos que um número natural é irado se ele é escrito, na base decimal, somente com 0's e 1's. 

De volta à narração, simultaneamente aos primeiros exemplos de números irados, chegou à mesa a primeira rodada de café: 3 expressos duplos! 

Problema. Mostrar que todo número natural possui um múltiplo irado.

Assim, sobre a mesa estavam o conceito de números irados, o problema acima e 3 expressos duplos. 


Senso comum: era hora de tomar um pouco de café, filosofar um pouco mais, encontrar a naturalidade da proposição acima. 


A aparente descontração daquele grupo ia se transformando em tensão. Aos olhos de quem se servia ao balcão da cafeteria e, de lá, estava à espera de um lugar mais confortável para se acomodar, um silêncio inexplicável também se punha sobre aquela mesa. 


Momentos que antecediam ao arremate final do problema, ainda antes de terminar a primeira xícara de café, os pensamentos convergiam para um único resultado. 

Teorema de Euler. Se $a$ e $n$  são números naturais relativamente primos, então $n$ divide $a^{\phi(n)}-1$.

Acima, $\phi$ é a função "phi" de Euler que é definida da seguinte forma: $\phi (n)$ é o número de naturais menores do que $n$ e relativamente primos com $n$.

Isso! O Teorema de Euler era suficiente para a construção de uma prova de que todo número natural possui um múltiplo irado. 

Solução do Problema
Seja $n$ um número natural. Escrevamos $n$ da seguinte forma: $n=2^a\cdot 3^b\cdot 5^c\cdot m$ em que $m$ é relativamente primo com $2,3,5$. 


Desde que 10 e $3^{b+2}\cdot m$ são relativamente primos, pelo Teorema de Euler, existe um número natural $k$ de sorte que
$k\cdot 3^{b+2}\cdot m = 10^{\phi(3^{b+2}\cdot m)}-1$
isto é,
$k\cdot 3^{b+2}\cdot m = 99\dots 9$
e, portanto,
$k\cdot 3^b\cdot m  = 11...1$.

Finalmente, recebemos que 
$(2^c\cdot 5^a\cdot k)\cdot n = 11\dots 10\dots 0$
é um múltiplo irado de $n$.
CQD


Para finalizar a postagem, vale ressaltar que essa prova da existência de múltiplos irados é puramente existencial no seguinte sentido: não apresentamos um algoritmo decente para o cálculo do menor múltiplo irado de um número natural qualquer.

Por exemplo, se utilizamos a demonstração acima para encontrar um múltiplo irado do número 13 obtemos o seguinte: pelo Teorema de Euler, 13 divide $10^{12}-1$, ou seja, 13 divide $999.999.999.999$ e, daí, 13 divide $111.111.111.111$. Essa prova produziu um múltiplo irado de 13 que, aparentemente, não possui relação com o menor múltiplo irado de 13, a saber, 1001.

As outras rodadas de café foram dedicadas à seguinte questão:


"há uma fórmula para obter o menor múltiplo irado de $n$ olhando apenas para a sua fatoração em primos?"

A questão acima permanece aberta!