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):

 

Congruences and Divisibility — A Purdue University Problem

pdf: ver caderno

Versão portuguesa aqui

PROBLEM OF THE WEEK, Problem No. 12 (Spring 2009 Series):

Problem. For how many positive integers x\leq 10,000 is 2^{x}-x^{2} not divisible by 7?

Justify your answer without the use of computers.

Here is my solution (accepted).

If a\equiv b\quad \left( \text{mod }m\right) , then a^{n}\equiv b^{n}\quad\left( \text{mod }m\right) . Applied to 2^{n} this property gives in general for n=3k+s,1\leq s\leq 3,0\leq k

2^{n}\equiv 2^{s}\quad\left( \text{mod }7\right) ,\quad (1)

which means that the remainders of the division of 2^{n} by 7 form a periodic sequence of length 3 starting at n=1

\overset{\text{period}}{\overbrace{2,4,1}},\overset{3\text{ terms}}{\overbrace{2,4,1}},\ldots .

As for n^{2} since (a) if a\equiv b\quad \left( \text{mod }m\right) and c\equiv d\quad \left( \text{mod }m\right) , then a+c\equiv b+d\quad \left( \text{mod }m\right) and (b) if a\equiv b\quad \left( \text{mod }m\right) , then a^{2}\equiv b^{2}\quad \left( \text{mod }m\right) , we have in general for n=7j+r,1\leq r\leq 7,0\leq j

n^{2}\equiv r^{2}\quad\left( \text{mod }7\right)\quad (2)

which means that the remainders of the division of n^{2} by 7 form a periodic sequence of length 7 starting at n=1

\overset{\text{period}}{\overbrace{1,4,2,2,4,1,0}},\overset{7\text{ terms}}{\overbrace{1,4,2,2,4,1,0}},\ldots .

If a\equiv b\quad \left( \text{mod }m\right) and c\equiv d\quad \left( \text{mod }m\right) , then a-c\equiv b-d\quad \left( \text{mod }m\right) . Let u_{n}=2^{n}-n^{2}. Therefore from (1) and (2) we have

u_{n}\equiv 2^{s}-r^{2}\quad \left( \text{mod}7\right) .\quad (3)

The remainders of the division of u_{n} by 7 form another periodic sequence of length 21=\text{lcm}(3,7) which starts also at n=1. Four examples of the evaluation of these remainders are presented below.

For 1\leq n\leq 21 the following 15 terms are not divisible by 7:

u_{1},u_{3},u_{7},u_{8},u_{9},u_{11},u_{12},u_{13},u_{14},u_{16},u_{17},u_{18},u_{19},u_{20},u_{21}.

Hence for 1\leq n\leq 9996=21\times \left\lfloor \dfrac{10000}{21}\right\rfloor , there are 15\times\left\lfloor \dfrac{10000}{21}\right\rfloor =7140 terms that are not divisible by 7.

From the remaining 4 terms u_{9997} and u_{9999}  are not divisible by 7, which gives a total of 7140+2=7142 numbers u_{n}=2^{n}-n^{2} not divisible by 7.

Four examples of the evaluation of the remainders:

u_{9}=2^{9}-9^{2}

(9=3\times 2+3,s=3,9=7\times 1+2,r=2)

2^{9}\equiv 2^{3}\quad\left(\text{mod }7\right) \equiv 1\quad\left(\text{mod }7\right)

9^{2}\equiv 2^{2}\quad\left(\text{mod }7\right) \equiv 4\quad\left(\text{mod }7\right)

u_{9}\equiv 2^{3}-2^{2}\quad\left(\text{mod }7\right) \equiv -3\quad\left(\text{mod }7\right)

u_{10}=2^{10}-10^{2}

(10=3\times 3+1,s=1,10=7\times 1+3,r=3)

2^{10}\equiv 2^{1}\quad\left(\text{mod }7\right) \equiv 2\quad\left(\text{mod }7\right)

10^{2}\equiv 3^{2}\quad\left(\text{mod }7\right) \equiv 2\quad\left(\text{mod }7\right)

u_{10}\equiv 2^{1}-3^{2}\quad\left( \text{mod }7\right)\equiv 0\quad\left( \text{mod }7\right)

u_{9997}=2^{9997}-9997^{2}

(9997=3\times 3332+1,s=1,9997=7\times 1428+1,r=1)

2^{9997}\equiv 2^{1}\quad\left(\text{mod }7\right) \equiv 2\quad\left(\text{mod }7\right)

9997^{2}\equiv 1^{2}\quad\left(\text{mod }7\right) \equiv 1\quad\left(\text{mod }7\right)

u_{9997} \equiv 2^{9997}-9997^{2}\quad \left( \text{mod}7\right) \equiv 1\quad \left( \text{mod }7\right)

u_{9998}=2^{9998}-9998^{2}

(9998=3\times 3332+2,s=2,9998=7\times 1428+2,r=2)

2^{9998}\equiv 2^{2}\quad\left(\text{mod }7\right) \equiv 4\quad\left(\text{mod }7\right)

9998^{2}\equiv 2^{2}\quad\left(\text{mod }7\right) \equiv 4\quad\left(\text{mod }7\right)

u_{9998} \equiv 2^{9998}-9998^{2}\quad \left( \text{mod}7\right) \equiv 0\quad \left( \text{mod }7\right)

Remark: typos corrected. [In the 2nd. last paragraph before the examples: “there are”  added]

Edited: May 29, 2009: Portuguese version removed and posted here