In partnership with

ED 046

Os dez armários que continuam abertos

Cem alunos percorrem o corredor invertendo portas, e o desfecho cabe numa lista de dez números que qualquer pessoa reconhece de longe.

Corredor escolar escuro com cem portas de armário fechadas e dez delas escancaradas.

Cem portas, dez ainda abertas

▼

Por que sobram dez portas abertas, e não cinquenta? Porque cada armário é mexido uma vez para cada divisor do próprio número, e divisor costuma andar aos pares. Uma única família de números escapa desse pareamento, e ela é curta.

O enunciado cabe num parágrafo. Um corredor tem cem armários, todos fechados, numerados de 1 a 100. Cem alunos entram em fila, também numerados de 1 a 100. O aluno 1 mexe em todos os armários. O aluno 2 mexe só nos de número par. O aluno 3 mexe nos múltiplos de 3. E assim segue, cada aluno n mexendo apenas nos armários cujo número é múltiplo de n.

Mexer aqui tem sentido preciso: o aluno inverte o estado da porta. Armário fechado ele abre, armário aberto ele fecha. Ninguém escolhe, ninguém pula, ninguém volta atrás. Quando o aluno 100 termina a passagem dele, o corredor fica parado num estado definitivo, e a pergunta é quais portas ficaram abertas.

A intuição chuta alto e erra por larga margem. Muita gente aposta em metade, cinquenta portas, porque a chance de estar aberta parece ser de cara ou coroa. Outros apostam nos ímpares, ou nos primos, ou num padrão alternado. As três apostas caem por terra na primeira conferência feita com papel.

O caminho curto passa por trocar a pergunta. Em vez de simular o corredor inteiro, olhe um armário só e conte quantas vezes a mão de alguém tocou nele. O armário 12 é tocado pelos alunos 1, 2, 3, 4, 6 e 12, que são exatamente os divisores de 12. São seis toques, número par, e porta que sai fechada e recebe quantidade par de inversões volta ao estado inicial. O armário 12 termina fechado.

Repita o raciocínio em qualquer armário e a regra aparece sozinha: a porta fica aberta quando a quantidade de divisores do número dela é ímpar. Resta descobrir quais números têm essa quantidade ímpar, e é aí que o problema deixa de ser sobre corredor e passa a ser sobre aritmética.

O armário 36 entrega a mecânica inteira, toque por toque, e explica por que a lista final é tão pequena.

Continue lendo ↓

I A resposta de ontem

Dez portas abertas num corredor de cem

Conte os divisores do 36 devagar: 1, 2, 3, 4, 6, 9, 12, 18 e 36. São nove alunos que mexem nessa porta, quantidade ímpar, e por isso o armário 36 termina aberto. Agora repare no motivo de os divisores do 36 darem número ímpar, porque é esse detalhe que resolve o corredor todo.

Divisor nasce em dupla. Se 2 divide 36, então 18 também divide, porque 2 vezes 18 dá 36. Se 3 divide, 12 divide. Se 4 divide, 9 divide. Cada divisor pequeno arrasta um parceiro grande, e a conta normalmente fecha em quantidade par. No 36 aparece uma dupla estranha: 6 vezes 6 dá 36, e o parceiro do 6 é ele mesmo. Essa dupla vale por um divisor só, e é ela que torna a contagem ímpar.

Isso acontece quando, e somente quando, o número é um quadrado perfeito (resultado de multiplicar um inteiro por ele mesmo). Qualquer outro número tem os divisores todos emparelhados, contagem par, porta fechada no final.

A lista final do corredor é curta: 1, 4, 9, 16, 25, 36, 49, 64, 81 e 100. Dez portas abertas, e nenhuma outra. Os armários 1 e 100 estão entre elas, o que costuma surpreender quem simulou o corredor de cabeça e imaginou o último armário muito visitado.

O armário 100 tem nove divisores: 1, 2, 4, 5, 10, 20, 25, 50 e 100. O último aluno a tocar nele é o 100. Como a contagem é ímpar, a porta fica aberta, e o aluno 10 é o que encosta nela sem trazer parceiro novo, porque 10 vezes 10 dá 100.

A pergunta mudou de lugar, e é por isso que a resposta encurtou. Ninguém precisa acompanhar cem alunos ao longo do corredor; basta contar os divisores de um número e olhar se a contagem é par ou ímpar.

Onde o teste de mesa trava

O primeiro erro é simular o corredor de verdade. Quem desenha cem quadradinhos e risca estado por estado gasta quarenta minutos e erra no meio da lista, porque a passagem do aluno 7 já embaralha o desenho.

O segundo erro é confundir aberto com muito visitado. O armário 96 recebe doze toques, mais que o 36, e mesmo assim termina fechado. O que decide é a paridade da contagem, nunca o tamanho dela.

O terceiro erro é parar no 1. O armário 1 tem um divisor só, contagem ímpar, e fica aberto depois da passagem do primeiro aluno, sem que ninguém mais encoste nele. Quem trata o 1 como caso especial acaba tirando ele da lista e devolve nove portas em vez de dez.

II O Enigma do dia

Mil portas, um aluno ausente e três perguntas

O corredor agora tem mil armários fechados, numerados de 1 a 1000, e mil alunos na mesma regra: o aluno n inverte o estado de todo armário múltiplo de n. Três perguntas, e as três pedem resposta escrita com número, não palpite. Primeira: quantos armários ficam abertos ao terminar a passagem do aluno 1000? Segunda: se o aluno 1 faltar à aula e ninguém cobrir a passagem dele, quantos armários ficam abertos, e quais são os fechados? Terceira: entre 1 e 100, quais armários são tocados exatamente três vezes, e o que esses números têm em comum?

