Staffetta 21. Coloriamo A

[jordan]

Siano A un insieme ordinato di $ n>1 $ elementi e $ B_1,\ldots, B_k \subseteq A $, con $ k<n $. Dimostrare che è sempre possibile dare una colorazione con due colori degli elementi di A tale che

• 1) ogni elemento di A o è colorato con uno dei due colori oppure è lasciato incolore.
  2) almeno un elemento di A è colorato.
  3) se esiste un elemento di un $ B_i $ colorato allora esiste almeno un altro elemento di $ B_i $ colorato con l'altro colore. Ossia o $ B_i $ è tutto incolorato oppure sono presenti entrambi i colori.

[staffo]

facciamo passo per passo:
0)ci sono elementi di $ A $ che non appartengono ad alcun $ B_i $: ne coloro uno;
i)tutti i $ B_i $ hanno cardinalità uno, fatta eccezione per un $ B_i $ con cardinalità due (tutti con cardinalità uno andrebbero contro le hp): allora la soluzione è banale (colorare di due colori i due elementi dell'insieme di cardinalità due);
ii)tutti i $ B_i $ disgiunti a due a due: per lo stesso ragionamento di prima è possibile effettuare la colorazione;
iii)sottoinsiemi (non tutti necessariamente) non disgiunti, con $ |B_i \cap B_j|>1 $ per almeno un $ i,j $: colorando gli elementi dell'intersezione di questi due ultimi insiemi con due colori otteniamo una soluzione;
iv)sottoinsiemi (non tutti necessariamente) non disgiunti, con $ |B_i \cap B_j|=1 $ per ogni $ i,j $: dalle ipotesi sappiamo che il numero di insiemi è minore del numero degli elementi di $ A $, e per la (0) dobbiamo avere che non ci sono elementi di $ A $ non appartenenti ad alcun $ B_i $. Se gli insiemi possiedono intersezioni a due a due, possono verificarsi 4 casi:
a)l'intersezione avviene tra $ |B_1|=1 $ e $ |B_2|=2 $; in tal caso non potremmo colorare, ma avremmo due insiemi per due elementi, e quindi ce ne sarebbero altri che ricadrebbero in uno degli altri casi citati sopra (o che citerò a breve);
b) si intersecano al più due insiemi tra di loro: allora coloro l'elemento dell'intersezione con un colore e uno degli elementi rimanenti in ciascun insieme con l'altro colore;
c)dati $ |B_{i}\cap B_{j}|=1, |B_{j}\cap B_{k}|=1, ...., |B_{n}\cap B_{i}|=0 $ per ogni $ i,j,k... $ (cioè, "il ciclo di intersezioni non si chiude, ovvero non c'è una sequenza che permette, spostandoci tra elementi dello stesso insieme e non ritornando mai sullo stesso, di tornare all'insieme iniziale), anche qui avremmo la possibilità di colorare senza cadere in casi problematici (partendo con un colore e scegliendo di conseguenza gli altri)
d)caso opposto a quello citato sopra: se almeno un insieme del ciclo ha cardinalità maggiore di due, non ci sono problemi;
se non c'è nessun insieme del ciclo che ha cardinalità maggiore di due, allora per le ipotesi ci sarà un altro insieme non appartenente al ciclo con cardinalità maggiore di uno (altrimenti il numero di sottoinsiemi andrebbe contro le ipotesi) e quindi sarà permessa la colorazione;

spero di aver trattatato esaustivamente tutti i casi...

[Anér]

iii)sottoinsiemi (non tutti necessariamente) non disgiunti, con $ |B_i \cap B_j|>1 $ per almeno un $ i,j $: colorando gli elementi dell'intersezione di questi due ultimi insiemi con due colori otteniamo una soluzione;

Qui c'è una falla: se $ B_i $ e $ B_j $ hanno almeno due elementi in comune e ne scegli due a caso, chiamiamoli $ x,y $ che colori uno di nero e uno di bianco, hai senz'altro sistemato $ B_i $ e $ B_j $, ma potrebbe esistere un altro insieme $ B_l $ che contiene $ x $ ma non $ y $ e a quel punto dovresti colorare almeno un altro elemento di $ B_k $ del colore diverso da $ x $.

Questa è la mia soluzione. Pongo $ A=\{a_1,\cdots, a_n\} $. Ora ogni elemento appartiene ad alcuni dei $ B_i $ e ad altri no. Allora per ogni elemento definisco il vettore $ v_i=(c_{i,1},\cdots, c_{i,k}) $, ove $ c_{i,j} $ vale 1 se $ a_i\in B_j $ e 0 altrimenti. Questi $ v_i $ sono $ n $ vettori appartenenti a $ \mathbb{R}^k $, e dato che $ k<n $ questi vettori non possono essere linearmente indipendenti, ovvero esistono coefficienti reali $ \lambda _1, \cdots, \lambda _n $ tali che $ \lambda _1v_1+\cdots+\lambda_nv_n=0 $, e non tutti i $ \lambda_i $ sono nulli. A questo punto coloro di nero gli elementi $ a_i $ per cui $ \lambda _i $ è positivo, di bianco quelli per cui $ \lambda _i $ è negativo, mentre non coloro quelli che hanno coefficiente nullo.
Poiché c'è almeno un coefficiente diverso da 0 ho colorato almeno un elemento. Inoltre se $ B_j $ avesse elementi neri ma nessun elemento bianco non potrebbe essere $ \lambda _1v_1+\cdots+\lambda_nv_n=0 $ perché la somma delle $ j $-esime componenti dei vettori sarebbe strettamente positiva (sarebbe la somma di alcuni $ \lambda _i $ positivi).

[staffo]

ma io infatti quel caso lo tratto dopo, perchè io in quel punto tratto un caso in cui tutte le intersezioni hanno cardinalità maggiore o uguale a due; il caso con intersezione di uno tra due insiemi lo considero dopo....

EDIT: rileggiendo mi sono accorto che ho scritto per alcuni i,j, ma intendevo che se c'è un'intersezione, allora essa aveva cardinalità maggiore per tutti gli i,j, ma che alcuni poitevano anche non avere intersezioni;

il caso da te citato lo tratto nel punto successivo comunque

[jordan]

L'obiezione di Anèr è giusta, così come la sua soluzione. Il fatto è che ciascun elemento può appartene al più ai k sottoinsiemi contemporaneamente, il che significa che, fissato k, dovresti svolgerti tutti i $ 2^k $ casi di intersezione..se non ho reso molto l'idea prova a farti un esempio con n=7 e k=5, in cui ogni elemento appartiene sempre ad almeno 4 sottoinsiemi

@Anèr: vai col prossimo

[Anér]

Il prossimo è qui.