The problem exactly:
Suppose you're helping to organize a summer sports camp, and the following problem comes up. For each of the n sports offered at this camp, the camp is supposed to have at least two counselors who are skilled at this sport. They have received job applications from m potential counselors. For each of the n sports, there is some subset of m applicants qualified in that sport. The question is: For a given k < m, is it possible to hire at most k of the counselors and have have at least two qualified in each of the n sports?
So, you are given a set U of elements, a collection of S1, S2...SM subsets of U, and an integer k. The original vertex-cover problem asks if there exists a collection of <= k of these sets whose union is equal to U. This question seems to ask how would we prove this is NP-Complete if we instead had to find a collection of <=k of these sets whose union covered the elements in U at least twice.
My first thought was to try to reduce the set cover problem. I was going to try to extend it to make it have to cover the union twice, but have no idea how to do that.
My next thought was to use 3-SAT since everything comes from that it seems, but I will die of old age before I figure that out.
My question is, what problem should I try to reduce from? Any could I get a hint for a first step to take? I've never proved one of these before so I'm really lost. I've been staring at this problem for 3 hours now.