Question

Your friends’ preschool-age daughter Madison has recently learned to spell some simple words. To help encourage this, her parents got her a colorful set of refrigerator magnets featuring the letters of the alphabet (some number of copies of the letter A, some number of copies of the letter B, and so on), and the last time you saw her the two of you spent a while arranging the magnets to spell out words that she knows. Somehow with you and Madison, things always end up getting more elaborate than originally planned, and soon the two of you were trying to spell out words so as to use up all the magnets in the full set – that is, picking words that she knows how to spell so that once they were all spelled out, each magnet was participating in the spelling of exactly one of the words. (Multiple copies of words are okay here; so for example, if the set of refrigerator magnets includes two copies of each of ‘C,’ ‘A,’ and ‘T,’ it would be okay to spell out "CAT" twice.) This turned out to be pretty difficult, and it was only later that you realized a plausible reason for this. Suppose we consider a general version of the problem of Using Up All the Refrigerator Magnets, where we replace the English alphabet by an arbitrary collection of symbols, and we model Madison’s vocabulary as an arbitrary set of strings over this collection of symbols. Prove that Using Up All the Refrigerator Magnets is NP-complete.

Answer 1

Answer:

Check the explanation

Explanation:

Given a collection SS of subsets of a set X, an exact cover of X is a subcollection S∗S∗ of SS that satisfies two conditions:

• The intersection of any two distinct subsets in S∗S∗ is empty, i.e., the subsets in S∗S∗ are pairwise disjoint. In other words, each element in X. is contained in at most one subset in S∗S∗.
• The union of the subsets in S∗S∗ is X, i.e., the subsets in S∗S∗ cover X. In other words, each element in XX is contained in at least one subset in S∗S∗.

XX is the collection of letters on the refrigerator.

SS is the collection of words that your daughter knows that are made up of letters in X.

S∗S∗ is a subcollection of words from SS that exactly cover X.