Unioni massimalizzanti
Salve a tutti.
Bazzicando per vie impervie sono giunto al seguente problema (eventualmente lo contestualizzerò meglio se a qualcuno interessa):
Sia $X$ un insieme finito, e sia $T$ un insieme di sottoinsiemi di $X$ tutti della stessa cardinalità $t$. Dati $A_1,...,A_n in T$, chiamiamo $c(A_1...A_n)$ la cardinalità dell'unione $A_1 uu ... uu A_n$, e chiamiamo $c_n$ il massimo dei $c(A_1...A_n)$ al variare di $A_1,...,A_n in T$.
Chiamiamo $n$-massimalizzante un sottoinsieme ${A_1,...,A_n}$ di $T$ tale che $c(A_1...A_n)=c_n$.
La domanda è questa: è vero che fissato $n$, ogni $n$-massimalizzante contiene un $(n-1)$-massimalizzante?
Ci tengo ad osservare che tutti gli elementi di $T$ hanno la stessa cardinalità, altrimenti la risposta sarebbe banalmente no: per esempio se prendo $T={{1,2},{3,4,5,6,7},{1,2,3,4,5,6}}$ dentro $X={1,2,3,4,5,6,7}$, allora ${{1,2},{3,4,5,6,7}}$ è un $2$-massimalizzante che non contiene $1$-massimalizzanti.
Mi sembra interessante, secondo me la risposta è sì anche se non sono ancora riuscito a provarlo. Mi scuso se esiste una soluzione immediata, non sono ancora in grado di determinare a occhio il grado di difficoltà di un problema.
Bazzicando per vie impervie sono giunto al seguente problema (eventualmente lo contestualizzerò meglio se a qualcuno interessa):
Sia $X$ un insieme finito, e sia $T$ un insieme di sottoinsiemi di $X$ tutti della stessa cardinalità $t$. Dati $A_1,...,A_n in T$, chiamiamo $c(A_1...A_n)$ la cardinalità dell'unione $A_1 uu ... uu A_n$, e chiamiamo $c_n$ il massimo dei $c(A_1...A_n)$ al variare di $A_1,...,A_n in T$.
Chiamiamo $n$-massimalizzante un sottoinsieme ${A_1,...,A_n}$ di $T$ tale che $c(A_1...A_n)=c_n$.
La domanda è questa: è vero che fissato $n$, ogni $n$-massimalizzante contiene un $(n-1)$-massimalizzante?
Ci tengo ad osservare che tutti gli elementi di $T$ hanno la stessa cardinalità, altrimenti la risposta sarebbe banalmente no: per esempio se prendo $T={{1,2},{3,4,5,6,7},{1,2,3,4,5,6}}$ dentro $X={1,2,3,4,5,6,7}$, allora ${{1,2},{3,4,5,6,7}}$ è un $2$-massimalizzante che non contiene $1$-massimalizzanti.
Mi sembra interessante, secondo me la risposta è sì anche se non sono ancora riuscito a provarlo. Mi scuso se esiste una soluzione immediata, non sono ancora in grado di determinare a occhio il grado di difficoltà di un problema.
Risposte
il problema mi interessa molto, ma non mi sono chiare alcune notazioni.
hai chiamato $t$ la cardinalità di ciascun sottoinsieme, ed hai specificato bene che cosa intendi.
però nella formulazione del problema hai usato sempre $n$ come pedice "massimo": questo significa che vanno considerati sempre $n$ sottoinsiemi di $X$ per definire $c$ (cioè sempre lo stesso numero di elementi di $T$)?
è proprio questo che intendi nella domanda (nel senso che analogamente si può definire $c_(n-1)$)?
un'ultima cosa: non è specificato che l'unione di tutti gli elementi di $T$ debba essere $X$, dunque può anche essere un sottoinsieme proprio di $X$ ?
ciao.
hai chiamato $t$ la cardinalità di ciascun sottoinsieme, ed hai specificato bene che cosa intendi.
però nella formulazione del problema hai usato sempre $n$ come pedice "massimo": questo significa che vanno considerati sempre $n$ sottoinsiemi di $X$ per definire $c$ (cioè sempre lo stesso numero di elementi di $T$)?
è proprio questo che intendi nella domanda (nel senso che analogamente si può definire $c_(n-1)$)?
un'ultima cosa: non è specificato che l'unione di tutti gli elementi di $T$ debba essere $X$, dunque può anche essere un sottoinsieme proprio di $X$ ?
ciao.
Ciao ada 
Lo dico meglio: fissato $n$, posso considerare l'insieme $\mathfrak{T}(n)$ degli insiemi del tipo ${A_1,...,A_n} subseteq T$, cioè i sottoinsiemi di $T$ di $n$ elementi, e ad ogni elemento ${A_1,...,A_n} in \mathfrak{T}(n)$ posso associare la $c(A_1...A_n)=|A_1 uu ... uu A_n|$ (questa "c" rimane definita indipendentemente da $n$, potevo scrivere direttamente $|A_1 uu ... uu A_n|$, ho usato "c" per uniformità di notazione). Sicuramente esiste ${bar(A_1),...,bar(A_n)} in \mathfrak{T}(n)$ tale che $c(A_1...A_n) le c(bar(A_1)...bar(A_n))$ per ogni ${A_1,...,A_n} in \mathfrak{T}(n)$ (basta prenderlo in modo che la cardinalità dell'unione sia massima). Ora $c(bar(A_1)...bar(A_n))$ è ben determinato e lo chiamo $c_n$ (ovviamente dipende da $n$).
Faccio tutto questo per ogni $n$.
In tutto questo la $t$ entra in gioco solo nel senso che $|A|=t$ per ogni $A in T$, non vedo "intrecciamenti" possibili tra $n$ e $t$
Sì, può essere un sottoinsieme proprio.
Però se ciò infastidisce si può anche eliminare da $X$ tutti gli elementi che non stanno in qualche elemento di $T$, perché questi ce li possiamo benissimo dimenticare: supporre che l'unione degli elementi di $T$ dia $X$ non è restrittivo.
Ah un'altra domanda non meno interessante: se si procede per massimalizzazioni successive si ottiene un'unione massimale?
Mi spiego meglio: se $|A_1 uu ... uu A_n|=c_n$ allora è vero che esiste $A_{n+1} in T$ tale che $|A_1 uu ... uu A_n uu A_{n+1}|=c_{n+1}$ ?
"adaBTTLS":
però nella formulazione del problema hai usato sempre $n$ come pedice "massimo": questo significa che vanno considerati sempre $n$ sottoinsiemi di $X$ per definire $c$ (cioè sempre lo stesso numero di elementi di $T$)?
Lo dico meglio: fissato $n$, posso considerare l'insieme $\mathfrak{T}(n)$ degli insiemi del tipo ${A_1,...,A_n} subseteq T$, cioè i sottoinsiemi di $T$ di $n$ elementi, e ad ogni elemento ${A_1,...,A_n} in \mathfrak{T}(n)$ posso associare la $c(A_1...A_n)=|A_1 uu ... uu A_n|$ (questa "c" rimane definita indipendentemente da $n$, potevo scrivere direttamente $|A_1 uu ... uu A_n|$, ho usato "c" per uniformità di notazione). Sicuramente esiste ${bar(A_1),...,bar(A_n)} in \mathfrak{T}(n)$ tale che $c(A_1...A_n) le c(bar(A_1)...bar(A_n))$ per ogni ${A_1,...,A_n} in \mathfrak{T}(n)$ (basta prenderlo in modo che la cardinalità dell'unione sia massima). Ora $c(bar(A_1)...bar(A_n))$ è ben determinato e lo chiamo $c_n$ (ovviamente dipende da $n$).
Faccio tutto questo per ogni $n$.
In tutto questo la $t$ entra in gioco solo nel senso che $|A|=t$ per ogni $A in T$, non vedo "intrecciamenti" possibili tra $n$ e $t$
un'ultima cosa: non è specificato che l'unione di tutti gli elementi di $T$ debba essere $X$, dunque può anche essere un sottoinsieme proprio di $X$ ?
Sì, può essere un sottoinsieme proprio.
Però se ciò infastidisce si può anche eliminare da $X$ tutti gli elementi che non stanno in qualche elemento di $T$, perché questi ce li possiamo benissimo dimenticare: supporre che l'unione degli elementi di $T$ dia $X$ non è restrittivo.
Ah un'altra domanda non meno interessante: se si procede per massimalizzazioni successive si ottiene un'unione massimale?
Mi spiego meglio: se $|A_1 uu ... uu A_n|=c_n$ allora è vero che esiste $A_{n+1} in T$ tale che $|A_1 uu ... uu A_n uu A_{n+1}|=c_{n+1}$ ?
ciao, Martino, grazie del chiarimento.
ma, a questo punto, una domanda sorge spontanea: gli $A_i$, $i=1,2, ..., n$ "devono" essere distinti?
ma, a questo punto, una domanda sorge spontanea: gli $A_i$, $i=1,2, ..., n$ "devono" essere distinti?
"adaBTTLS":
gli $A_i$, $i=1,2, ..., n$ "devono" essere distinti?
Non necessariamente.
"Martino":
se si procede per massimalizzazioni successive si ottiene un'unione massimale?
Mi spiego meglio: se $|A_1 uu ... uu A_n|=c_n$ allora è vero che esiste $A_{n+1} in T$ tale che $|A_1 uu ... uu A_n uu A_{n+1}|=c_{n+1}$ ?
Mi sono (banalmente) risposto no: se prendo $X={1,2,3,4,5}$ e $T={{1,2},{2,3},{1,3},{2,4},{1,4},{2,5}}$ e parto da ${1,2}$ non posso raggiungere $c_2=c({1,3} uu {2,4})=4$ aggiungendo un elemento di $T$ dato che nessun elemento di $T$ e' disgiunto da ${1,2}$.
con l'esempio che hai fatto, hai preso $t=2$. allora "pretenderesti" che la tesi sia valida per ogni $t$ ? (da 0 o da 1 a |X| ?)
ciao.
PS: ho detto questo perché io mi sarei immaginata una conclusione del tipo "la tesi è valida per quei t tali che... (oppure per t=....)"
ciao.
PS: ho detto questo perché io mi sarei immaginata una conclusione del tipo "la tesi è valida per quei t tali che... (oppure per t=....)"
No, ma il fatto che esista un controesempio per $t=2$ mi fa pensare che ne esistano per ogni $t$. In ogni caso nella seconda domanda che avevo posto $t$ era fissato ma arbitrario, quindi la risposta a tale domanda è no. A questo punto, secondo me si può sempre massimalizzare a tacche in modo sufficientemente "stupido" in modo che il risultato non sia globalmente massimale.
la risposta alla prima domanda sembrerebbe essere NO.
ti scrivo brevemente un controesempio, con |X|=6, t=n=4, $c_3=c_2=6$, uno dei 3-massimalizzanti è ${A_2,A_3,A_4}$, ma l'unico 2-massimalizzante è ${A_1,A_4}$:
$A_1={1,2,4,5}," "A_2={1,3,4,5}," "A_3={2,4,5,6}," "A_4={3,4,5,6}$.
spero di non aver toppato né nell'interpretazione né nell'esempio, e di essere stata chiara. ciao.
ti scrivo brevemente un controesempio, con |X|=6, t=n=4, $c_3=c_2=6$, uno dei 3-massimalizzanti è ${A_2,A_3,A_4}$, ma l'unico 2-massimalizzante è ${A_1,A_4}$:
$A_1={1,2,4,5}," "A_2={1,3,4,5}," "A_3={2,4,5,6}," "A_4={3,4,5,6}$.
spero di non aver toppato né nell'interpretazione né nell'esempio, e di essere stata chiara. ciao.
"adaBTTLS":
la risposta alla prima domanda sembrerebbe essere NO.
ti scrivo brevemente un controesempio, con |X|=6, t=n=4, $c_3=c_2=6$, uno dei 3-massimalizzanti è ${A_2,A_3,A_4}$, ma l'unico 2-massimalizzante è ${A_1,A_4}$:
$A_1={1,2,4,5}," "A_2={1,3,4,5}," "A_3={2,4,5,6}," "A_4={3,4,5,6}$.
Mi sembra che anche ${A_2,A_3}$ sia un 2-massimalizzante.
ho toppato nell'esempio, ma ormai credo di aver trovato la strada. propongo quest'altro esempio:
$X={1,2,3,4,5,6}," "A_1={1,2,4}," "A_2={1,4,5}," "A_3={2,4,5}," "A_4={3,5,6}$
$|X|=6," "t=3," "n=4," "c_4=c_3=c_2=6," "c_1=3$
questa volta dovrebbe essere vera la stessa condizione scritta erroneamente per l'altro esempio:
uno dei $3$-massimizzanti è ${A_2,A_3,A_4}$, mentre l'unico $2$-massimizzante è ${A_1,A_4}$.
a presto. ciao.
$X={1,2,3,4,5,6}," "A_1={1,2,4}," "A_2={1,4,5}," "A_3={2,4,5}," "A_4={3,5,6}$
$|X|=6," "t=3," "n=4," "c_4=c_3=c_2=6," "c_1=3$
questa volta dovrebbe essere vera la stessa condizione scritta erroneamente per l'altro esempio:
uno dei $3$-massimizzanti è ${A_2,A_3,A_4}$, mentre l'unico $2$-massimizzante è ${A_1,A_4}$.
a presto. ciao.
Hai ragione. Grazie
prego.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo