Insiemi e combinatoria?

[RuCoLa1]

Siano $A_1$ , $A_2$ .... $A_(n+1)$ insiemi aventi ciascuno n elementi, tali che ogni coppia di insiemi abbia esattamente un elemento in comune e che ogni elemento dell' unione appartenga ad esattamente 2 insiemi. Per quali valori di n è possibile colorare con 2 colori gli elementi dell' unione in modo che ogni insieme possegga un ugual numero di elementi dei due colori?
Se ho capito bene ciascun elemento deve appartenere ad esattamente 3 insiemi... ma non so andare avanti.

Potete aiutarmi?
Grazie

[anto_zoolander]

Considerando che è tardi ti posto una bozza di quello che ho tirato fuori in questi dieci minuti guardando le olimpiadi, magari può servire e domani lo rifaccio a mente fresca.

mmm... intanto comunque prendo due insiemi, hanno un solo elemento in comune. Questo vuol dire che comunque prendo due insiemi, l'intersezione è non vuota(e contiene un elemento soltanto)

Pensandoci in quanti modi posso fare questo $->$ $A_kcapA_j$? Beh considerando che ci sono $n+1$ insiemi e considerando che $A_kcapA_j=A_jcapA_k,forallj,kinNN:jnek$ Ho $1,2,...,n+1$ indici da distribuire a coppie di due.

$C_(n+1,2)=((n+1),(2))=(n(n+1))/2$

ad esempio se ho $n=3$ avrò $A_1,A_2,A_3,A_4$ insiemi che possono combinare in $C_(4,2)=6$ modi.

${(A_1capA_2),(A_1capA_3),(A_1capA_4),(A_2capA_3),(A_2capA_4),(A_3capA_4):}$ sono tutte le combinazioni

allora faccio così $A_jcapA_k={a_(j,k)}$ così creo una corrispondenza biunivoca che lega ad ogni intersezione l'unico elemento del tipo $a_(j,k)$ ad esempio $a_(2,7)$ è l'elemento dell'intersezione $A_2capA_7$ inoltre la coppia $a_(j,k)=a_(k,j)$ che per come è definita la corrispondenza, è giustificata dalla commutatività dell'intersezione.

La seconda informazione non la riesco a tradurre benissimo vediamo proviamo a fare qualche tentativo con numeri bassi.
Prendiamo $n=2$, avremo $3$ insiemi con $2$ elementi ciascuno e $C_(3,2)=3$ intersezioni.

${(A_1capA_2={a_(1,2)}),(A_2capA_3={a_(2,3)}),(A_1capA_3={a_(1,3)}):}$

beh essendo che ogni insieme ha $n=2$ elementi abbiamo che gli insiemi sono composti da questi elementi

${(A_1={a_(1,2),a_(1,3)}),(A_2={a_(1,2),a_(2,3)}),(A_3={a_(2,3),a_(1,3)}):}$

vediamo che comunque prendo l'unione, ogni elemento appartiene a soltanto due insiemi. Quindi suppongo che intenda che ogni elemento dell'unione appartiene a esattamente due insiemi che non sono per forza quelli che compongono l'unione.

${(A_1cupA_2={a_(1,2),a_(1,3),a_(2,3)}),(A_2cupA_3={a_(2,3),a_(2,1),a_(3,1)}),(A_1cupA_3={a_(1,3),a_(1,2),a_(3,2)}):}$

Viene da pensare che avendo ogni insieme $n$ elementi e l'intersezione di due insiemi un solo elemento, allora quando li unisco quell'insieme avrà, passami il termine, un solo doppione. Allora avrà $n$ elementi del primo, $n$ elementi del secondo, meno un elemento che hanno in comune(questo elemento lo tolgo solo una volta). Dunque $|A_jcupA_k|=2n-1,forallj,kinNN:jnek$

Sarebbe utile se chiarissi come devono essere colorati gli insiemi: ogni termine con un colore diverso, con due colori soltanto?
Ora ci dormo un po' su.

[RuCoLa1]

Ah okay credevo che una volta fatta l'unione i due insiemi uniti contassero come uno solo, ma in effetti deve essere come dici te. Dal testo, secondo me gli elementi possono essere colorati con due colori soltanto.

[anto_zoolander]

Forse il problema è che la questione è posta un po' male:

Per quali valori di n è possibile colorare gli elementi dell' unione in modo che ogni insieme possegga un ugual numero di elementi dei due colori?

mi viene da fare le seguente domanda:
Quando coloro un insieme unione, posso usare soltanto due colori? se è si, quei due colori valgono soltanto per gli insiemi che compongono l'unione?

