100 cacifos — número par ou ímpar de divisores do inteiro n

O Prof. Antero Neves, no artigo Um pouco de Matemática n.º 0, publica um link para o número zero do “jornal” escolar com o mesmo nome e do qual é autor, onde aparece o seguinte desafio, que aqui reproduzo com a sua autorização:

« Imagine-se um corredor com 100 cacifos, numerados de 1 a 100. Quando passa o primeiro estudante, ele abre todos os cacifos, quando passa o segundo, ele fecha todas as portas pares, quando o terceiro passa, ele muda o estado das portas cujo número é múltiplo de 3, ou seja, as abertas são fechadas e as fechadas passam a estar abertas. Isto continua até passar o centésimo aluno. Quais as portas que permanecem abertas no final? »

Uma possível abordagem ao problema  pareceu-me ser a que passo a descrever.  Pelo enunciado ficamos a saber:

1. No início todos os cacifos estão fechados.

2. Os estudantes passam pelos cacifos por ordem crescente de n, desde n=1 a n=100.

3. O estudante de ordem n muda o estado das portas cujo número é múltiplo de n, não mexendo nas restantes.

Vejamos dois exemplos.

A – Quais são os estudantes que mudam o estado da porta 16?

São os de número de ordem 1, 2, 4, 8 e 16, ou seja, os divisores de 16. Como há um número ímpar de divisores, a porta 16, no final, está aberta (1 – abre, 2 – fecha, 4 – abre, 8 – fecha e 16 abre).

Notemos que os cinco divisores de 16 dão origem às seguintes decomposições num produto de dois factores: 1×16, 2×8 e 4×4 (3 pares de factores; o 4 aparece duas vezes)

B – Quais os que  mudam o estado da porta 18?

Os de número de ordem 1, 2, 3, 6, 9 e 18. Neste caso, em que há um número par de divisores, esta porta,  no final, está fechada (1 – abre, 2 – fecha, 3 – abre, 6 – fecha, 9 – abre e 18 – fecha).

Agora as possíveis factorizações são: 1×18, 2×9, 3×6 (3 pares de factores; nenhum se repete)

Podemos generalizar, pensando no número de divisores de n. Se ímpar, a porta n fica aberta, se par, fechada. Basta agora apercebermo-nos que apenas os quadrados perfeitos têm um número ímpar de divisores, porque um dos divisores aparece duas vezes,  para concluirmos que as portas abertas, no final, são as 1, 4, 9, 16, 25, 36, 49, 64, 81 e 100.

Adenda de 30-4-2009: no número 1 de Um pouco de Matemática encontra-se  a explicação do autor

[1-5-2009: alterado título]

Nova adenda de 6-1-2011:   Motivado pelo comentário de Anabela Vieira, decidi inserir as duas sondagens seguintes (os links iniciais já não existem, mas lembro-me que a interpretação do enunciado era a que lhe dei):

 

Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer
Esta entrada foi publicada em Enigmas, Matemática com as etiquetas , , . ligação permanente.

9 respostas a 100 cacifos — número par ou ímpar de divisores do inteiro n

  1. The short proof you showed that demonstrates why squares have an odd number of divisors is a nice one. Indeed, all the divisors of any square, n^2, can be paired up except n itself. This is because if d|n^2, then there exists another divisor k such that dk = n^2 and k > n. Hence, any square has an odd number of divisors.

    There is, of course, another simple proof, which however is not as elegant as the one above. Any square n^2 must be of the form p_1^{2m_1} \cdot p_2^{2m_2} \cdots p_k^{2m_k} for primes p_1, p_2, \ldots , p_k and positive integers m_1, m_2, \ldots , m_k. Then, any divisor of n^2 is obtained by suitably varying the exponent of p_i from 0 to 2m_i (2m_i + 1 choices) for 1 \leq i \leq k. Therefore, the number of divisors is equal to (2m_1 + 1) (2m_2 + 1) \cdots (2m_k + 1), which of course is an odd integer. And, we are done! (Yeah, not a very inspiring proof!)

    • Vishal,

      I’d thought about the proof you wrote (or a variant) but I avoided it because this problem appears in the “Um pouco de Matemática” School Journal for the 7th/8h grades, I think.

      The main idea of the pairs of divisors occurred to me only after some time.
      Thanks!

  2. Américo,

    Thanks, you got it right! :-) For some reason my LaTeX code containing the letter ‘e’ wasn’t being rendered correctly. The letter ‘e’ just didn’t show up, earlier. Let me just write it in plain text one last time (using a different letter) and also let me correct one more error in the 2nd paragraph.

    1st paragraph: This is because if d|n^2, then there exists another divisor ‘k’ such that dk = n^2 and k > n.

    2nd paragraph, 3rd line: … for 1 <= i <= k.
    —–

    Ah, you already had the proof (I wrote) in your mind. I guess I needlessly wrote my comment! :-) Thanks, anyway!

    [Previous comments concerning typos deleted] A Tavares

  3. Anabela Vieira diz:

    Este problema induz-nos em erro. O facto de continuar até passar o centésimo aluno, não nos leva a aferir que o 4º aluno, possivelmente mudará os múltiplos de 4.
    Eu e as minhas colegas, tentámos resolver e todas deduzimos que o 4ºaluno, quando passasse iria abrir novamente todas as portas. É meramente uma questão de Português, mas que na minha opinião se torna relevante neste caso. Penso, que se poderia incluir no enunciado:
    “o 4º aluno quando passa muda o estado de todos os múltiplos de 4 e, assim sucessivamente.”
    Assim, penso que nos levasse a pensar nos múltiplos e não num ciclo.

    • Subentendi que inicialmente todos os cacifos estavam fechados. Sabemos que o primeiro estudante abre todos os cacifos. Por isso, mudaria o estado de todas as portas, ou dito de outra forma, mudaria o estado das portas cujo número é múltiplo de 1. Sabemos que o segundo fecha todas as portas pares, isto é, mudaria o estado das portas cujo número é múltiplo de 2. Sabemos que o terceiro muda o estado das portas cujo número é múltiplo de 3.

      O que significa “Isto continua até passar o centésimo aluno.”? Com a interpretação que dei ao que ocorreria quando passasse o primeiro, segundo e terceiro alunos, pareceu-me natural pensar que o quarto mudaria o estado das portas cujo número é múltiplo de 4, quando o quinto passasse, iria mudar o estado das portas cujo número é múltiplo de 5, etc., o que corresponde exactamente ao sentido da sugestão, “o 4º aluno quando passa muda o estado de todos os múltiplos de 4 e, assim sucessivamente”.

      A questão de haver um ciclo repetitivo de período igual a 3, em que os alunos 1, 4, 7, …, 97, 100 abririam todas as portas, os alunos 2, 5, 8, …, 95, 98 fechariam todas as pares, e os alunos 3, 6, 9, …, 96, 99 mudariam o estado das portas cujo número é múltiplo de 3, parece-me ser uma interpretação possível, mas mais rebuscada, até pelo facto de o número total de alunos, que é 100, não ser múltiplo de 3.

      Mas, claro que, quando é necessário inferir uma lei geral a partir dos primeiros casos exemplificativos, há sempre a possibilidade de obter interpretações diferentes. É o que pode acontecer com as sucessões definidas não pelo termo geral, mas só pelos primeiros termos. Uma boa regra, parece-me ser, partir do princípio que a lei geral é a mais simples possível que é compatível com os exemplos fornecidos.

    • No seguimento do seu comentário, que agradeço, coloquei duas sondagens, a propósito da interpretação do enunciado.

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s