Um baralho com n cartas numeradas de 1 a n é embaralhado de forma que todas as n! ordenações de cartas possíveis sejam igualmente prováveis. Suponha que você faça n palpites sucessivos, onde o i-ésimo palpite diz que a carta desejada está na posição i. Chame de No número de palpites corretos.
a) Se você não recebe informações sobre seus palpites anteriores, mostre que, para qualquer estratégia, E[N] = 1.
b) Suponha que, após cada palpite, a carta na posição em questão seja mostrada para você. Qual estratégia você considera a melhor? Mostre que, com essa estratégia,
c) Suponha que lhe digam após cada palpite se você estava certo ou errado. Neste caso, pode-se mostrar que a estratégia que maximiza E[N] é aquela em que você continua a fazer sempre o mesmo palpite, escolhendo a mesma carta até acertá-la e mudando depois para uma nova carta. Para essa estratégia, mostre que
Passo 1
Fala galeraaa!
Vamos que vamos!
No item (a):
Defina a variável aleatória que marca se adivinhamos cartão ou não. Como todos os arranjos possíveis são igualmente prováveis, a probabilidade de que j a carta tenha sido adivinhada é de:
Observe que . Usando a linearidade da expectativa, temos:
que foi reivindicado.
Passo 2
No item (b):
Nesse caso, sabemos quais cartas foram colocadas nas posições antes de adivinhar qual carta está na posição j. Assim, podemos excluir essas cartas anteriores de nossa consideração e escolher uma das cartas restantes aleatoriamente. Portanto, a probabilidade de estarmos certos é de:
Usando a linearidade da expectativa, temos que:
que foi reivindicado.
Passo 3
No item (c):
Observe que neste caso temos o seguinte. Temos que se e somente se continuarmos adivinhando do começo ao fim.
Daí, temos que:
Da mesma forma, temos que:
Então, acabamos com:
Resposta
Veja solução.