Newsgroup: it.hobby.enigmi
Titolo: i 100 lampioni

supponiamo di avere una strada con 100 lampioni, tutti spenti.
ogni lampione ha un pulsante, se lo premi quando e' spento il lampione
si accende, se lo premi quando e' acceso lampione si sgegne.
passa sulla strada un primo uomo che preme il pulsante nei lampioni
multipli 1 (tutti).
poi un secondo uomo che preme il pulsante nei lampioni multipli di 2.
un terzo uomo i multipli di 3 e cosi' via fino a 100 uomini.
qual'e la situazione dei lampioni (accesi/spenti) dopo il centesimo
uomo?
porkyporkus

 uomo?
Ci hanno arrestati tutti e 100 con accuse varie tra cui turbamento
dell' ordine pubblico, vandalismo, e pure gara di velocita' non
autorizzata (avevo detto a tutti di andare piu' in fretta possibile
per rispondere per primo).
Attendo risultato dalla mia cella, mi dicono che verremo liberati se
qualcuno dara' la soluzione esatta
PS- Ho rinunciato a chiamare il mio avvocato in cambio di questa email
al NG, ho fatto bene?
fulvio


SPOILER
Rimarranno accesi solo quei lampioni attivati un numero dispari di volte.
Ciascun pulsante viene premuto un numero di volte pari al numero dei 
divisori del lampione corrispondente. es il lampione numero 10 cambia stato 
con le persone 1,2,5,10.
Gli unici interi con un numero dispari di divisori sono i quadrati:
1,4,9,16,25,36,49,64,81,100.

 ha scritto nel messaggio
news:3E8C984A...@uriland.it...

WOW!  Sono libero!  Grazie Dario!
ciao
fulvio

 ha scritto nel messaggio
news:3E8C984A...@uriland.it...


Ok, e' chiaro!
il numero e' scisso in un prodotto m x n, e quindi ho sempre un numero pari
di divisori, perche' c'e' una coppia.
Solo nel caso di quadrati perfetti ho n x n e quindi non una coppia ma un
solo divisore n che quindi porta il numero dei divisori ad essere dispari.
Io ho provato a fare un foglio in excel ed ho notato che effettivamente solo
i lampioni quadrati perfetti si accendono.
Ed ovviamente la cosa e' indipendente dal numero dei lampioni, perche' solo
le prime n persone possono toccare l'interruttore dell'ennesimo lampione,
sempre coppie tranne nel caso dei quadrati perfetti, ove la persona radice
di enne fa la differenza e non ha un altra persona corrispondente all'altro
divisore che ristabilisca lo stato del lampione.
Ciao.
Uahlim vel ~Uahlim!

Uahlim vel ~Uahlim! <ti....@liver.oilime> wrote in message
LD3ja.54485$Jg1.1...@news1.tin.it...

ma allora ci sei pure tu su questo ng :-) ciaoooo

 > uomo?
Spero di non aver fatto errori
Accesi:1, 4, 9, 16, 25, 36, 49, 64, 81, 100
Spenti tutti gli altri
Infatti questi sono gli unici numeri aventi un nuero dispari di
fattori (considerando anche 1)

...

Ho ottenuto la stessa soluzione, ma sono andato a contare i numeri che
avevano un numero dispari di divisori. Ora tu dici che se N è un
quadrato allora ha un numero dispari di divisori, scusami ma questa
implicazione non mi sembra evidente, sono dubbioso

 ha scritto nel messaggio
news:de1c8286.03040...@posting.google.com...

