52. Isola con $n$ abitanti

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
xXStephXx
Messaggi: 472
Iscritto il: 22 giu 2011, 21:51

52. Isola con $n$ abitanti

Messaggio da xXStephXx »

C'è un'isola sperduta con $n$ abitanti, dove $n$ è pari. Quindi $n$ potrebbe valere tranquillamente $76$ ma stavolta si rimane sul generico.
Bella st'isola eh? :D ..... Su quest'isola però c'è un problema (ovviamente).... presi due abitanti qualsiasi, essi sono reciprocamente o amici o nemici, senza vie di mezzo...
Così un bel giorno il sovrano dell'isola stabilisce una nuova regola: ogni abitante sarà costretto ad indossare una collana con delle perle in modo che due abitanti abbiano una perla dello stesso colore se e solo se sono amici. Quindi se due sono amici dovranno mettere nella propria collana almeno una perla dello stesso colore... se invece due sono nemici le loro collane non devono avere nessuna perla dello stesso colore.

- Quanti colori diversi servono come minimo se si vuole avere la certezza di poter completare tutte le collane a prescindere dalle amicizie e inimicizie?

PS: anche il sovrano rientra negli $n$ abitanti e come tutti gli altri ha simpatie e antipatie, quindi farà la collana pure lui.
nassus95
Messaggi: 79
Iscritto il: 14 giu 2012, 11:06

Re: 52. Isola con $n$ abitanti

Messaggio da nassus95 »

Penso alle persone come a punti di un grafo e due persone sono amiche se e solo se hanno un arco che le collega (altrimenti sono nemiche). Considero 3 punti a caso:
1) 3 lati $\Rightarrow$ posso utilizzare un unico colore per determinare questa "tripla amicizia"
2) 2 lati $\Rightarrow$ devo utilizzare 2 colori
3) 1 lato $\Rightarrow$ devo utilizzare 1 solo colore
4) 0 lati $\Rightarrow$ nessun colore
Nel caso peggiore ho solo situazioni del secondo tipo, ovvero nessun triangolo (o, ancora meglio, grafo completo con più di 3 nodi) e nessun caso del del terzo e quarto tipo. Ciò è possibile se, dati gli $n$ punti, ne scelgo uno a caso, lo collego ad altri $\frac{n}{2}$ e tutti questi li collego agli altri $\frac{n}{2}-1$. In questo modo ogni punto è collegato ad altri $\frac{n}{2}$ e, presi tre punti qualsiasi, questi sono uniti da 2 lati. Così facendo devo utilizzare un colore diverso per ogni arco e gli archi totali sono: $\frac{n \frac{n}{2}}{2}=\frac{n^2}{4}$
Quindi come minimo servono $\frac{n^2}{4}$ colori
xXStephXx
Messaggi: 472
Iscritto il: 22 giu 2011, 21:51

Re: 52. Isola con $n$ abitanti

Messaggio da xXStephXx »

Le osservazioni sono corrette e anche il risultato :D

Però.......... immagino che sai già.... che manca totalmente la dimostrazione xD
xXStephXx
Messaggi: 472
Iscritto il: 22 giu 2011, 21:51

Re: 52. Isola con $n$ abitanti

Messaggio da xXStephXx »

Siccome è passata più di una settimana:
Le parti che mancano della dimostrazione sono sostanzialmente due credo..
1) Dimostrare davvero che il caso peggiore richiede l'assenza di triangoli. Qua ci è andato vicino ma secondo me non basta dire che se c'è un triangolo posso usare due volte lo stesso colore... (perchè comunque la presenza di triangoli potrebbe implicare che ci sono molti più lati, quindi a priori non so se è scontato che i colori richiesti siano davvero di meno rispetto ad un grafo con molti meno lati).
2) Dimostrare che un grafo senza triangoli può avere al più $\displaystyle \frac{n^2}{4}$ lati. Qua è stata mostrata una configurazione buona, ma manca da dimostrare che quello è davvero il massimo... e qui:
Testo nascosto:
viene bene per ricorrenza (se applicata nel modo giusto)
Talete
Messaggi: 745
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: 52. Isola con $n$ abitanti

Messaggio da Talete »

Siccome non ho niente da fare se non aspettare che mi venga la voglia di fare gli ultimi problemi per il Senior, mi chiedo: è normale che un problema della staffetta rimanga senza risposta per... quanto? Quattordici mesi? Però, è parecchio tempo... :)
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
xXStephXx
Messaggi: 472
Iscritto il: 22 giu 2011, 21:51

Re: 52. Isola con $n$ abitanti

Messaggio da xXStephXx »

Penso sia dovuto più che altro al fatto che questa sezione è diventata semi-deserta. Il problema in sè non me lo ricordo cattivo, anche se ora non lo saprei fare :lol:
Avatar utente
karlosson_sul_tetto
Messaggi: 1452
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: 52. Isola con $n$ abitanti

Messaggio da karlosson_sul_tetto »

Questo post poteva benissimo raggiungere il record di post della staffetta più lungo, ma ovviamente Talete deve rovinare tutto ( :mrgreen: ).

