Le luci dell'hotel

[Pianoth]

In un hotel con $N$ stanze numerate da $1$ a $N$, ciascuna stanza ha una luce che può essere rossa, verde o blu. Inizialmente, tutte le luci sono rosse. Arrivano $N$ ospiti all'hotel, ed ogni ospite $k$, in ordine, entra in tutte le stanze i cui numeri sono multipli di $k$ e cambia il colore della luce avanzandolo di $k$ posizioni nella sequenza rosso → verde → blu → rosso. Tuttavia, se la luce è verde quando l’ospite lascia la stanza, un gatto dispettoso la riporta a rossa.

Dimostrare che, alla fine del passaggio di tutti gli ospiti, tutte le stanze numerate $27 \mod 2025$ avranno la luce rossa.

Si tratta di un piccolo problema che ho inventato, di cui ho anche una soluzione. L'ho trovato piuttosto interessante, quindi ve lo lascio come esercizio (o per divertimento). Qualora nessuno riuscisse a risolverlo entro qualche settimana, proporrò la mia dimostrazione.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Chiaramente nella stanza \(1 \leq m \leq N \) entrano tutti e solo gli ospiti \(k\) che sono divisori di \(m\). Inoltre notiamo che in base alle regole, se \(k \equiv 0 \mod 3\) allora il colore dela stanza non cambia, se \(k \equiv 1 \mod 3 \) il colore da rosso diventa verde e torna rosso per via del gatto. Da verde diventa blu, ma ci accorgiamo facilmente che siccome inizialmente tutte le stanze sono tutte rosse non è possibile che un ospite entri nella stanza e trovi la luce verde poiché se un certo ospite la rende verde il gatto la farà tornare rossa. Infine da blu diventa rossa. Se invece \(k \equiv 2 \mod 3 \) da rosso diventa blu. Da verde diventa rossa (ma non è possibile per lo stesso discorso di prima), e da blu diventa verde e per via del gatto diventa rossa.

In altre parole i divisori \(k\) multipli di 3 non cambiano lo stato della luce, i divisori \(k \equiv 1 \mod 3 \) trasformano il colore solo in rosso (poiché lo stato iniziale di verde non è possibile), mentre se \(k \equiv 2 \mod 3 \) invertono il rosso e il blu. Inizialmente sono tutte rosse, poi siccome \(1 \mid m \) per ogni \(m\) abbiamo che \(k=1\) cambia tutte le luci in verdi che grazie al gatto tornano ad essere tutte rosse. Quindi \(k=1\) non cambia nulla. Sia \(m \equiv 27 \mod 2025 \), notiamo che \(m=2025 n + 27 =3^3 ( 75 n +1) \). Poiché \( \operatorname{gcd}(3^3,75n+1)=1 \) e la funzione che conta i divisori è moltiplicativa abbiamo quindi che i divisori di \(m\) che non sono multipli di \(3\) devono necessariamente essere divisori di \(75n+1\) il quale a sua volta soddisfa \(75n+1 \equiv 1 \mod 3 \). Pertanto se \(d_1 \cdot d_2 = 75 n +1 \) allora abbiamo due possibilità \(d_1 \equiv d_2 \equiv 1 \mod 3 \) oppure \( d_1 \equiv d_2 \equiv 2 \mod 3 \). Pertanto se \(1=d_1 < d_2 < \ldots < d_{\sigma_{0}(m)} =m\) sono i divisori di \(m \) in ordine crescente, se dopo che \(d_{i-1} \) è uscito la stanza è rossa con \(2 \leq i \), ed entra \(d_i \equiv 2 \mod 3 \), l'unico divisore che cambia il colore della stanza e la cambia da rosso a blu, allora esiste \( i < j \) tale che per ogni \( i < x < j < \sigma_0(m) \) abbiamo che \(d_x \equiv 0 \mod 3 \) i quali non cambiano il colore e poi abbiamo \(d_j \equiv 1 \mod 3 \) oppure \(d_j \equiv 2 \mod 3 \). Questo perché se scriviamo in ordine il resto modulo 3 dei divisori di \(75n+1\) abbiamo che formano un palindromo che inizia e finisce per \(1\) (ad esempio per \(76\) abbiamo \(1,2,1,1,2,1 \) che corrisponde ai resti modulo 3 di \(1,2,4,19,38,76\)). In entrambi i casi abbiamo che ogni volta che la stanza diventa blu ad un certo punto ritorna rossa. Questo dimostra che se \(m \equiv 27 \mod 2025 \) allora \(m\) sarà rossa una volta che sono entrati tutti gli ospiti.

[Pianoth]