Dunque se un numero p ha un divisore d e' perche' e' esprimibile come
prodotto di divisore d e quoziente q, cioe' p=q*d.
Quindi se il numero non e' un quadrato perfetto ha sempre 2*n divisori ove n
e' il numero di coppie quoziente divisore possibili.
Solo se il numero e' un quadrato perfetto si ha il caso in cui quoziente e
divisore sono lo stesso numero e quindi non si ha una coppia di divisori ma
un solo divisore.
Spero che ora sia chiaro.
Esempio:
64 si esprime come 8*8, come 16*4, come 32*2 e come 64*1, quindi i divisori
sono 8, 16 e 4, 32 e 2, 64 e 1 cioe' ci sono 4 prodotti che danno pero' a 3
coppie di divisori ed ad 1 divisore UNICO 8.
nel caso di numeri che non sono quadrati perfetti i possibili prodotti non
possono essere con un solo divisore, ma sempre con due e quindi si hanno
sempre coppie di divisori corrispondenti ai prodotti.
Esempio 2:
48 si esprime come 12*3, 6*8, 3*16, sempre quindi con coppie di divisori e
quindi il numero di divisori e' pari.
Se si potesse esprimere come n*n sarebbe un quadrato perfetto.
Ora dovrebbe essere chiaro.
Ciao.
Uahlim vel ~Uahlim!

 > quadrato allora ha un numero dispari di divisori,
Non lo dico io, o meglio il primo a dirlo e' stato Dario Uri.
Io ci ho ragionato e confermo questo fatto con la spiegazione dei prodotti
che generano le coppie di divisori tranne nel caso in cui il prodotto abbia
gli stessi fattori (quadrato perfetto).
Ma anch'io avevo fatto come te con un foglio excel.
Ciao.
Uahl!

uomo?
Secondo me sono tutti spenti: mi stupirei se, dopo tanti
accendi/spengi, le lampadine non si bruciassero....
:-))))))))
Robby
-
**** Per risposte private: cancellare TUTTE le "x" dal mio address ! ****
**** To reply privately: delete ALL the "x" from my address ! ****

 accendi/spengi, le lampadine non si bruciassero....
Non sono alla fine grandi numeri!
;-)))
Ciao.
Uahlim vel ~Uahlim!

 > > > >
...
M'hai sfondato la rotella del mouse :)
Qualche sforbiciatina qua e là, per pietà.
--
Ciao, Silv:o)

ecco un programmino in python che visualizza lo stato dei lampioni a ogni
passaggio.
e' interessante vedere che quando il numero di lampioni e' il  quadrato di
un numero n, si raggiunge la situazione che avete descritto esattamente in
n passi.
ma quando il numero di lampioni *non e'* un quadrato, si raggiunge lo
stesso la situazione descritta (i lampioni accesi sono quelli di posto
uguale a 1, 4, 9,,, ma in un numero inferiore di passi...)
ci sto studiando sopra...
ciao ciao,
           vanni
# Gioco dei lampioni
#
# Si hanno n lampioni inizialmente tutti spenti
#
# Il procedimento si effettua in n passi cosi' definiti:
#
# Al passo 1 tutti i lampioni vengono accesi
# Al passo 2 vengono accesi (spenti) i lampioni di posto alternato (1,3,,,)
# Al passo 3 vengono accesi (spenti) i lampioni di posto 1,4,7...
# La simulazione mostra lo stato dei lampioni dopo m passi
############################################################################
# Dichiarazione e inizializzazione lista
# 0: lampione spento, 1: lampione acceso
L=[0]
L=L*100
n=len(L)
print "Dimensione problema: ",n
for i in range(0,n):         
        print "Passo ", i+1,
#        print ": inversione di ",
#        print int(n/(i+1)), "elementi ",
        for j in range(0,int(n/(i+1))):
#                print (i+1)*(j+1),   # posizioni degli elementi da
invertire
                L[(i+1)*(j+1)-1]=not(int(L[(i+1)*(j+1)-1]))     #
inversione
        print "\n",L
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

 ha scritto nel messaggio
news:e7ce352a.03040...@posting.google.com...

Sono spenti i lampioni numero 100, 81, 64, 49, 36, 25, 16, 9, 4 e 1. Gli
altri sono accesi.... Spero sia cosě :)

Dò una risposta algoritmica:
Se è n il numero di lampioni o bit con un qualsiasi stato di partenza
noto.
Il numero di inversioni di stato per ogni intero i in [1..n] è dato
dal numero di divisori interi di i. Ora se questo numero è pari, lo
stato rimane quello di partenza mentre si inverte nel caso il numero
di divisori sia dispari.
Costruire adesso un algoritmo in qualsiasi linguaggio diventa quasi
prosaico...
Saluti