Math Is Fun Forum

monicao

Member

Registered: 2007-10-10

Posts: 6

A test problem...

I found this problem and I couldn't get the ideea... I thought that the minimum number of questions is 15... but what do you think?

Ten teachers are assigned to evaluate a multiple choice test. In order to secure the privacy of the examination, each teacher was given only the answers of some of the questions. The point is to guarentee the gathering of at least five teachers for getting answers to all of the questions. (That is to say, no combination of four or less teachers will be able to collect all the answers, whereas any combination of five or more teachers will be able to collect them all).

What is the minimum possible number of questions in this test and at least how many answers should be given to each teacher?

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: A test problem...

Well, I can only say that the answer must be less than or equal to 210. This is my proof.

The first thing to note is that each answer must be given to at least 6 teachers – otherwise there would be 5 teachers who wouldn’t have one particular answer and this combination of five teachers wouldn’t have the complete set of answers. And since we want that no four teachers have the complete set, we may as well assume that each answer is given to exactly 6 teachers.

Thus, if there are

questions, we can arrange things so that given any four teachers, there will be (exactly) one answer which is not given to these four and so they will not have the complete set. On the other hand any five teachers will have the complete set. If not, it would mean that one answer has not been given to these five teachers – but we have already given every answer to six teachers so this cannot arise.

If 210 is the answer, then each teacher will have

questions. However I can’t prove that 210 is actually the minimum number; all I’ve proved is that 210 works.

Last edited by JaneFairfax (2009-11-10 20:29:11)

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: A test problem...

Here is a smaller example to illustrate my point.

Suppose there are only 5 teachers, and we want that every combination of three or more teachers will have the complete set of answers but no combination or two or fewer teachers will. In this case each answer must be given to at least 3 teachers (otherwise there would be three teachers who don’t have the complete set). Assume then that each answer is given to exactly 3 teachers. And now, if there are

questions, we can arrange things so that given any two teachers, there will be exactly one question which is not given to them, as follows.

Teacher 1: {1,2,3,4,5,6}
Teacher 2: {1,2,3,7,8,9}
Teacher 3: {1,4,5,7,8,10}
Teacher 4: {2,4,6,7,9,10}
Teacher 5: {3,5,6,8,9,10}

Thus no two teachers have the complete set but any three teachers do. Again 10 may not be the minimum answer, but, as you can see for yourself, it works.

monicao

Member

Registered: 2007-10-10

Posts: 6

Re: A test problem...

Jane, I see your point, and you're right, but we had 10 teachers... what should be the minimum number of questions?

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: A test problem...

Well, unless I see a counterexample, I will stick to 210 as the answer.

Avon

Member

Registered: 2007-06-28

Posts: 80

Re: A test problem...

In order to satisfy the condition that no set of four teachers has all of the answers but every set of five does we must have that for any set S of four teachers there is a question Q_S such that the four teachers in S don't have the answer to Q_S but the other six all do.

If S and T are two sets of four teachers and Q_S = Q_T then we must have S = T since S is the set of teachers who don't have the answer to Q_S and T is the set of teachers who don't have the answer to Q_T. Therefore we must have at least as many questions are there are sets of four teachers.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: A test problem...

HI;

http://www.mymathforum.com/viewtopic.php?f=27&t=10712

I am not backing the above answer up because frankly I am not following their analysis at all. I am just providing it.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: A test problem...

If S and T are two sets of four teachers and Q_S = Q_T then we must have S = T since S is the set of teachers who don't have the answer to Q_S and T is the set of teachers who don't have the answer to Q_T. Therefore we must have at least as many questions are there are sets of four teachers.

It took me a while but I finally understood it all.

To elaborate, the condition that no four (or fewer) teachers know all the answers means that if

are four teachers, there is an answer

such that none of

don’t have

. Now, suppose that

are

are distinct sets of four teachers such that there is an answer

such that

don’t have

and

don’t have the same answer

. Since the sets of four are distinct, there is some

such that

. But if

don’t have

, then the other six teachers must have

(since every answer must be given to (at least) six teachers) – and

is one of these six teachers! Contradiction! Therefore, given distinct sets of four teachers, there must be distinct answers which they don’t have. Hence the total number of answers must be at least the total number of selections of four teachers, i.e.

.

Thanks Avon! You’re a genius.

Last edited by JaneFairfax (2009-11-12 22:50:09)

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: A test problem...

To generalize:

Suppose there are

teachers

and given

, we want that any

or more teachers know all the answers but no

or fewer teachers will know all the answers. Then the minimum number of questions is

and each teacher is given

answers.

scientia

Member

Registered: 2009-11-13

Posts: 224

Re: A test problem...

none of

don’t have

.

You mean none of

has

.

To generalize:

Suppose there are

teachers

and given

, we want that any

or more teachers know all the answers but no

or fewer teachers will know all the answers. Then the minimum number of questions is

and each teacher is given

answers.

That is a very good generalization.