Comunque a parte questo, penso che ci si possa porre un problema ausiliario. Intanto potendo identificare un elemento con una intersezione, possiamo creare il seguente sistema, dati $n+1$ insiemi con $n$ elementi e $((n+1),(2))$ possibili intersezioni.

$(n(n+1))/2$ int. ${(A_1capA_2={a_(1,2)}),(A_1capA_3={a_(1,3)}),(...),(A_1capA_k={a_(1,k)}),(...),(A_jcapA_k={a_(j,k)}):}$

per brevità ora scriverò $a_(j,k)=a_(k,j)$ intendendo l'elemento dell'insieme dato dall'intersezione $A_jcapA_k=A_kcapA_j$
Ogni insieme conterrà $n$ elementi ma in totale ci sono tanti elementi quante intersezioni, poiché ogni intersezione rappresenta uno e un solo elemento. Ora se $n$ è dispari nemmeno ci poniamo il problema visto che non sarà possibile avere esattamente due gruppi di $n/2$ elementi di colore diverso. Quindi $n$ deve essere pari.

Ora volendo se $n$ è pari si può fare questo ragionamento, disponendo gli elementi in fila. Prendendo ad esempio il caso $n=4$ avremo

$ [ ( a_(1,2) , a_(1,3) , a_(1,4) , a_(1,5) , a_(2,3) ),( a_(2,4) , a_(2,5) , a_(3,4) , a_(3,5) , a_(4,5) ) ] $

e fare:

${(a_(1,2)=r),(a_(1,3)=v),(a_(1,4)=r),(a_(1,5)=v):}$

e abbiamo il primo insieme $A_1={r,v,r,v}$
poi il secondo avrà vincolati tutti quel del tipo $a_(j,2)$, ne è uscito soltanto $1:{a_(1,2)}$

${(a_(2,1)=r),(a_(2,3)=r),(a_(2,4)=v),(a_(2,5)=v):}$

così abbiamo il secondo insieme $A_2={r,r,v,v}$

il terzo avrà vincolati tutti quelli del tipo $a_(j,3)$ e ne sono usciti $2:{a_(1,3),a_(2,3)}$

${(a_(3,1)=v),(a_(3,2)=r),(a_(3,4)=v),(a_(3,5)=r):}$

anche così abbiamo formato il terzo insieme $A_3={v,r,v,r}$

il quarto avrà vincolati tutti quelli del tipo $a_(j,4)$ e ne sono usciti $3:{a_(1,4),a_(2,4),a_(3,4)}$

${(a_(4,1)=r),(a_(4,2)=v),(a_(4,3)=v),(a_(4,5)=r):}$

il quarto insieme $A_4={r,v,v,r}$

il quinto infine avrà vincolati $a_(j,5)$ e ne sono usciti $4:{a_(1,5),a_(2,5),a_(3,5),a_(4,5)}$

${(a_(5,1)=v),(a_(5,2)=v),(a_(5,3)=r),(a_(5,4)=r):}$

con l'insieme $A_5={v,v,r,r}$

Ora bisognerebbe trovare una corrispondenza tra un gli elementi e i colori. Cioè come devo scegliere un colore. Ora devo scendere, quindi metto un altro spoiler. Nel frattempo spero di contribuire

PS: dove lo hai preso questo esercizio?

[onlyReferee]

Un saluto ad entrambi
Allora, possiamo verificare innanzitutto facilmente che una volta scelto $n$, ciascuno dei nostri insiemi deve contenere $n$ elementi e che il numero totale degli elementi che compongono la nostra unione degli elementi dei vari insiemi è pari a $\sum_{i = 1}^{n} i = \frac{n\cdot(n + 1)}{2}$ (già spiegato da anto_zoolander).
Risulta subito chiaro che per avere gli elementi di ciascun insieme colorati in egual numero dobbiamo avere sicuramente $n$ pari. Ciò però è condizione necessaria ma non sufficiente in quanto se $n$ è multiplo di $2$ ma non di $4$ abbiamo che $\frac{n}{2}$ è dispari. Inoltre se $n$ è pari, $n + 1$ è dispari e, dato che $\frac{n}{2}$ è dispari, ed il valore della sommatoria sopra sarà per forza dispari. Se abbiamo un numero dispari di elementi nella nostra unione di insiemi ci sarà sicuramente uno degli insiemi che non avrà elementi dei due colori presenti nella medesima quantità. Le condizioni richieste invece si verificano nel caso in cui invece $n$ sia multiplo di $4$, pertanto quando possiamo scrivere $n = 4 \cdot k, k \in \mathbb{N}$.

[anto_zoolander]

