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 8:20 am
Località: Verona

Coprire con catene

Messaggio da Tino » ven mag 04, 2012 5:18 pm

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