47 Idraulico

[Troleito br00tal]

Ogn. Sia $n \ge 3$ un intero positivo. Sia $A_1A_2...A_n$ un poligono regolare di $n$ vertici. Associamo un numero $k$ tale che $1 \le k \le \frac{n^2-n}{2}$ ad ogni diagonale (o lato) del tipo $A_iA_j$, tale ad ogni diagonale sia associato esattamente un numero ed ogni numero sia associato ad esattamente una diagonale (quindi vengono associati tutti i numeri tra $1$ e $\frac{n^2-n}{2}$). Diciamo che due diagonali $d_1$ e $d_2$ sono connesse se hanno in comune un vertice $A_i$ e se tra i numeri associati alle diagonali uscenti da $A_i$ nessun numero è compreso tra i numeri associati a $d_1$ e a $d_2$. Determinare, in funzione di $n$, il minor numero di colori con i quali è possibile colorare tutte le diagonali del nostro poligono in modo che tutte le diagonali connesse abbiano colori distinti tra loro.

[Triarii]

Comunque io ho interpretato il problema come: metto i numeri in modo che mi torni comodo e poi trovo il numero di colo necessari in questa configurazione ottimale (spero che il problema non fosse:"trova il minimo numero con cui sicuramente in qualsiasi caso ce la fai". Poi boh forse non c'è nemmeno differenza, chissà)
Dimostriamo che $3$ colori ci bastano indipendentemente da $n$.
Procediamo per induzione sul numero di vertici $n$. Il passo base sul triangolo con lati numerati da $1$a $3$ è ovvio.
Passiamo al passo induttivo. Per semplicità chiamerò diagonali nuovi le diagonali aggiunte nel passo induttivo, mentre le altre già presenti le chiamerò diagonali vecchie. Come ipotesi abbiamo che 3 colori mi sono bastati per colorare il $n-1$-agono. Ora aggiungo un vertice, e di conseguenza $n-1$ diagonali (fra cui 2 lati, lo sottointendo ovviamente). Assumo che i numeri associati alle diagonali aggiunte siano gli $n-1$ più grandi. Ogni diagonale così aggiunta ovviamente unisce il vertice nuovo ad uno dei vertici già presenti (un vertice vecchio per diagonale). Siccome ogni diagonale ha fra i numeri più alti, è connessa ad esattamente una diagonale vecchia che incontra nel suo estremo sul vertice vecchio. Inoltre nel vertice nuovo ci sono 2 diagonali connesse ad una sola nuova diagonale (quelle contrassegnate dal più piccolo e dal più grande numero aggiunto), mentre le altre sono connesse alle 2 diagonali nuove contrassegnate dal numero precedente e successivo. Ricapitolando, 2 diagonali sono connesse ad altre 2 diagonali, mentre le altre a 3. Mostro ora che è possibile colorare le nuove diagonali usando gli stessi 3 colori (che chiamo $A$,$B$,$C$). Parto dalla diagonale col numero più basso aggiunto. Essa è collegata ad una diagonale vecchia, che suppongo essere colorata wlog $A$. La coloro wlog $B$. L'unica diagonale nuova a cui è connessa quindi può assumere o 2 colorazioni (se la diagonale vecchia a cui è connessa quest'ultima è colorata $B$), oppure una soltanto. Procedendo in questo modo ce la facciamo a colorare le altre diagonali perchè ogni diagonale è collegata a 2 diagonali già colorate (la terza è da colorare e posso quindi scegliermi come colorarla in modo opportuno). Quindi riusciamo ad arrivare alla fine del percorso, con l'ultima diagonale che è connessa a solo 2 diagonali (una vecchia e una nuova) già colorate e quindi esiste sicuramente almeno un colore diverso da quelli di queste due con il quale posso colorarla.

[Troleito br00tal]

Ottimo:)