Torres dos Raros
O clássico Torres de Hanói com os raros do hotel. Sua coleção está empilhada numa coluna só, do mais caro embaixo ao mais barato em cima — leve a pilha inteira pra última coluna. Só que tem duas regras: um raro por vez e nunca um raro mais caro em cima de um mais barato (ele esmagaria o coitado).
Aqui o mínimo de lances não é chute nosso nem gabarito do sorteio: é teorema. Com n raros são exatamente 2ⁿ−1 lances — 7 com três raros, 255 com oito. Isso vale pra todo mundo, em qualquer estratégia: bater o mínimo é impossível, empatar é o desafio. E o placar te acompanha de verdade — a cada lance ele diz quantos ainda faltam no mínimo, mesmo depois que você se perde no meio do caminho.
Termine sem dica nem desfazer para marcar um recorde com 3 raros.
Por que 2ⁿ−1, e por que ninguém consegue menos
Pense no raro maior, o de baixo. Uma hora ele tem que sair da primeira coluna e ir pra última. E pra ele poder se mexer, todos os outros n−1 raros precisam estar empilhados na coluna do meio — não tem outro lugar: não podem estar em cima dele, e não podem estar na coluna de chegada, senão ele não pousa. Então todo mundo concorda em três etapas: levar n−1 raros pro meio, mover o maior (1 lance), e levar os n−1 do meio pro fim. As duas pontas são o mesmo problema, um raro menor.
Isso dá T(n) = 2·T(n−1) + 1, e com T(1) = 1 sai 2ⁿ−1. Repare que o argumento não diz "o jeito mais esperto que a gente achou" — ele diz que qualquer solução é obrigada a passar por ali. É por isso que o número é um piso de verdade, e é por isso que a gente pode prometer que ele nunca vai ser batido.
O contador de "jogados fora" sai da mesma conta: lances que você já deu, mais o mínimo que ainda falta, menos 2ⁿ−1. E ele tem uma propriedade meio cruel — nunca diminui. Lance desperdiçado não se recupera: quem sai do caminho perfeito não volta mais pra ele naquela partida. Por isso o selo apaga e não acende de novo.