Forse io ho allargato troppo il concetto a voler trovare un modo per individuare il modo di colorarli, più che dimostrare soltanto che sia possibile farlo ormai arrivato a questo punto penso che cercherò comunque di farlo

[consec]

"onlyReferee":Se abbiamo un numero dispari di elementi nella nostra unione di insiemi ci sarà sicuramente uno degli insiemi che non avrà elementi dei due colori presenti nella medesima quantità.

Non ho capito questa affermazione, ti dispiace spiegarmela?

[RuCoLa1]

Grazie mille ad entrambi, credo di aver capito. In pratica n deve essere pari perché coloro gli elementi di due colori diversi. Inoltre anche il numero totale degli elementi deve essere pari per poter soddisfare le condizioni. Poiché nella formula per calcolare il numero totale degli elementi si divide per 2 allora affinché n (n+1) / 2 sia pari n deve essere anche multiplo di 4.
L'esercizio l'ho preso da http://www.dmi.units.it/divulgazione/ma ... oniche.pdf pagina 71

[onlyReferee]

"consec":[quote="onlyReferee"]Se abbiamo un numero dispari di elementi nella nostra unione di insiemi ci sarà sicuramente uno degli insiemi che non avrà elementi dei due colori presenti nella medesima quantità.

Non ho capito questa affermazione, ti dispiace spiegarmela? [/quote]
Detto in altre parole: se la cardinalità dell'unione degli insiemi é dispari non posso sicuramente avere una metà degli elementi (sempre dell'unione) di un colore e l'altra metà di un altro colore.

"RuCoLa":Grazie mille ad entrambi, credo di aver capito. In pratica n deve essere pari perché coloro gli elementi di due colori diversi. Inoltre anche il numero totale degli elementi deve essere pari per poter soddisfare le condizioni. Poiché nella formula per calcolare il numero totale degli elementi si divide per 2 allora affinché n (n+1) / 2 sia pari n deve essere anche multiplo di 4.
L'esercizio l'ho preso da http://www.dmi.units.it/divulgazione/ma ... oniche.pdf pagina 71

Di nulla, felice di esserti stato d'aiuto !

[consec]

"onlyReferee":[quote="consec"][quote="onlyReferee"]Se abbiamo un numero dispari di elementi nella nostra unione di insiemi ci sarà sicuramente uno degli insiemi che non avrà elementi dei due colori presenti nella medesima quantità.

Non ho capito questa affermazione, ti dispiace spiegarmela? [/quote]
Detto in altre parole: se la cardinalità dell'unione degli insiemi é dispari non posso sicuramente avere una metà degli elementi (sempre dell'unione) di un colore e l'altra metà di un altro colore.

"RuCoLa":Grazie mille ad entrambi, credo di aver capito. In pratica n deve essere pari perché coloro gli elementi di due colori diversi. Inoltre anche il numero totale degli elementi deve essere pari per poter soddisfare le condizioni. Poiché nella formula per calcolare il numero totale degli elementi si divide per 2 allora affinché n (n+1) / 2 sia pari n deve essere anche multiplo di 4.
L'esercizio l'ho preso da http://www.dmi.units.it/divulgazione/ma ... oniche.pdf pagina 71

Di nulla, felice di esserti stato d'aiuto ![/quote]
Da come avevo interpretato io il problema, credevo che soo gli $n+1$ insiemi di partenza dovessero avere gli elementi divisi in due colori, non anche l'insieme unione. In questo caso hai ovviamente ragione (ma la traccia del problema non è chiarissima al riguardo). Anche perché se l'insieme unione non è incluso nella richiesta del problema, la condizione della divisibilità per $4$ non mi pare necessaria, giusto?

[anto_zoolander]

"onlyReferee":Detto in altre parole: se la cardinalità dell'unione degli insiemi é dispari non posso sicuramente avere una metà degli elementi (sempre dell'unione) di un colore e l'altra metà di un altro colore.

La cardinalità dell'unione è sempre dispari guarda.

$|A_jcupA_k|=2n-1,forallj,kinNN:jnek$

Questo perché $|A_j|=|A_k|$ e $|A_jcapA_k|=1$

Quindi quando li unisco ho $n$ elementi del primo più $n$ elementi del secondo, di cui uno viene contato due volte poiché lo hanno entrambi e quindi dobbiamo toglierlo. Dunque la cardinalità dell'unione è $2n-1$ che è dispari comunque scelga $n$

[consec]

"anto_zoolander":[quote="onlyReferee"]Detto in altre parole: se la cardinalità dell'unione degli insiemi é dispari non posso sicuramente avere una metà degli elementi (sempre dell'unione) di un colore e l'altra metà di un altro colore.

