Math problem

Toggle sidebar Toggle sidebar
M

Mark R

Diamond Member
Oct 9, 1999
8,513
16
81
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.
 
J

JoeFahey

Platinum Member
Jan 15, 2005
2,163
1
0
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.
 
S

smack Down

Diamond Member
Sep 10, 2005
4,507
0
0
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.
 
KoolAidKid

KoolAidKid

Golden Member
Apr 29, 2002
1,932
0
76
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.
 
J

JSFLY

Golden Member
Mar 24, 2006
1,068
0
0
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
 
M

Mark R

Diamond Member
Oct 9, 1999
8,513
16
81
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.
 
B

bsobel

Moderator Emeritus<br>Elite Member
Dec 9, 2001
13,346
0
0
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
 
X

xtknight

Elite Member
Oct 15, 2004
12,974
0
71
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?
 
J

JSFLY

Golden Member
Mar 24, 2006
1,068
0
0
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.
 
Y

yosuke188

Platinum Member
Apr 19, 2005
2,726
2
0
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
 
T

thesurge

Golden Member
Dec 11, 2004
1,745
0
0
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.
 
crt1530

crt1530

Diamond Member
Apr 15, 2001
3,194
0
0
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

COMPANY
RESOURCES
FOLLOW
Top Bottom