Semafori in fila

[Franchifis]

Ci sono n semafori in serie, uno accanto all'altro. Ogni semaforo ha due luci: rossa e verde. Faccio partire un cronometro: all'istante iniziale tutti i semafori hanno la luce verde accesa, ma dopo n minuti dall'inizio l'n-esimo semaforo diventa rosso, per poi tornare verde il minuto successivo, poi dopo altri n minuti di nuovo rosso per un solo minuto, e così via. Per esempio:
0. All'istante iniziale tutti i semafori sono verdi. (V V V V V ...)
1. Dopo 1 minuto il primo semaforo diventa rosso, gli altri non cambiano. (R V V V V ...)
2. Dopo 2 minuti dall'inizio il primo semaforo torna verde e il secondo diventa rosso. (V R V V V ...)
3. Dopo 3 minuti dall'inizio il primo semaforo diventa rosso, il secondo verde, il terzo rosso. (R V R V V ...)
4. Dopo 4 minuti dall'inizio il primo semaforo torna verde, il secondo è ancora verde, il terzo torna verde, il quarto diventa rosso, e gli altri ancora sono verdi. (V V V R V ...)
5. (R R V V R ...)
...

Le domande sono:
(i) Dopo quanti minuti si stabilisce un periodo?
(ii) Delle $ 2^n $ configurazioni ce n'è qualcuna che non comparirà mai (potrebbe dipendere da n)?
(iii) Quante volte all'interno del periodo accade che tutti i semafori siano verdi?

Al lavoro!

[edriv]

Non so se ho capito bene, però:
- dopo n minuti si stabilisce un periodo che dura 2 minuti, cioè tutti cominciano a lampeggiare
- per n>1 ce ne sono sempre (ad esempio due semafori rossi vicini)
- mai

però evidentemente è troppo semplice, non è che hai dimenticato di spiegare qualcosa?

[Franchifis]

Ehm, no. Hai interpretato il problema in maniera completamente diversa. Ho ampliato il testo, ora dovrebbe essere più chiaro.

[piever]

Un periodo si stabilisce dopo $ m $ minuti dove m è il mcm tra tutti gli interi $ i $ tali che $ 2 \leq i \leq (n+1) $
Ci sono alcune configurazioni che non compariranno mai se $ n>2 $ (ad esempio non accadrà mai che il primo semaforo sia verde e il terzo rosso perche dovrebbe passare un numero di minuti che sia 0 in mod 2 e allo stesso tempo 3 in mod 4)
Durante un periodo capita che tutti i semafori siano verdi almeno in una circostanza, cioè dopo $ m-2 $ minuti.
P.S. C'è ancora qualcosa a cui non ho risposto?

[mattilgale]

mah...
allora...

1. penso che ci sia da dire quante combinazioni non compariranno mai...

2.
in un periodo accade che i semafori siano tutti verdi $ \phi(m) $ volte
infatti i semafori sono tutti verdi quando sono passati i minuti ed i è primo con tutti gli interi 2<=k<=n+1... infatti il k-esimo semaforo è rosso ogni k+1 minuti quindi tutti i semafori sono verdi dopo t minuti se e solo se t non è divisibile per nessuno degli interi da 2 ad n... quindi in $ \phi (m) $ casi...
sono stato abbastanza abbreviatore ma il ragionamento dovrebbe tornare

[piever]

1. penso che ci sia da dire quante combinazioni non compariranno mai...

Il fatto è che non so come si determinano con esattezza, ma nella domanda chiedeva solo se ce ne fossero.

2. in un periodo accade che i semafori siano tutti verdi $ \phi(m) $ volte

Cosa si intende con $ \phi $?

Comunque il tuo ragionamento non torna, ad esempio con 3 semafori al quarto turno sono tutti e 3 verdi ma $ 2|4 $ ...

In realtà i semafori sono tutti verdi dopo $ i $ minuti dove $ i $ non corrisponde a $ -1 $ (mod k) dove $ 2 \leq k \leq (n+1) $ ma, pur sapendo questo, non riesco a determinare quanti $ i $ esistano.

[mattilgale]

mi sa che ho indicato malissimo il trascorrere dei minuti
tra parentesi metto il numero con il quale tornano tutte le mie farneticazioni

0.(1) VVV
1.(2) RVV
... VRV
... RVR
... VVV
...
...

con qualche ritocco comunque i miei ragionamenti dovrebbero tornare lo stesso... ora non ho il tempo di controllare...

comunque $ \phi(m)=\left|\{x:x<m,\ MCD(x,m)=1,\ x\in\mathbb{N}\}\right| $
cioè il numero dei naturali minori di m e primi con esso

[piever]

Sì, basta qualche ritocco. Per determinare i basta che (i+1) sia primo con m e minore di esso, quindi la risposta $ \phi(m) $ è in ogni caso giusta. Invece passiamo alle configurazioni impossibili: basta che ci siano 2 numeri compresi tra 2 e (n+1) tali che uno divide l'altro e non potrà mai accadere che il minore di essi sia verde e il maggiore rosso. In termini matematici se $ (n+1)\ge(b)>a\ge 2 $ e $ b|n $ allora dopo che sono trascorsi x minuti se x=-1 mod b (quindi b è rosso) evidentemente x=-1 mod a (quindi anche a è rosso). Perciò non può accadere che a sia verde e b rosso. Quindi il numero di configurazioni impossibili equivale al numero di coppie a,b tali che $ (n+1)\ge(b)>a\ge 2 $ e $ b|n $

Detto questo, sembrerebbe tutto risolto