As regras valem reler antes de escrever qualquer coisa. Todos os armários começam fechados, cada aluno percorre o corredor uma vez só, e inverter significa abrir o que está fechado e fechar o que está aberto. A resposta pedida traz a contagem, a lista quando ela é curta e o critério que decide cada caso.

Onde quase todo mundo trava

O primeiro erro é multiplicar a resposta anterior por dez. Cem armários deram dez portas abertas, e a tentação é dizer cem portas abertas em mil armários. A conta certa procura o maior número cujo quadrado não passa de mil, e esse número não é cem.

O segundo erro, na pergunta do aluno faltoso, é imaginar que a ausência dele muda pouco. Ele é o único que toca em todas as portas, então a falta dele altera a paridade de cada armário do corredor, sem exceção. O resultado vira o avesso exato do caso anterior, e a lista curta troca de lado.

O terceiro erro é tratar a terceira pergunta como caça ao acaso. Quantidade de toques igual a três significa quantidade de divisores igual a três, e número com poucos divisores tem formato rígido. Escreva quais números admitem exatamente três divisores e a lista aparece em dois minutos, sem varredura.

Contagem de divisores é o instrumento certo, e vale a pena montar ela antes de contar qualquer porta. Fatore o número em primos, some 1 a cada expoente, multiplique os resultados. A conta entrega quantos divisores existem, e a paridade desse produto decide o estado da porta sem que ninguém precise andar pelo corredor.

Responda as três com prova. Escreva quantos armários ficam abertos em mil, quantos ficam abertos com o aluno 1 ausente mais a lista dos fechados nesse cenário, e quais números entre 1 e 100 recebem exatamente três toques.

Quem banca a edição de hoje

We’ve driven over $10M in revenue for our newsletter clients. For the first time, we’re unpacking the plug-and-play system thousands of people are using to turn a small email list into $2k-$10k/month.

If you've tried to grow your email list’s revenue and hit a wall of vague advice like 'post more' or 'engage your audience,' this workshop is built to show you precisely what is working for the top newsletter operators in the world.

We’ll show you how to pick or validate your niche, scale to 1,000 readers, and make your first $10,000 in revenue.

No prior experience, no camera time, and no need to already have a big email list.

Save Your Free Seat

Patrocinadores mantêm a edição gratuita

III Sequência

A conta de divisores que dispensa o corredor

O material é papel, lápis e quinze minutos. O procedimento abaixo fecha os três casos e serve para qualquer problema em que um estado se inverte repetidamente.

1. Traduza a passagem em divisor. O armário de número n é tocado pelo aluno k quando k divide n. A quantidade de toques na porta n é a quantidade de divisores de n, e nada mais precisa ser simulado.

2. Fatore e conte. Escreva n como produto de primos com expoentes. A quantidade de divisores é o produto dos expoentes somados de 1 cada. Em 36, que é 2 elevado a 2 vezes 3 elevado a 2, a conta dá 3 vezes 3, ou seja nove divisores.

3. Olhe a paridade do produto. Esse produto só é ímpar quando todos os expoentes são pares, e expoente par em toda a fatoração é a definição de quadrado perfeito. Porta aberta no final equivale a número quadrado perfeito, sempre.

4. Ajuste o cenário e refaça a paridade. Se algum aluno faltar, subtraia os toques que ele daria e recalcule se a contagem virou par ou ímpar. Mudança pequena na lista de alunos costuma inverter o corredor inteiro, e a conta mostra isso em uma linha.

"Um matemático, tal como um pintor ou um poeta, é um fabricante de padrões."

G. H. Hardy, Em Defesa de um Matemático, 1940.

A resposta das três perguntas vem escrita, sem sobra. Em mil armários ficam abertos 31, que são os quadrados perfeitos de 1 a 961, porque 31 vezes 31 dá 961 e 32 vezes 32 já passa de mil. Com o aluno 1 ausente, cada porta perde um toque, a paridade se inverte e ficam abertos os 969 armários que não são quadrados perfeitos; fechados ficam os 31 quadrados, incluindo o armário 1, que nesse cenário não recebe toque nenhum. Entre 1 e 100, recebem exatamente três toques os armários 4, 9, 25 e 49, que são os quadrados de números primos: divisores 1, o primo e o quadrado dele, três e nada mais.

A Sequência é o placar de quem fecha sozinho. Um ponto por enigma resolvido antes da solução chegar, e o placar zera quando você espia fora da hora.

O enunciado viaja bem porque troca de roupa com facilidade. Trocando armário por lâmpada e aluno por interruptor, a mesma conta descreve um painel de luzes; trocando por engrenagem que gira meia volta a cada comando, descreve um mecanismo. A estrutura por trás tem nome próprio em matemática, a paridade da função contadora de divisores.

Todo problema em que um estado se inverte muitas vezes se resolve contando quantas inversões cada peça recebe, nunca acompanhando a ordem delas. A ordem dos alunos no corredor não muda coisa alguma no desfecho, e perceber isso derruba a metade do trabalho que a simulação exigiria.

"Quantas vezes você simulou passo a passo um processo cujo desfecho dependia só de uma contagem par ou ímpar?"

Teste hoje, em oito minutos: escreva numa folha os números de 1 a 20 e, para cada um, anote quantos divisores ele tem, contando na mão. Circule os que deram quantidade ímpar. Você vai circular exatamente quatro números, o 1, o 4, o 9 e o 16, e nenhum outro. Depois estenda a folha até 30 sem contar divisor nenhum, só marcando o 25: acertar essa previsão em menos de dez segundos mostra que a conta já substituiu o corredor na sua cabeça.