Quinta, 08 Fevereiro 2018 15:26

UM PROBLEMA EM 3 ATOS

Escrito por

Vamos iniciar nossas publicações com problemas matemáticos aqui no blog. Confira semanalmente nossas publicações com questões relevantes para concursos e olimpíadas de matemática.

Tempos atrás, um colega de trabalho propôs-me o seguinte problema:

Ao longo do corredor de uma escola estão 100 armários, numerados de 1 a 100. Inicialmente todos estão com as portas fechadas. 100 alunos da escola, também numerados de 1 a 100, resolvem fazer a seguinte brincadeira:

O aluno nº 1 passa pelo corredor e abre todos os armários.

Em seguida, o aluno nº 2 passa e fecha cada segundo armário (isto é, fecha os armários de número par).

Depois, passa o aluno nº 3 e inverte a posição das portas (isto é, ela fecha as que estão abertas e abre as que estão fechadas) de cada terceiro armário, começando com armário de nº 3.

E assim por diante, ou seja, quando o k-ésimo aluno passa, ele inverte a posição das portas de cada k-ésimo armário, começando pelo armário de número k.

Depois da passagem do 100º aluno, quais armários estarão abertos?

1º ato: solução por computador

Na época, eu passava a maior parte do tempo na frente de uma tela de computador, a qual, normalmente, continha uma planilha Excel. Assim, a primeira ideia que me ocorreu foi resolver o problema com uma planilha.

Segundo o enunciado, a porta do n-ésimo armário teria sua posição invertida pelo k-ésimo aluno se e somente se n fosse um múltiplo de k. Assim, ficou claro que eu poderia usar a função MOD do Excel, cuja definição é:

MOD(n;k) = valor do resto na divisão euclidiana de n por k,

a fim de identificar os alunos cujos números k fossem divisíveis pelo número n do armário, ou seja, aqueles tais que MOD(n;k) = 0.

Representando as posições “fechada” e “aberta” de cada porta por 0 e 1, respectivamente, e chamando de X(n,k) a posição da porta do armário n após a passagem do aluno k, eu simplesmente programei a planilha com as condições iniciais:

X(n,0) = 0, para 1 n 100 (todos os armários fechados inicialmente)

e com a fórmula de recorrência:

X(n,k) = SE( MOD(n,k) = 0 ; 1 – X(n,k-1) ; X(n,k-1) ), para 1 n, k 100 (se k dividir n, então a posição da porta do armário n muda de 0 para 1 ou de 1 para 0; caso contrário, o posição da porta não se altera).

“Rodando” a planilha (ou seja, executando o programa), eu descobri que X(n,100) = 1 para n = 1, 4, 9, 16, 25, 36, 49, 64, 81 e 100. Para todos os demais valores de n, X(n,100) era igual a 0. Ou seja, após a passagem do 100º aluno, os únicos armários abertos seriam aqueles cujos números fossem quadrados perfeitos. O colega que havia proposto o problema confirmou que a solução estava correta, e a coisa ficou por isso mesmo.

2º ato: decomposição em fatores primos e o princípio multiplicativo

Algum tempo depois, folheando uma coletânea de problemas matemáticos, eu me deparei com o mesmo problema. Imediatamente me lembrei da solução por computador. No entanto, desta vez me ocorreu que, naquela ocasião, apesar de ter determinado corretamente quais armários estariam abertos, eu não havia, de fato, “resolvido” o problema. Eu havia descoberto a resposta, mas não sabia por que a resposta era aquela.

Pensando um pouco sobre o problema, concluí que:

1) os únicos alunos que inverteriam a posição da porta de número n seriam aqueles cujo número fosse um divisor de n;

e

2) como todas as portas começaram fechadas, as únicas que estariam abertas após a passagem dos alunos seriam aquelas cujas posições tivessem sido invertidas um número ímpar de vezes;

Isso quer dizer que os armários que estariam abertos após a passagem dos alunos seriam aqueles cujos números têm um número ímpar de divisores.

O primeiro fato já me havia ocorrido na época em que “resolvi” o problema com a planilha, pois foi a condição que usei no teste lógico da função SE do Excel. No entanto, não me lembro de ter, na época, pensado no segundo fato, apesar deste ser mais ou menos óbvio, pelo menos depois de alguma reflexão sobre o problema.

