I am extremely stuck on how to go about this problem and any help would be so appreciated. We are told to consider the following combinatorial problem:
Unit Intersection: Let X = {1, 2,...,n}. Given a family of subsets $S_1,...,S_m$ of X, determine whether there is a subset T of X such that for all i,|T ∩ $S_i$| = 1 ?
I am then trying to prove that Unit Intersection is NP-complete using a reduction from Exactly-One-3SAT. In the Exactly-One-3SAT problem, we are given a 3CNF formula, and need to decide whether there is an assignment to the variables such that every clause contains exactly one true literal. In a 3CNF formula, every clause has at most three literals. A clause in a 3CNF formula may contain repeated literals.
I've been working for hours trying to find a way to even start this problem, but am so stuck right now. Thank you in advance for any help.