Maths Puzzle: Partitioning a set into two disjoint sets

Question

Le $X$ be the set of all non-empty subsets of $\{a,b,c,d,e,f\}$. So $X=\{a,b,c,d,e,f,ab,ac,ad,ae,af,bc,bd,be,bf,cd,ce,cf,de,df,ef,abc,\cdots,abcdef\}$; i.e., $|X|=63$. We want to partition $X$ into two disjoint sets $Y$ and $Z$ such that: (i) $|Y|=13$; (ii) Given any element $z \in Z$, $\exists ~ y_1,y_2 \in Y$ such that $y_1y_2=z$; (iii) If $x_1,x_2 \in Y$, then $x_1x_2 \notin Y$.

Note the following:

(1.) $(X,\cdot)$ is commutative: Given $ x=ab,y=cd\in X$, then $x \cdot y=(ab)(cd)=abcd=adbc=dcba=\cdots=cdab=y \cdot x$;

(2.) Two same letters cancels themselves: $(ab)(ac)=aabc=bc$.

My target is to find $Y$. I have tried many things to no avail. For instance, $Y$ cannot consist of all words of lengths $1$, $5$ and $6$ since this cannot yield all the words of length $3$ or $4$.

Any help in solving for $Y$ will be highly appreciated.

Answer 1

So I think this will work:

$$ Y = \{a, b, c, d, e, f, abce, bcdf, acde, bdef, acef, abdf, abcdef\} $$

That is, $Y$ consists of all one-letter sets, the four-letter set $abce$ and its "rotations", and the six-letter set $abcdef$. That no $y_1, y_2 \in Y$ admit $y_1 \cdot y_2 \in Y$ can be seen as follows:

• A one-letter set combined with a one-letter set produces a two-letter set or the empty set.

• A one-letter set combined with a four-letter set produces a three-letter set or a five-letter set.

• A one-letter set combined with the six-letter set produces a five-letter set.

• A four-letter set combined with the six-letter set produces a two-letter set.

• The six-letter set combined with itself produces the empty set.

None of those products can be in $Y$. That leaves the combination of two four-letter set. Consider $abcd$. Combined with itself, it produces the empty set. Combined with $acde$ or $acef$, it produces a two-letter set. Finally, combined with $bcdf, bdef, abdf$, respectively, it produces $adef, acdf, cdef$. None of those is in $Y$.

That all $z \in Z = X \backslash Y$ can be produced as $z = y_1 \cdot y_2$, with $y_1, y_2 \in Y$, can be seen as follows:

• The empty set and all one-letter sets are not in $Z$.

• All two-letter sets can be produced by combining the individual letters from $Y$.

• The three-letter set $abc$ can be produced as $abce \cdot e$. All of the "rotations" of $abc$ can be produced by rotating both of the elements from $Y$.

• The three-letter set $abd$ can be produced as $abdf \cdot f$. All of its "rotations" can be produced similarly.

• The three-letter set $abe$ can be produced as $abce \cdot c$. All of its "rotations" can be produced similarly.

• The three-letter set $ace$ can be produced as $abce \cdot b$. Its one rotation, $bdf$, can be produced similarly. There are no other three-letter sets.

• All five-letter sets can be produced by a combination of the six-letter set $abcdef$ with whichever letter is missing.

• There is, of course, no six-letter set in $Z$.

That leaves, again, the four-letter sets not in $Y$. $Y$ already contains all four-letter sets where the missing letters are $ac$, or its "rotations". The other four-letter sets can be produced as follows:

• The four-letter set $abcd$ can be produced as $bdef \cdot acef$. All of its "rotations" can be produced similarly.

• The four-letter set $abde$ can be produced as $bcdf \cdot acef$. All of its "rotations" can be produced similarly. There are no other four-letter sets.

---

The motivation behind this set's construction was something like this: It would be convenient if all sets in $Y$ of a given "length" were rotations of each other, for then the construction of all other sets could be easily shown.

What length to make the sets? Though the rules allowed for some "overlap" (that is, some $z$ would be produced through two or more combinations), the condition that $|Y| = 13$ didn't leave much room for waste, since $(13)(12)/2 = 78$ isn't that much greater than $|Z| = 50$.

It occurred to me that including all one-letter sets would produce all two-letter sets into the bargain. Introducing four-letter sets had the advantage that one-letter sets and four-letter sets cannot combine to produce themselves. That left a single set remaining, and the obvious choice was the sole six-letter set $abcdef$.

Then the only question remaining was which four-letter sets to contain. I first considered $abcd$, but that left a gap of two spaces ($ef$), and no combination would produce, say, $ace$, which lacks any gap of that size. The next guess was $abce$, and that works.

Answer 2

It has been pointed out in the comments that the problem is equivalent to the following: find a subset $Y$ of the vector space $V=\mathbb{F}_2^6$ such that $|Y|=13$, and $Y\oplus Y=V\setminus Y$.

Necessarily, the elements of $Y$ must be linearly independent (otherwise you could only get $32$ linear combinations, much less $50$ sums.) The conditions on $Y$ are invariant under invertible linear transformations, so we can assume without loss of generality that the density-one vectors (i.e. singleton subsets) are in $Y$.

Thus, all density-two vectors must be in $V\setminus Y$. We put two complementary density-three vectors into $Y$ -- we can assume these are $(1,1,1,0,0,0)$ and $(0,0,0,1,1,1)$ -- so that $(1,1,1,1,1,1)\in Y\oplus Y$. This leaves us $5$ vectors to choose in order to obtain all vectors of density $3$, $4$ and $5$. Since the singletons are in $Y$, we pick all $5$ of the remaining vectors to have density $4$, such that (a) each density-$5$ vector contains one of them (i.e. the density $4$ vectors taken together have a zero in every position), and (b) each density-$3$ vector is contained in one of the density-$4$ vectors. This is easy to do; one solution is: $${a, b, c, d, e, f, a b c, d e f, b c d f, a c d e, a b d f, a c e f, a c d f}$$

Incidentally, for $n=7$ letters, there is a solution with $|Y|=21$: $${a, b, c, d, e, f, g, a c e, a b c e f g, a c d f g, b e f g, b c g, a e f g, a d f, b c d f, a b f, a b d, a c d e f, d e f, c e f g, a b d f g}$$ I suspect it is optimal.