n punti su un cerchio

[mattilgale]

abbiamo n punti $ P_1,\ P_2,\dots,\ P_n $ su un cerchio e il segmento che unisce due punti può essere blu o rosso...

$ P_iP_j $ è rosso se e solo se $ P_{i+1}P_{j+1} $ è blu con $ i,j\in\{1,\dots,n\} $

i) determinare per quali n tale colorazione è possibile
ii) dimostrare che da qualsiasi punto è possibile raggiungere ogni altro punto con al più tre spostamenti lungo segmenti rossi (per spostamento si intende il passaggio da uno dei $ P_i $ ad un altro)

[enomis_costa88]

Con $ P_{1+n} $ intendo $ P_1 $, in generale con $ P_{i+n} $ intendo $ P_i $.
Inoltre suppongo Wlog che gli n punti siano disposti ordinatamene su un n-agono regolare.

i) Step 1: Fissato k i segmenti del tipo $ P_iP_{i+k} $ per $ i \in \{1,\dots,n\} $ sono pari.
Chiamo coppia di segmenti amici le coppie del tipo: $ (P_iP_j ; P_{i+1}P_{j+1}) $.
Dalle ipotesi deduco facilmente che non posso avere una coppia di segmenti amici dello stesso colore.
Ovvero i segmenti del tipo $ P_iP_{i+k} $ devono essere al variare di i alternativamente blù e rossi.
Se si disponessere diversamente ne avrei due consecutivi (quindi amici) dello stesso colore.
Se lo step 1 fosse falso avrei un k t.c. i segmenti $ P_iP_{i+k} $ siano dispari.
Quindi i segmenti rossi del tipo $ P_iP_{i+k} $ non sono dello stesso numero dei segmenti blu.
Questo vuole dire che ho una coppia di segmenti amici dello stesso colore, contro quanto dimostrato sopra.

Step 2: necessariamente n è multiplo di 4.
n deve essere pari poichè i segmenti del tipo $ P_iP_{i+1} $(ovvero i lati dell'n-agono regolare) sono in numero pari.
n=2m.
Inoltre i segmenti del tipo$ P_iP_{i+k} $ sono n per $ k \not = m $.
Infatti ogni $ P_i $ risulta essere connesso con $ P_{i+k} $ e con $ P_{i-k} $mediante uno di questi segmenti.
Ogni segmento connette due vertici.
Quindi i segmenti $ P_iP_{i+k} $ sono in numero $ 2\frac{n}{2}=n $ .
Se k=m invece ogni $ P_i $ risulta essere connesso solo con $ P_{i+m} = P_{i-m} $ mediante uno di questi segmenti.
Quindi il numero di segmenti del tipo $ P_iP_{i+m} $ risulta $ \frac{n}{2} $.
Se $ \frac{n}{2} $ è pari allora $ n \equiv 0 \pmod 4 $ .

E' inoltre facile verificare che questa condizione è anche sufficente.
Infatti se coloro di blù $ P_iP_{i+k} $ allora posso sempre colorare di blu tutti i $ P_{i+2j}P_{i+2j+k} $ e di rosso tutti i $ P_{i+2j+1}P_{i+2j+1+k} $ per qualsiasi k,j rispettando quindi le ipotesi.

[enomis_costa88]

ii)Step 1: da $ P_i $ posso sempre arrivare in max 2 mosse a $ P_{i+2j+1} $
Le coppie $ (P_iP_{i+1};P_{i-1}P_i) $ sono di segmenti amici, quindi di colore distinti.
Se $ P_iP_{i+1} $ è rosso: allora dato che i segmenti $ P_jP_{j+1} $ sono alternativamente rossi e blù pure $ P_{i+2j}P_{i+2j+1} $ è rosso.
Inoltre i 2 segmenti $ (P_iP_{i+2j};P_{i+1}P_{i+2k+1}) $ sono amici e almeno uno di essi è rosso.
Quindi il percorso $ P_iP_{i+1};P_{i+1}P_{i+2j+1} $ oppure il percorso $ P_iP_{i+2j};P_{i+2j}P_{i+2j+1} $ è formato solo da segmenti rossi.
Se $ P_iP_{i+1} $ è blù allora $ P_{i-1}P_i $ è rosso e agisco analogamente ma sostituendo $ P_{i+1} $ con $ P_{i-1} $ e $ P_{i+2j} $ con $ P_{i+2j+2} $.

Step 2: da $ P_i $ posso sempre arrivare in max 3 mosse a $ P_{i+2j} $
Infatti posso arrivare in max due mosse sia in $ P_{i+2j-1} $ che in $ P_{i+2j+1} $ per lo step 1.
I segmenti $ P_{i+2j-1}P_{i+2j}; P_{i+2j}P_{i+2j+1} $ sono amici quindi almeno uno è rosso, quindi da $ P_i $ posso sempre arrivare in max 3 mosse a $ P_{i+2j} $ .