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,

E N = 1 n + 1 n - 1 + … + 1 ≈ ∫ 1 n 1 x d x = log ⁡ n

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

E N = 1 +   1 2 ! + 1 3 ! + … + 1 n ! ≈ e - 1 .

Passo 1

Fala galeraaa!

Vamos que vamos!

No item (a):

Defina a variável aleatória I j que marca se adivinhamos j   t h 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:

P ( I j = 1 ) = 1 n

Observe que N = ∑ j I j . Usando a linearidade da expectativa, temos:

E N = ∑ j E I j = ∑ j P I j = 1 = n ⋅ 1 n = 1

que foi reivindicado.

Passo 2

No item (b):

Nesse caso, sabemos quais cartas foram colocadas nas posições 1,2 ,   … ,   j - 1 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:

P ( I j = 1 ) = 1 p j + p 1

Usando a linearidade da expectativa, temos que:

E ( N ) = ∑ j P ( I j ) = ∑ j P I j = 1 = ∑ j = 1 n 1 n ≈ ∫ 1 n 1 x d x = log ⁡ n

que foi reivindicado.

Passo 3

No item (c):

Observe que neste caso temos o seguinte. Temos que I n = 1 se e somente se continuarmos adivinhando do começo ao fim.

Daí, temos que:

P ( I n = 1 ) = 1 n !

Da mesma forma, temos que:

P ( I j = 1 ) = 1 n - j + 1 !

Então, acabamos com:

E N = ∑ j E I j = ∑ j P I j = 1 = ∑ j = 0 n 1 j ! ≈ e - 1

Resposta

Veja solução.