Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2009-11-10 05:11:36

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?

Offline

#2 2009-11-10 20:14:28

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)

Offline

#3 2009-11-10 20:32:28

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.

Offline

#4 2009-11-11 02:49:04

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?

Offline

#5 2009-11-11 04:32:39

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.

Offline

#6 2009-11-11 09:08:58

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.

Offline

#7 2009-11-12 19:25:23

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.

Offline

#8 2009-11-12 22:40:38

JaneFairfax
Member
Registered: 2007-02-23
Posts: 6,868

Re: A test problem...

Avon wrote:

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. thumbup.gif

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! kiss You’re a genius. notworthy.gif

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

Offline

#9 2009-11-13 00:28:41

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.

Offline

#10 2009-11-13 11:01:30

scientia
Member
Registered: 2009-11-13
Posts: 224

Re: A test problem...

JaneFairfax wrote:

none of
don’t have
.

You mean none of
has
. wink

JaneFairfax wrote:

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. smile

Offline

Board footer

Powered by FluxBB