0

1

Suppose I have a set of finite sets: $X = \{V_1, V_2, V_3\}$ where each set called $V_i$ in $X$ contains a number of symbols (i.e. $V_1 = \{a,b,c\}$). $Z$ contains all of the Cartesian products of pairs of sets chosen from $X$. So in this case $Z = \{V_1 \times V_2, V_1 \times V_3, V_2 \times V_3\}$. A "word" is a set with each character at position $i$ drawn from the corresponding $V_i$. The set of all words is $W = V_1 \times V_2 \times V_3$. A "sentence" is an ordered set of "words" taken from $W$.

How many "sentences" of minimal length can I make such that every pair from $Z$ is in that "sentence" at least once? Minimal means fewest possible number of "words."

flag
Are $V_1,V_2,V_3$ disjoint sets? – Hsueh-Yung Lin Jun 16 2011 at 16:24
yes... I wouldn't consider pairs made from elements within a single $V_i$ to be valid. For example if $V_1 = \\{a,b,c\\}$ and $V_2 = \\{1,2,3\\}$, "words" starting with $\\{a,1,...\\}$ would be valid but "words" like ${a,a,...}$ or ${1,1,...}$ would not be since a "word" is an ordered set where each character at position $i$ may only be drawn from the corresponding $V_i$. – Misha Jun 16 2011 at 17:41
It is not clear to me what it means for a pair from $Z$ to be "in" a sentence. Your sentence is an ordered $n$-tuple of ordered triples; what do you mean by asking that a pair be in such an $n$-tuple? Maybe an example of sets $V_1,V_2,V_3$ together with a minimal sentence would help. – Gerry Myerson Jun 16 2011 at 23:41
Here's an example of what I mean: $V_1=\{a,b\}$, $V_2=\{c,d\}$, $V_3=\{e,f\}$. $V_1 \times V_2 \times V_3 = \{ace,acf,ade,adf,bce,bcf,bde,bdf\}$ There are 12 total pairs: $Z=\{\{ac,ad,bc,bd\},\{ae,af,be,bf\},\{ce,cf,de,df\}\}$. A minimal acceptable sentence is: $S=\{acf,ade,bce,bdf\}$. ...another is $\{ace,adf,bcf,bde\}$ – Misha Jun 17 2011 at 3:53
@Misha, thanks, now I think I understand the question (but regret I don't have a solution). Can you answer the question of how many minimal sentences there are in your example? – Gerry Myerson Jun 17 2011 at 12:29

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.