La cardinalità dell'unione è sempre dispari guarda.

$|A_jcupA_k|=2n-1,forallj,kinNN:jnek$

Questo perché $|A_j|=|A_k|$ e $|A_jcapA_k|=1$

Quindi quando li unisco ho $n$ elementi del primo più $n$ elementi del secondo, di cui uno viene contato due volte poiché lo hanno entrambi e quindi dobbiamo toglierlo. Dunque la cardinalità dell'unione è $2n-1$ che è dispari comunque scelga $n$[/quote]
Credo intenda l'unione di tutti gli insiemi, di cardinalità $n+(n-1)+(n-2)+...1$ da cui abbiamo tolto a ogni insieme le intersezioni con i precedenti già conteggiati nella somma.

[anto_zoolander]

Vediamo se ho capito che intende... essendo che ci sono $((n+1),2)$ intersezioni allora l'unione di tutti gli insiemi deve contenere esattamente $((n+1),(2))$ elementi. Poiché di fatto ogni intersezione individua un elemento e quindi l'unione di tutti gli insiemi dovrà contenere esattamente quel numero di elementi.

$|bigcup_(j=1)^(n+1)A_j|=(n(n+1))/2$

Dunque se $n$ è multiplo di due allora il numero di elementi totali dispari. E quindi non si può dividere l'unione in due colori. Dunque se $n$ è multiplo di $4$ allora quella quantità può essere divisa in due colori. Però è una condizione sufficiente per la colorazione dell'unione. Dovrebbe verificarsi che poter colorare l'Unione con due colori implichi che gli $n+1$ insiemi possano essere colorati in modo di uguale quantità.

[anto_zoolander]

Ho fatto qualche passo e confermo che quella è una condizione soltanto necessaria(naturalmente data l'ambiguità del testo ci muoviamo con i piedi di piombo). Se $n=4k,forallkinNN$ allora $(n(n+1))/2$ è pari e quindi si ha questo.

$|A|=|bigcup_(j=1)^(n+1)A_j|=(n(n+1))/2$

è la cardinalità dell'insieme unione. $n=4k$ dunque $2k(4k+1)=4k^2+2k=2(4k^2+k)$ ovvero si può dividere in due quantità uguali. Siano esse dispari o pari. Ad esempio per $n=4$ si ha che $k=1$ e quindi l'insieme unione si può dividere in due quantità da $5$ elementi. Questa è dunque una condizione sufficiente per colorare l'insieme unione con solo due colori.

Possiamo dunque creare una partizione di $A$ con due insiemi, scegliendo metà elementi di un colore e metà di un altro.

$B_1,B_2subsetA:B_1capB_2=emptyset,B_1cupB_2=A$

in particolare

$|B_1|+|B_2|=(n(n+1))/4+(n(n+1))/4=(n(n+1))/2$

Ora $(((n(n+1))/2),((n(n+1))/4))$ rappresenta il numero di combinazioni possibili in cui posso colorare gli elementi dell'insieme unione a gruppi di $(|A|)/2$. Ora si può notare un'ulteriore cosa, ovvero che gli elementi posso essere disposti simmetricamente in una tabella

$ | ( - , a_(1,2) , a_(1,3) , ... , a_(1,k) ),( a_(2,1) , - , a_(2,3) , ... , a_(2,k) ),( a_(3,1) , a_(3,2) , - , ... , a_(3,k) ),( ... , ... , ... , - , ... ),( a_(k,1) , a_(k,2) , ... , a_(k,k-1) , - ) | $ un esempio $ | ( - , a_(1,2) , a_(1,3) , a_(1,4) , a_(1,5) ),( a_(2,1) , - , a_(2,3) , a_(2,4) , a_(2,5) ),( a_(3,1) , a_(3,2) , - , a_(3,4) , a_(3,5) ),( a_(4,1) , a_(4,2) , a_(4,3) , - , a_(4,5) ),( a_(5,1) , a_(5,2) , a_(5,3) , a_(5,4) , - ) | $

Si nota che colorando una fila, si colora anche una colonna e viceversa. Penso si possa dimostrare in qualche modo che vale per ogni multiplo di $4$ sfruttando qualche proprietà che deriva dalla tabella. In particolare una proprietà che penso abbiano è che se due tabelle contengono la stessa quantità di elementi e una si può colorare, allora si può colorare anche l'altra. Quindi essendo vera per $n=4$ ogni tabella da $4$ elementi può essere colorata in quel modo. Però questo vale solo per quella simmetrica, ovvero che ha quella striscia in mezzo e non per tutte le tabelle. Buh vado a dormire