A regra dos 37 por cento

O problema

Você está procurando apartamento numa cidade cara. São 20 para visitar, um por dia, e o mercado é brutal: se você não fechar na hora, o apartamento vai embora. Cada visita termina numa decisão irreversível — assinar ali e parar de procurar, ou recusar para sempre.

Só existem dois jeitos de errar, e eles puxam para lados opostos. Fechar cedo demais é assinar sem saber o que existia depois. Olhar demais é deixar os bons passarem e ficar com o resto. Quantos você deveria visitar só para olhar, antes de começar a aceitar?

A resposta: 37%

Visite os primeiros 37% sem fechar com nenhum, guarde qual foi o melhor deles, e depois disso assine com o primeiro que for melhor que todos esses. Com 20 apartamentos: recuse os 7 primeiros, aconteça o que acontecer.

Seguindo essa regra, a chance de terminar com o melhor dos 20 é de 38,4%. E o número quase não se mexe com o tamanho da fila: com mil candidatos, recusando os 368 primeiros, a chance é de 36,82%; com um milhão, 36,8%. Um em cada três, escolhendo um entre um milhão quase às cegas.

As duas fases

A regra tem duas fases, e a primeira é a que dói.

Na fase de amostra você visita e recusa, mesmo gostando. Ela não serve para achar apartamento: serve para construir uma régua. Sem ela você não tem ideia do que é “bom” naquela cidade.

Na fase de aposta a régua já existe, e a primeira coisa que passar por cima dela é sua. Se nada passar, você fica com o último — e isso acontece exatamente quando o melhor de todos estava na amostra, com chance $r/n$, que também tende a 37%.

A conta

Chame de $n$ o tamanho da fila e de $r$ o tamanho da amostra. Para a regra terminar com o melhor de todos, duas coisas precisam acontecer juntas:

1. o melhor de todos precisa estar depois da amostra, numa posição $i>r$;
2. ninguém antes dele pode ser aceito — ou seja, o melhor entre os $i-1$ primeiros precisa estar dentro da amostra, senão ele teria batido a régua e sido aceito antes.

O melhor está na posição $i$ com chance $1/n$. Dado isso, o melhor dos $i-1$ anteriores está em qualquer uma dessas posições com a mesma chance, e cai na amostra com chance $r/(i-1)$. Somando sobre as posições possíveis:

$$P(r)=\sum _{i=r+1}^n\frac{1}{n}\cdot \frac{r}{i-1}=\frac{r}{n}\sum _{j=r}^{n-1}\frac{1}{j}.$$

Para $n=20$, a soma é máxima com 7 candidatos na amostra:

$$P(7)=\frac{7}{20}\left(\frac{1}{7}+\frac{1}{8}+\cdots +\frac{1}{19}\right)\approx 0,3842.$$

De onde sai o 1/e

Para filas grandes, chame $x=r/n$ a fração usada como amostra. A soma vira uma integral — é uma soma de Riemann, com retângulos de largura $1/n$:

$$P\approx x{\int }_x^1\frac{\mathrm{d}t}{t}=-x\ln x.$$

As duas condições brigam dentro dessa fórmula: o fator $x$ cresce com a amostra (a régua fica mais alta, menos gente medíocre engana você), e o $-\ln x$ encolhe (sobra menos fila para o melhor aparecer depois). O equilíbrio é onde a derivada zera:

$$\frac{\mathrm{d}}{\mathrm{d}x}(-x\ln x)=-\ln x-1=0⟹x=\frac{1}{e},P=-\frac{1}{e}\ln \frac{1}{e}=\frac{1}{e}\approx 0,3679.$$

O mesmo número nos dois lugares: 36,8% da fila para olhar, 36,8% de chance de acertar em cheio. O $e$ aparece pelo mesmo motivo que em juros compostos e em decaimento radioativo: no fundo, uma quantidade sendo multiplicada muitas vezes por algo quase igual a 1 — aqui, a chance de cada candidato da fase de aposta não bater a régua.

O que a regra supõe

Antes de sair aplicando, olhe as três hipóteses — e repare como elas são fortes:

1. Não dá para voltar. Recusou, perdeu.
2. Você só compara, nunca pontua. Você sabe que este é melhor que aquele, mas não sabe se é bom.
3. Só o melhor de todos vale. O segundo lugar vale zero — o que é bizarro: ninguém procura apartamento assim.

Afrouxe uma hipótese e o número muda

E essa é a boa notícia: 37% é o caso mais cego possível. É o piso, não o teto.

Se o segundo lugar também serve, a melhor estratégia possível passa a ter duas fases de aceite: até uns 34,8% da fila, recuse todos; dali em diante, aceite quem for o melhor até então; e a partir de uns 66,8% aceite também quem for o segundo melhor até então. A chance de terminar com um dos dois melhores sobe para 57,4%.

Se você consegue pontuar cada candidato numa escala absoluta — conhece a distribuição das notas —, a estratégia ótima deixa de ter uma fase de amostra: vira um limite de aceitação que vai caindo conforme a fila acaba. Com essa informação a mais, a chance de pegar o melhor sobe para cerca de 58% (resultado de Gilbert e Mosteller, de 1966).

Se recusar tem custo — cada visita custa tempo e dinheiro —, a amostra encurta ainda mais.

Onde isso vale

A regra encaixa onde as três hipóteses são quase verdadeiras: procurar vaga numa rua de mão única (você passa, avalia e não volta), entrevistar candidatos com decisão na hora, escolher em que posto abastecer numa estrada longa. Em todos, a forma da resposta é a mesma: olhe sem fechar por um tempo, depois feche com o primeiro que bater o recorde.

O valor prático não é o número exato: é a estrutura. Existe um momento certo de parar de coletar informação e começar a decidir, e ele chega bem antes do que a ansiedade sugere — 37%, não 90%. Continuar olhando depois disso não é prudência. É a forma mais cara de errar.

Os números do episódio

Desafios

Para ir além

• O problema circulou como quebra-cabeça nos anos 1950 e ficou famoso em 1960, na coluna de Martin Gardner na Scientific American (como o “jogo do googol”). A solução com $1/e$ aparece em trabalhos de Dennis Lindley (1961) e outros; a história completa está no artigo de Thomas Ferguson Who solved the secretary problem? (1989).
• As variações com o segundo lugar e com notas absolutas são de John Gilbert e Frederick Mosteller (1966).
• O episódio sobre limite explica o que significa “para filas grandes” com precisão.