GIochino di logica...

[glc2]

Buongiorno!!!! Chi mi aiuta?

La scuola "Viva la logica" ha un direttore al quale piace il pensiero creativo ed il giorno inaugurale del corso fa la seguente presentazione: "Nella scuola ci sono 1000 alunni e 1000 armadietti"
Il direttore chiede al primo alunno di aprire tutti gli armadietti.
Dopo dice al secondo di chiudere gli armadietti pari.
Al terzo alunno chiede di "cambiare lo stato"(se aperto chiude, se chiuso apre) agli armadietti 3, 6, 9, ecc.
Al quarto chiede di "cambiare lo stato" agli armadietti 4, 8, 12, ecc.
E cosi fino al millesimo alunno. Dopo questa cerimonia, quanti armadietti saranno aperti?

[Gi81]

$31$?

[Gi81]

Prova a ragionare così: prendiamo ad esempio l'armadietto numero $12$
Alla fine sarà aperto o chiuso? Perchè?

Prova a rispondere a queste domande e poi dovresti arrivare alla soluzione

[krek1]

100 li ho contati tutti sono sicuro al 100x100

Credo ...

ops mi son confuso credevo fossero 10000 armadietti

si son proprio quanti dici tu Gi8

[glc2]

Il problema è che non riesco ad impostare il ragionamento...

[Gi81]

Prova a risolvere cio' che ti ho chiesto prima:

"Gi8":prendiamo ad esempio l'armadietto numero $12$
Alla fine sarà aperto o chiuso? Perchè?

Prova a rispondere a queste domande e poi dovresti arrivare alla soluzione

[paperino001]

il 12 sarà chiuso ?

[Gi81]

Esatto! Il $12$ sarà chiuso.
In generale, qual è il criterio per stabilire se l'armadietto $n$ sarà aperto o chiuso?

[paperino001]

Forse bisogna trovare una relazione tra i numeri pari, i multipli di 3 e quelli di 4....

[Injo]

Se consideriamo tutti gli armadietti aperti, credo che ad ogni armadietto venga cambiato lo stato tante volte quant'è la somma degli esponenti della fattorizzazione standard della sua posizione. In particolare alla fine saranno aperti quelli che risultano avere tale somma pari. A questo punto credo si possa raggiungere il risultato con tecniche combinatorie, ma non ho provato

[Lord K]

Osserviamo che è un bel modo per leggere il crivello di Eratostene. Infatti credo che la soluzione sia 1000 meno il numero di primi minori di [tex]1000[/tex], infatti se consideriamo un numero [tex]n[/tex] questo viene aperto e chiuso un numero di volte pari ai suoi divisori, ovvero [tex]\sigma_0(n)=\sum_{d\mid n} 1=n-\phi(n)[/tex], dove [tex]\phi(n)[/tex] sono i numeri coprimi con [tex]n[/tex].

Da osservare che un primo ha [tex]\sigma_0(p)=\sum_{d\mid p} 1=2[/tex], ovvero il primo alunno li apre tutti e vengono chiusi solo dopo il passaggio [tex]p[/tex]-esimo. Da dire allora che il massimo valore di porte aperte deve essere [tex]1000[/tex] meno il numero di primi.

[Gi81]

"glc":Il direttore chiede al primo alunno di aprire tutti gli armadietti.
Dopo dice al secondo di chiudere gli armadietti pari.
Al terzo alunno chiede di "cambiare lo stato"(se aperto chiude, se chiuso apre) agli armadietti 3, 6, 9, ecc.
Al quarto chiede di "cambiare lo stato" agli armadietti 4, 8, 12, ecc.
E cosi fino al millesimo alunno. Dopo questa cerimonia, quanti armadietti saranno aperti?

Per avere una comprensione migliore, suggerisco di vedere il problema nel seguente modo.
All'inizio tutti e $1000$ gli armadietti sono chiusi.

passaggio 1: cambiare stato a tutti gli armadietti che sono divisibili per $1$ [ovvero tutti]
passaggio 2: cambiare stato a tutti gli armadietti che sono divisibili per $2$
passaggio 3: cambiare stato a tutti gli armadietti che sono divisibili per $3$
.
.
.
passaggio k: cambiare stato a tutti gli armadietti che sono divisibili per $k$
.
.
.
passaggio 999: cambiare stato a tutti gli armadietti che sono divisibili per $999$
passaggio 1000: cambiare stato a tutti gli armadietti che sono divisibili per $1000$

Si nota velocemente che se un armadietto cambia stato un numero pari di volte, allora alla fine sarà chiuso.
Se invece esso cambia stato un numero dispari di volte, allora alla fine sarà aperto.


Prendiamo il caso dell'armadietto numero $12$. Quante volte cambierà stato?
Cambierà stato nei passaggi $1,2,3,4,6,12$. Dunque $6$ volte in tutto [tante quanti sono i suoi divisori]
Dunque l'armadietto $12$ sarà chiuso, perchè cambia stato un numero pari di volte.

Da questo esempio possiamo capire che
se $n$ ha un numero pari di divisori, allora l'armadietto $n$ sarà chiuso alla fine;
viceversa,
se $n$ ha un numero dispari di divisori, allora l'armadietto $n$ sarà aperto alla fine;

Per esempio, tutti gli armadietti che hanno come numero un numero primo saranno chiusi (perchè i numeri primi hanno 2 divisori)

Quali sono i numeri tra $1$ e $1000$ che hanno un numero dispari di divisori?
Lascio a voi la risposta