SOLUZIONE

Dopo il passaggio del 100-esimo studente (e se nessuno prima avrà scoperto la logica) rimarranno accese soltanto le 10 lanterne contrassegnate da numeri naturali che siano quadrati perfetti (escluso lo 0 che non è considerato nel testo del quesito).

Precisamente: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100

• Che legame c'è fra il risultare accesa o spenta della singola lanterna alla fine e il numero degli studenti che l'avranno sfiorata, cioè ne avranno modificato lo stato (accesa/spenta)? 

• Quali caratteristiche hanno in comune gli studenti che l'avranno sfiorata?

• A cosa corrisponde il numero di volte in cui sarà stata sfiorata?

L'alternanza di accensione e spegnimento per la singola lampada implica che ogni lampada alla fine risulterà:

• accesa se avrà subito un numero dispari di incantesimi (accensioni/spegnimenti);

• spenta  se avrà subito un numero pari di incantesimi (accensioni/spegnimenti).

Inoltre, si nota che il numero di accensioni/spegnimenti di ogni lampada altro non è che il numero di divisori del numero che la contrassegna.

Il quesito diventa perciò stabilire quali numeri naturali fra 1 e 100 abbiano un numero dispari di divisori.

SOLUZIONE 1

Come abbiamo già visto, ogni numero naturale può essere espresso come prodotto di 2 suoi divisori: infatti, se d è un divisore di n, anche il quoziente n/d deve essere un divisore di n: e si ha che n =  d   ∙  n/d

Quindi per ogni numero naturale n si possono elencare tutte e sole le coppie distinte di divisori che, moltiplicati fra loro, producono n, facendo variare come primo elemento della coppia tutti i divisori: il numero delle coppie coincide perciò con il numero dei divisori di n.

Esempio: n = 12

Elenchiamo le coppie di divisori di 12 il cui prodotto sia 12:

1 ∙ 12 = 12

2 ∙ 6 = 12

3 ∙ 4 = 12

e, commutando i fattori, anche:

12 ∙ 1 = 12

6 ∙ 2 = 12

4 ∙ 3 = 12

Abbiamo ottenuto in totale 3 ∙ 2 = 6 coppie di divisori, cioè un numero pari di divisori.

Cosa succede se il numero naturale n è un quadrato perfetto?

Esempio: n = 16

Elenchiamo le coppie di divisori di 12 il cui prodotto sia 12:

1 ∙ 16 = 16

2 ∙ 8 = 16

4 ∙ 4 = 16

e, commutando i fattori, anche:

16 ∙ 1 = 16

8 ∙ 2 = 16

4 ∙ 4 = 16

Abbiamo ottenuto in totale 3 ∙ 2 = 6 coppie di divisori, ma 4 si appaia con se stesso e la coppia 4 ∙ 4 = 16 figura 2 volte, poiché la commutatività lascia invariati termini identici; le coppie distinte sono perciò 5 in tutto, cioè i divisori sono in numero dispari (1, 2, 4, 8, 16).

In sintesi: in tutti i quadrati perfetti n e solo in loro esiste un divisore che, moltiplicato per se stesso, produca n (la sua radice quadrata). Questo divisore rompe la simmetria delle coppie e rende il totale dispari.

SOLUZIONE 2

Abbiamo visto come dedurre il numero dei divisori di un naturale n a partire dalla sua scomposizione in fattori primi: è il prodotto degli esponenti dei fattori primi, ciascuno aumentato di 1. 

Consideriamo, per esempio, un numero n così scomposto in fattori primi:

card (D(pa ∙ pb ∙ pc)) = (a + 1)(b + 1)(c + 1)

Quando questo prodotto è dispari?

Sappiamo che il prodotto di numeri interi è dispari se e solo se tutti i suoi fattori sono dispari: occore e basta, infatti, che un fattore sia pari affinché il prodotto sia pari.

Ora: a + 1 è pari se e solo se a è dispari e vale lo stesso per b e c.

Quindi, affinché il numero dei divisori del naturale n sia dispari, tutti gli esponenti a, b e c dei suoi fattori primi devono essere pari.

Questo significa che possiamo dividere ogni esponente per 2 e, per le proprietà delle potenze,  riscrivere:

n = (pa/2 ∙ pb/2 ∙ pc/2)2

n è, quindi, un quadrato perfetto.