• We’re currently investigating an issue related to the forum theme and styling that is impacting page layout and visual formatting. The problem has been identified, and we are actively working on a resolution. There is no impact to user data or functionality, this is strictly a front-end display issue. We’ll post an update once the fix has been deployed. Thanks for your patience while we get this sorted.

Math problem

M

Mark R

Diamond Member
An exam consisting of six questions is sat by 2006 children.

Each question is marked either right or wrong. Any three children have right answers to at least five of the six questions between them.

Let N be the total number of right answers achieved by all the children (i.e. the total number of questions solved by child 1 + the total solved by child 2 + · · · + the total solved by child 2006).

Find the least possible value of N.
 
1

EDIT: Well, let me explain. I'll "show my work" as my math teacher would always say.

Lets see...2006-42=1964*.25=491^0=1
Simple.
 
Any three children have right answers to at least five of the six questions between them.

So the lowest for this is 2 right for all but one of the children. The remaining child would get 1 right.
 
2005*2 + 1. 2005 students have 2 answers correct, 1 has one answer correct. Otherwise you could pick a group of three that has less than 5 correct between them. Just a guess.
 
Hes the answer, not that I understand it any.

Note that a child solving all six questions is overkill, that is, we can take away a question and the condition still holds. So everybody solves at most five.

Now note that, if three children solve exactly the same questions, they must obviously solve five each. Furthermore, for a set X of 4 questions, at most 2 students solve set X or a subset of it. There are 15 sets of 4 questions, so at most 30 students solve fewer than 5 questions. We can see that N=2006 \times 5 -30 is achievable: take 2 students solving each set of 4 questions and let the rest solve some five questions each. We want to show that this is best possible.

A set Y of 3 questions is contained in 3 sets X of 4 questions, so if Y is among the solved sets, there are 3 sets X which get a slot filled. A set of 2 questions is in 6 sets of 4 questions. A set of 1 question is in 10, and a set of none is in 15. There are 30 slots in total, and we fill them up with units (which gives us -1 on N), with 3s (which gives us -2), with 6s (which gives us -3), with 10s (which gives us -4) or with 15s (which gives us -5). Then it is obvious that we can get no more than -30 in total, and N=5 \times 2000 is best possible.

Answer
 
Sweet answer. So obvious in retrospect!

I'd pretty much given up on this problem because I couldn't think of a rigorous way of doing it.
 
Now note that, if three children solve exactly the same questions, they must obviously solve five each
Click to expand...

And that holds thru for any set of three, therefore 2006 * 5 = 10030

Furthermore, for a set X of 4 questions, at most 2 students solve set X or a subset of it. There are 15 sets of 4 questions, so at most 30 students solve fewer than 5 questions. We can see that N=2006 \times 5 -30 is achievable: take 2 students solving each set of 4 questions and let the rest solve some five questions each. We want to show that this is best possible.
Click to expand...

I don't see where you get the -30 from. Where did the set of questions come from, not in the original problem.

Bill
 
Originally posted by: JoeFahey
1

EDIT: Well, let me explain. I'll "show my work" as my math teacher would always say.

Lets see...2006-42=1964*.25=491^0=1
Simple.
Click to expand...

I are so confused. Perhaps you could show dimensional analysis of that?
 
Originally posted by: bsobel
Now note that, if three children solve exactly the same questions, they must obviously solve five each
Click to expand...

And that holds thru for any set of three, therefore 2006 * 5 = 10030

Furthermore, for a set X of 4 questions, at most 2 students solve set X or a subset of it. There are 15 sets of 4 questions, so at most 30 students solve fewer than 5 questions. We can see that N=2006 \times 5 -30 is achievable: take 2 students solving each set of 4 questions and let the rest solve some five questions each. We want to show that this is best possible.
Click to expand...

I don't see where you get the -30 from. Where did the set of questions come from, not in the original problem.

Bill
Click to expand...


Ask the math whiz who wrote the answer. Apparently some of the other math brains at Mathlinks agreed with his answer being correct, so I assume its correct. I dont think this problem is something that can be solved without knowledge of SETS and the like, so I don't feel bad that I can't get the right answer.
 
o = wrong x = right

x x x x x x o X 1976
o o x x x x x
o o x x x x x
o x o x x x x
o x o x x x x
o x x o x x x
o x x o x x x
o x x x o x x
o x x x o x x
o x x x x o x
o x x x x o x
o x x x x x o
o x x x x x o
x o x x x x o
x o x x x x o
x x o x x x o
x x o x x x o
x x x o x x o
x x x o x x o
x x x x o x o
x x x x o x o
x x x x x o o
x x x x x o o
x o o x x x x
x o o x x x x
x x o o x x x
x x o o x x x
x x x o o x x
x x x o o x x
x x x x o o x
x x x x o o x

(5*1976) + (4*30) = 10000
 
Originally posted by: bsobel
Now note that, if three children solve exactly the same questions, they must obviously solve five each
Click to expand...

And that holds thru for any set of three, therefore 2006 * 5 = 10030

Furthermore, for a set X of 4 questions, at most 2 students solve set X or a subset of it. There are 15 sets of 4 questions, so at most 30 students solve fewer than 5 questions. We can see that N=2006 \times 5 -30 is achievable: take 2 students solving each set of 4 questions and let the rest solve some five questions each. We want to show that this is best possible.
Click to expand...

I don't see where you get the -30 from. Where did the set of questions come from, not in the original problem.

Bill
Click to expand...

The "-30" comes from nCr(6,4) [combinations, this IS combinatorics, if you didn't notice the topic] for each of the two students (15 x 2).

edit: I can explain the answer more, if you guys want.

Bill, you are assuming that no child can solve less then 5. However, two children can solve the same 4 questions.
 
There are 15 ways to choose four correct answers from six possible answers (nCr(6,4)). This is the same as picking two incorrect answers out of six (nCr(6,2)). You can have at most two students with the same two incorrect answers in a grouping of three, or else they cannot have five correct answers. So, you can have at most 30 (15 ways to have two wrong times two students per way) students with four out of six correct answers. It is not possible to have students with three incorrect answers because you could not group them with two of the two incorrect answer people. So, you can have 1976 people with five correct answers and 30 with four correct to satisfy the condition in the question.
 
You must log in or register to reply here.

TRENDING THREADS

Back
Top