Coprire con catene

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
Tino
Livello 5
Livello 5
Messaggi: 221
Iscritto il: mer mag 25, 2005 9:20 am
Località: Verona

Coprire con catene

Messaggio da Tino »

Ciao!

Qual è il numero minimo di catene che occorre per coprire $P(\{1,\dots,n\})$?

Mi spiego meglio.

Fissiamo un intero $n \geq 1$ e definiamo $I_n := \{1,\dots,n\}$. Chiamiamo $P(I_n)$ l'insieme delle parti di $I_n$, cioè l'insieme dei sottoinsiemi di $I_n$, e lo pensiamo ordinato tramite la relazione di inclusione.

Una "catena" di $P(I_n)$ è un sottoinsieme totalmente ordinato di $P(I_n)$. In altre parole $C \subseteq P(I_n)$ si dice catena se per ogni $a,b \in C$ si ha $a \subseteq b$ oppure $b \subseteq a$. Un esempio di catena è questo: $\{\emptyset,\{1\},\{1,2\},\dots,\{1,\dots,n\}\}$.

Qual è il numero minimo di catene necessario a coprire tutto $P(I_n)$?

In altre parole: un insieme $\{C_1,\dots,C_m\}$ di catene di $P(I_n)$ si dice ricoprimento di $P(I_n)$ se vale $C_1 \cup \dots \cup C_m = P(I_n)$. Un ricoprimento si dice minimale se ha cardinalità minima. Qual è il valore di questa cardinalità minima?

Se n'è parlato qui (dove potete constatare i progressi fatti), e volevo sapere cosa ne pensate voi. Lì si parla di partizione tramite catene, ma il concetto è lo stesso: un ricoprimento tramite catene induce una partizione (basta togliere la roba in più: infatti un sottoinsieme di una catena è ancora una catena).
"Oh! But I have been blind- blind. Complex, I have said?
Complicated? Mais non. Of a simplicity extreme - extreme.
And miserable one that I am, I saw nothing - nothing."
(Peril At End House)

Rispondi