1
$\begingroup$

Sam is a teacher. He teaches exotic materials (he's not a very computer fluent person and knows no programming). In his course he has several topics he teaches, say $a$, and each topic has a variable number of subtopics. The total number of subtopics in his course is $b$. In his exam (which is in essay form), the dean has stipulated that he can only set a maximum of $n$ questions, out of which students can select any $k$ questions to answer. Each of Sam's $n$ questions will have $c$ sub-questions.

Sam wants to design his questions so that no matter which of the $\binom{n}{k}$ question set his students choose, they'll find at least one question on each of the $b$ subtopics. Sam also wants to reduce the number of questions he sets. Loving efficiency, he wants to set the minimum number of $c$ that meets his requirements.

Can you give Sam an algorithm to help him out? Remember Sam is not computer fluent.

P.S: This is NOT a homework question. I made it up myself after writing an exam today that was similar to the above scenario.

I have not yet started a course on Algorithms and Data Structures. My knowledge (meagre as it is) is self taught.

Improve this question
$\endgroup$
5
  • 5
    $\begingroup$ What have you tried? Where did you get stuck? What is the origin of the problem? What is your question (the one you ask, not the one asked to you)? $\endgroup$
    – Evil
    Commented Dec 9, 2016 at 14:24
  • $\begingroup$ I made up this question. I wrote an exam in Networking today, and realised that tge questions were set such that all topics taught were covered(though we had one compulsory question). I have not yet started classes on Data Structures and Algorithms. I'm taking it next semester. My knowledge on it is self taught. I know my problem is related to set cover, but it seems differnt enough, that I thought it might be a different problem. That and I haven't reached algorithms for solving set cover yet in my textbook. $\endgroup$
    – Tobi Alafin
    Commented Dec 9, 2016 at 14:40
  • 3
    $\begingroup$ OK, glad to know that it's a self-composed problem. But still, that's not what this site is for. We expect that the answers to questions asked here will be useful to the person who asked the question. We're not looking for questions that are essentially a test to the answerer. We're here to help people understand computer science, not to prove that we can solve puzzles. $\endgroup$
    – David Richerby
    Commented Dec 9, 2016 at 14:49
  • $\begingroup$ I don't know the solution. I'm not "testing" anybody. It was a problem I thought up, and I wanted to see the solution for it. $\endgroup$
    – Tobi Alafin
    Commented Dec 9, 2016 at 14:51
  • $\begingroup$ @DavidRicherby, can you please at least tell me the formal name of my "problem"? I have not yet researched it(in part due to not knowing it's name) $\endgroup$
    – Tobi Alafin
    Commented Dec 9, 2016 at 14:58

1 Answer 1

Reset to default
1
$\begingroup$

Here is a more succinct formulation of your question:

Given three parameters $n,k,b$, find the minimum $c$ such that there exist $n$ sets $S_1,\ldots,S_n \subseteq \{1,\ldots,b\}$ of size $c$ such that the union of any $k$ of them is $\{1,\ldots,b\}$.

We can obtain a lower bound on $c$ as follows. Each element $i \in \{1,\ldots,b\}$ must appear in at least $n-k+1$ sets, since otherwise, we can choose $k$ sets not containing it. It follows that $cn \geq b(n-k+1)$, and so $$ c \geq \lceil \frac{n-k+1}{n} b \rceil. $$ Conversely, if each element $i \in \{1,\ldots,b\}$ appears in at least $n-k+1$ sets, then the sets are a solution for the problem. When $c = \lceil \frac{n-k+1}{n} b \rceil$, we can construct such a system in many different ways. For example, we can go over the elements repeatedly ($1,\ldots,c,1,\ldots,c,\ldots$), putting the first $c$ elements in the first set, the following $c$ elements in the second set, and so on. In total the $n$ sets contain $nc \geq (n-k+1)b$ elements, and so each element has appeared at least $n-k+1$ times. Since $c \leq b$, each of these occurrences is in a different set, and so each element appears in at least $n-k+1$ sets.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I have one question. Why is it $n$ times. I thought it was supposed to be $n C k$ times. Now unless $k$ is $1$ or $n-1$, I don't see how that is the case. That aside, is there a name for this problem? It seems different enough from Set cover. $\endgroup$
    – Tobi Alafin
    Commented Dec 9, 2016 at 21:05
  • $\begingroup$ I don't see why it should be $\binom{n}{k}$. Regarding the name, there are so many problems that not each and every one of them has a name. In fact, the vast majority don't. $\endgroup$
    – Yuval Filmus
    Commented Dec 9, 2016 at 21:07
  • $\begingroup$ The students have $n$ questions of which they can choose $k$. So they have $\binom{n}{k}$ ways of selecting the questions. Each of these $\binom{n}{k}$ question sets should cover the set $\{1 \dots b\}$. $\endgroup$
    – Tobi Alafin
    Commented Dec 9, 2016 at 21:22
  • $\begingroup$ Right, we both agree on the formulation of the question. That's just not how the lower bound works. It uses the technique of double counting, which I haven't spelled out in full. $\endgroup$
    – Yuval Filmus
    Commented Dec 9, 2016 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.