A simulação com a planilha havia mostrado que, dentre os números naturais de 1 até 100, os únicos com um número ímpar de divisores são os quadrados perfeitos. Como não vi nenhum motivo para que isso não valesse também para números naturais maiores do que 100, formulei a conjectura: “todos os números naturais possuem um número par de divisores, com exceção dos quadrados perfeitos, que possuem um número ímpar de divisores”.

Nesta época, eu já havia começado a estudar teoria dos números (um hobby barato e instrutivo!) e, desta forma, já conhecia a fórmula que expressa o número d(n) de divisores de um número natural n em função dos expoentes da decomposição canônica de n em fatores primos:

Se então d(n) = .

Esta fórmula é uma consequência simples do teorema fundamental da aritmética e do princípio multiplicativo da combinatória. Com base nela, é fácil ver que, se d(n) é ímpar, então cada fator (1 + ) deve ser ímpar, ou seja, cada expoente deve ser par, o que implica que n é um quadrado perfeito, pois cada um de seus fatores primos aparece na decomposição canônica com expoente par. Reciprocamente, se n for um quadrado perfeito, então cada expoente será par, o que por sua vez significa que cada fator (1 + ) será ímpar e, portanto, d(n) será ímpar. Isso demonstra a conjectura acima, a qual, portanto, é um teorema do qual decorre a solução do problema original.

Ou seja, agora o problema tinha uma solução matematicamente satisfatória, que explicava a resposta obtida por meio da planilha.

3º ato: partição em pares

Mas será que explicava mesmo?

Não há dúvidas de que o argumento acima, baseado na fórmula do número de divisores de n, mostra que a afirmação “dentre todos os números naturais, apenas os quadrados perfeitos possuem um número ímpar de divisores” é verdadeira. Mas não estou tão certo de que aquele argumento mostra por que ela é verdadeira. Ou seja, é um argumento que demonstra, mas que não explica, não ilumina. Uma das razões para isso é que, apesar de o teorema dizer respeito apenas aos divisores de um número, esta demonstração recorre a elementos que poderíamos chamar de “estranhos” ao problema: o princípio multiplicativo e a decomposição em fatores primos de um dado número, cuja unicidade, aliás, não é tão óbvia quanto pode parecer.

Assim, mesmo de posse de uma demonstração absolutamente correta, o fato é que eu ainda não havia capturado totalmente a “essência” do problema.

Mais alguns anos se passaram e, um belo dia, folheando o excelente Elementary Theory of Numbers, de William J. LeVeque [.], eu me deparei com a seguinte passagem:

“Considere, por exemplo, a afirmação de que d(n) é par a menos que n seja um quadrado perfeito. Isso pode ser provado da seguinte forma: Se d é um divisor de n, então o natural também o é. Se n não for um quadrado perfeito, então d . Caso contrário, teríamos n = : uma contradição. Logo, se n não for um quadrado perfeito, o conjunto de seus divisores pode ser particionado em pares da forma {d , }, de modo que cada divisor ocorre uma única vez como elemento de algum par. O número de divisores de n é, portanto, igual ao dobro do número de pares e, por ser o dobro de um número natural, é um número par.”

A partir disso, não foi difícil completar a demonstração: se n for um quadrado perfeito, basta separar a raiz quadrada de n e particionar os demais divisores em pares da forma acima. Isso mostra que um quadrado perfeito tem um número ímpar de divisores.

Agora sim! Finalmente uma demonstração que prova e que explica, que mostra que o teorema é verdadeiro e porque é verdadeiro. Em retrospecto, não surpreende que esta tenha sido uma demonstração combinatória, obtida por meio de uma reorganização adequada dos elementos do problema, e apenas eles, sem envolver elementos “estranhos”. Ou como o próprio William J. LeVeque explicou em seu livro: “Nós aplicamos aqui o princípio segundo o qual, ao contar inteiros que tenham uma certa propriedade, pode ser útil agrupá-los, inicialmente, de alguma forma judiciosamente escolhida.”

Antônio Cláudio Lage Buffara.

Ler 91 vezes Última modificação em Quinta, 05 Abril 2018 12:50
Antonio Claudio Lage Buffara

Me descrevo com um engenheiro, empresário e investidor mas com alma de matemático.

O blog é direcionado especialmente aos professores e estudantes de matemática. Tratará não só da matemática em si mas também do ensino da matemática, desde a escola (ensino fundamental) até a universidade.

Deixe um comentário

Certifique-se de preencher os campos indicados com (*). Não é permitido código HTML.