La soluzione proposta da 3m0o naturalmente è corretta; il problema tuttavia nasconde altro di potenzialmente interessante:

1. È possibile dimostrare che avranno luce rossa tutti gli $n = 1 \mod 3$, $n = 3 \mod 9$, $n = 9 \mod 27$, $n = 27 mod 81$, e così via. Ovvero, ogni $n = 3^(k-1) \mod 3^k$ ha luce rossa, da cui segue direttamente che $n = 27 mod 2025$ ha luce rossa, perché $2025 = 3^4*5^2$. Questo costituirebbe una generalizzazione del problema che ho proposto.

2. È possibile dimostrare che avranno luce blu le stanze $n$:
- Tutti i numeri primi $n = 2 \mod 3$
- $n = 2 \mod 6$, $n = 6 \mod 18$, $n = 18 \mod 54$, ecc.
- $n = 5 \mod 30$, $n = 15 \mod 90$, $n = 45 \mod 270$, ecc.
- Molte altre classi di congruenza tra cui ad esempio $n = 11 \mod 462$, $n = 17 \mod 4641$, $n = 323 \mod 4641$, $n = 737 \mod 924$, $n = 1199 \mod 1386$, $n = 2123 \mod 2310$, $n = 3047 \mod 3234$, ...

3. Ci sono altre classi di congruenza che avranno luce rossa, oltre alla sequenza infinita menzionata prima: $n = 77 \mod 770$, $n = 231 \mod 770$, $n = 539 \mod 770$, e $n = 693 \mod 770$. Dopo queste 4, ce ne sono anche molte altre in $\mod 15470$, ad esempio $119 \mod 15470$, $n = 357 mod 15470$, e altre.

4. La conseguenza di queste infinite classi di congruenza consente di concludere che la densità asintotica di stanze rosse è superiore al 50%, ma inferiore al 70%. Questo è un grafico che mostra come varia la percentuale di stanze blu con l'aumentare del numero di stanze.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

A me sembra che il colore di \(3n \) è uguale al colore di \(n\) per ogni \(n\). Inoltre mi sembra che se \( n \equiv 1 \mod 3 \) allora \(n \) è rosso e se \(n \equiv 2 \mod 3 \) allora \(n \) è blu. Siccome la densità naturale di \(\{ 3^k : k \in \mathbb{N} \} \) è zero, i quali sono tutti rossi e stanno in \(n \equiv 0 \mod 3 \). Allora dovremmo avere che la densità naturale dei numeri blu è \(1/2\) così come la densità naturale dei numeri rossi. O almeno la densità superiore dei blu dovrebbe essere \(1/2\) e la densità inferiore dei rossi dovrebbe essere \(1/2\).

[Pianoth]

"3m0o":

A me sembra che il colore di \(3n \) è uguale al colore di \(n\) per ogni \(n\). Inoltre mi sembra che se \( n \equiv 1 \mod 3 \) allora \(n \) è rosso e se \(n \equiv 2 \mod 3 \) allora \(n \) è blu. Siccome la densità naturale di \(\{ 3^k : k \in \mathbb{N} \} \) è zero, i quali sono tutti rossi e stanno in \(n \equiv 0 \mod 3 \). Allora dovremmo avere che la densità naturale dei numeri blu è \(1/2\) così come la densità naturale dei numeri rossi. O almeno la densità superiore dei blu dovrebbe essere \(1/2\) e la densità inferiore dei rossi dovrebbe essere \(1/2\).

Purtroppo non è così semplice. Ad esempio, $n = 77 = 2 \mod 3$ avrebbe luce rossa: i divisori $1, 7, 11, 77$ cambiano la luce in questo modo:
- $1$ la cambia in verde e il gatto la reimposta rossa;
- $7$ la cambia in verde e il gatto la reimposta rossa;
- $11$ la cambia in blu
- $77$ la cambia in rossa.
Quindi la luce finale sarebbe rossa. Dato che metà dei numeri è occupata da $1 \mod 3$, e ci sono probabilmente infinite classi di congruenza aggiuntive che non combaciano con questa che portano ad una luce rossa (alcune le ho menzionate nell'altro post), la densità naturale delle luci rosse è certamente superiore a $1/2$. D'altronde lo vedi anche dal grafico che ho allegato che mostra come la percentuale di luci blu tende a diminuire, anche se molto lentamente. Ha però un limite inferiore, dovuto al fatto che anche le luci blu hanno infinite classi di congruenza; è possibile dimostrare che la densità naturale è sicuramente superiore a $467/1540 \approx 30.324675%$, e con un po' di pazienza si può migliorare ancora il lowerbound ulteriormente un po' per volta.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Hai ragione, mi sono reso conto sta notte del

77