Possiamo immaginarci la situazione come un grafo di $n=2k$ vertici in cui due vertici sono collegati se e solo se i due tizi sono amici. Come prima cosa, dimostro che nel caso peggiore non ci sono tre persone, tutte amiche tra di loro.
Prendo una configurazione in cui ci sono dei triangoli. Se per ogni scelta di tre persone $A,B,C$ tutte amiche tra di loro, NON c'è una perla che usano tutti e tre, allora c'è una distribuzione di perle che usa meno colori che assegna ai tre tizi una sola perla (al contrario di tre per identificare la loro reciproca amicizia); inoltre non ci sono problemi del tipo "ma la perla $x$ che usano A e B non può essere sostituita con un'altra perla $y$ che useranno A, B e C perché la perla $x$ la usa pure $D$ e dovrei aggiungere altre perle" perché cosi si andrebbe contro l'ipotesi di questo caso. In parole povere: ci sono (almeno) tre amici che usano la stessa perla.
Ora, creo un'altra configurazione in cui due di questi tre amici sono diventati nemici: avrò bisogno di usare almeno due perle per collegare i due amici al posto di quella singola di prima.
Non direi che è una dimostrazione molto formale... ma sorvoliamo
Ora che ho fatto la parte brutta, noto che se non ho triangoli allora per ogni coppia di amici ho bisogno di una perlina, il che è equivalente a trovare il numero massimo di archi (caso peggiore) in un grafo del genere.


Metodo 1, suggerito da xXStephXx:
Chiamo $f(x)$ il numero massimo di archi che può avere un grafo senza triangoli con $x$ vertici. Cerco di ottenere ricorsivamente $f(n)$. Prendo due vertici collegati, $A$ e $B$ e guardo gli altri $n-2$ vertici; in questi, ci saranno al massimo $f(n-2)$ collegamenti. $A$ e $B$ non possono essere entrambi collegati ad uno stesso vertice; d'altronde, nel caso migliore, se ci fosse un vertice non collegato né ad $A$ né a $B$, potrei collegarlo ad uno dei 2 senza avere paura di avere tre vertici collegati perché l'altro non è collegato. Il numero massimo di archi è quindi: $f(n)=1+(n-2)+f(n-2)$ (arco $AB$, archi da $A$ e da $B$, archi nel resto del grafo) ovvero ricordando che n è pari:
$f(2k)=2k-1+f(2k-2)=2k-1+2(k-1)-1+f(2k-4)=\sum\limits_{i=1}^{k} 2i-1=$
$=2\sum\limits_{i=1}^{k}i-\sum\limits_{i=1}^{k}1=
2\frac{k(k+1)}{2}-k=k^2=\frac{n^2}{4}$
Anche qua, andrebbe formalizzato meglio con l'induzione...


Metodo 2 figo:
Prendo i vertici $v_1\ldots v_n$ ed ad ognuno assegno un numero reale $x_1\ldots x_n$ con le condizioni $\sum\limits_{i=1}^n x_i=1$ e $x_i \geq 0 \; \forall i$.
Considero la somma $S=\sum x_ix_j$, dove è presente il termine $x_ix_j$ se e solo se $v_i$ e $v_j$ sono collegati. Cerco il massimo di S. Siano $v_A$ e $v_B$ due vertici NON collegati, sia $n=\sum x_i$ tali che $v_i$ e $v_A$ sono collegati e $m=\sum x_i$ tali che $v_i$ e $v_B$ sono collegati. WLOG $n\geq m$. Posso scrivere $S$ come:
$S=D+x_An+x_Bm$ dove $D$ è il contributo delle coppie di vertici che non hanno né $v_A$ né $v_B$.
Ora noto che sostituendo a $(x_A,x_B)$ la coppia $(x_A+x_B,0)$, le condizioni sugli $x_i$ restano verificate, ma $S$ aumenta:
$S'=D+(x_A+x_B)\cdot n+0\cdot m=D+x_An+x_Bn \geq D+x_An+x_Bm$ siccome ho presupposto $n\geq m$.
Rifacendo il procedimento taaante volte, visto che non ci sono triangoli arrivo ad un momento in cui ci sono solo due $x_k, x_l$ diversi da $0$.
$S\leq S^{''\ldots '}=x_kx_l \leq \left( \frac{x_k+x_l}{2} \right)^2=\frac{1}{4}$ (la disuguaglianza vale per AM-GM)
Se pongo $x_i=\frac{1}{n} \; \forall i$, ho:
$S=\sum\frac{1}{n}\cdot \frac{1}{n}=|\mathrm{E}|\frac{1}{n^2}\leq \frac{1}{4}$, dove E è l'insieme degli archi del grafo.
Segue che il numero degli archi è $\leq \frac{n^2}{4}$ ( e si noti che in questo caso non è necessario $n$ pari)


Per la configurazione che funziona, basta dividere il grafo in due parti ciascuna con $\frac{n}{2}$ abitanti e collegare i vertici di una parte a tutti quelli dell'altra parte, per un totale di $\frac{n^2}{4}$ archi e quindi lo stesso numero di perline.
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
Talete
Messaggi: 745
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: 52. Isola con $n$ abitanti

Messaggio da Talete »

karlosson_sul_tetto ha scritto:Questo post poteva benissimo raggiungere il record di post della staffetta più lungo, ma ovviamente Talete deve rovinare tutto ( :mrgreen: ).
Be', io sono su questo forum da molti meno anni di te, però credo che quattordici mesi sia un record parecchio duro da battere, no? ;)
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
xXStephXx
Messaggi: 472
Iscritto il: 22 giu 2011, 21:51

Re: 52. Isola con $n$ abitanti

Messaggio da xXStephXx »

Ok bene :D Mi sembra che l'avevo fatto proprio uguale al primo metodo. Nel secondo che è tutto 'sto magheggio? xD Comunque ok vai col prossimo.
Rispondi