You spend some time with your preschool-age daughter trying to use up all of the magnet letters on the refrigerator to spell words that she knows. Formally, you have a set of letters and you are trying to form words such that each letter is used exactly once and all of the words collectively use all of the letters. Prove that this problem is NP-complete.
I thought that showing Set Packing $\le_p$ Using Up All Letters would be sufficient to show that the problem is NP-Complete. However, I'm having some trouble showing that if we have a set packing instance, then this implies there is a Using Up All Letters instance.
So suppose we have a Set Packing instance defined in the sense of the Wikipedia article. How does this show that there is an equivalent Using Up All Letters instance?
I know how to go in the reverse direction: suppose we have a Using Up All Letters instance, then we know this is also a Set Packing instance merely by how the problem of Using Up All Letters is defined (the universe is all of the letters, and the set of words that "covers" the universe is disjoint by definition). But, again, I'm having trouble going in the other direction.