Author |
Topic: Boys and Girls Math Contest (Read 8525 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Boys and Girls Math Contest
« on: Oct 23rd, 2007, 2:05pm » |
 Quote  Modify
|
21 girls and 21 boys participate in a math competition. The results show that:
a) Each contestant solved at most six problems, and
b) For each pair of a girl and a boy, there was at least one problem that they both solved.
Prove that there is a problem that was solved by at least three girls and at least three boys.
Source: IMO 2001
|
|
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Ghost Sniper
Senior Riddler
Do not hide. It is useless.
Gender:
Posts: 599
|
|
Re: Boys and Girls Math Contest
« Reply #1 on: Oct 24th, 2007, 4:56am » |
Quote Modify
|
How many problems are there? Or does it not matter?
|
|
IP Logged |
*sob* I miss my mommy... *blows nose* huh, I'm on? oh right.
(thinks to self) Time for my speech to these college kids.
"Reason is more important than all emotions..."
|
|
|
mikedagr8
Uberpuzzler
A rich man is one who is content; not wealthy.
Gender:
Posts: 1105
|
|
Re: Boys and Girls Math Contest
« Reply #2 on: Oct 24th, 2007, 5:27am » |
Quote Modify
|
on Oct 24th, 2007, 4:56am, Ghost Sniper wrote:| How many problems are there? Or does it not matter? |
|
I'm fairly confident here that you have to figure out how many questions there are.
Someone correct me if I am wrong.
|
| « Last Edit: Oct 24th, 2007, 5:37am by mikedagr8 » |
IP Logged |
"It's not that I'm correct, it's that you're just not correct, and so; I am right." - M.P.E.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Boys and Girls Math Contest
« Reply #3 on: Oct 24th, 2007, 5:36am » |
Quote Modify
|
on Oct 24th, 2007, 5:27am, DC1E2L wrote:I'm fairly confident here that you have to figure out how many questions there are.
Someone correect me if I am wrong. |
|
I don't think it matters how many questions there are in total.
|
| « Last Edit: Oct 24th, 2007, 5:37am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
mikedagr8
Uberpuzzler
A rich man is one who is content; not wealthy.
Gender:
Posts: 1105
|
|
Re: Boys and Girls Math Contest
« Reply #4 on: Oct 24th, 2007, 5:38am » |
Quote Modify
|
Damn you found it.
|
|
IP Logged |
"It's not that I'm correct, it's that you're just not correct, and so; I am right." - M.P.E.
|
|
|
FiBsTeR
Senior Riddler
Gender:
Posts: 581
|
|
Re: Boys and Girls Math Contest
« Reply #5 on: Oct 24th, 2007, 5:42am » |
Quote Modify
|
No, it doesn't matter how many questions there are. (I know because I googled the answer...) 
|
| « Last Edit: Oct 24th, 2007, 6:45am by FiBsTeR » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Boys and Girls Math Contest
« Reply #6 on: Oct 24th, 2007, 9:20am » |
Quote Modify
|
Make a sheet 21x21 rows are boys, columns are girls. For each problem color it boy if at least 3 boys solved it, color it girl if at least 3 girls solved it. Write to the corresponding cell of the table an arbitrary problem solved by both the girl and the boy and if the problem is colored, color the cell. Suppose at first no cell is colored both girl and boy.
Lemma:Now in each row(boy) there is at least 11 girl colored cells, and in each column(girl) there is at least 11 boy colored cells.
Summed together there are at least 21*11 girl colored cells and 21*11 boy colored cells 21*11*2>21*21 therefore a cell is colored by both boy and girl ... contradiction.
So the lemma: For a given person, maximize the number of problems solved by the person which were solved by at most 2 persons of opposite sex. Clearly 2x5 is the maximum, therefore 21-10=11 is the lower bound for the number of problems colored by the opposite sex.
Uf, fast like in 17 
|
| « Last Edit: Oct 25th, 2007, 11:25am by Hippo » |
IP Logged |
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Boys and Girls Math Contest
« Reply #7 on: Oct 29th, 2007, 10:41am » |
Quote Modify
|
I'm not convinced of Hippo's solution. Specifically, suppose we know that the cell intersecting boy A and girl B have both "colors." How can we be sure it's the same problem? Perhaps there was one problem solved by all the boys and B, and a second problem solved by all the girls and A?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Boys and Girls Math Contest
« Reply #8 on: Oct 29th, 2007, 11:21am » |
Quote Modify
|
on Oct 29th, 2007, 10:41am, Joe Fendel wrote:| I'm not convinced of Hippo's solution. Specifically, suppose we know that the cell intersecting boy A and girl B have both "colors." How can we be sure it's the same problem? Perhaps there was one problem solved by all the boys and B, and a second problem solved by all the girls and A? |
|
It only has a color for boys and for girls if at least three of each solved it..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Boys and Girls Math Contest
« Reply #9 on: Oct 29th, 2007, 11:31am » |
Quote Modify
|
on Oct 29th, 2007, 11:21am, towr wrote:
It only has a color for boys and for girls if at least three of each solved it.. |
|
Not exactly, towr. I think you're confusing "it" a problem and "it" a (boy, girl) pair.
The cell intersecting row A and column B has a color for boys if there exists a problem X solved by boy A and girl B and at least two other boys. If this same cell has a color for girls, then there exists a problem Y solved by these two and at least two other girls. But there is no guarantee that these are the same problem. X might be colored for boys and Y might be colored for girls, and they might both be in the (A, B) cell, but then we still don't have a single problem solved by 3 boys and 3 girls.
|
|
IP Logged |
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Boys and Girls Math Contest
« Reply #10 on: Oct 29th, 2007, 1:07pm » |
Quote Modify
|
I think that this same approach works if we just tweak it a bit.
| hidden: | Let's keep the 21 x 21 grid. We'll put a BLUE dot in the cell intersecting boy A and girl B if A and B have co-solved some problem which was solved by FEWER than 2 other boys. We'll put a pink dot in the cell if they co-solved a problem which was solved by fewer than 2 other girls.
For each boy, the number of pink dots in their row can be no more than 10. That's because any problem they co-solved with fewer than 3 girls can supply at most 2 dots, and there can be at most 5 such problems. Hence the total number of pink dots on the grid at most 210. Similarly the total number of blue dots on the grid is at most 210. Thus there are 21*21 - 210*2 = at least 21 squares with no dots. Pick any boy and girl whose intersection contains no dots. They co-solved some problem. But the lack of dots indicates that this problem must have been solved by at least 3 boys AND at least 3 girls. |
This is a nice puzzle. I've actually been thinking about it for days along the same lines Hippo suggested (and couldn't get past the issue I describe above), but seeing the solution formulated so clearly helped a lot.
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Boys and Girls Math Contest
« Reply #11 on: Oct 29th, 2007, 8:13pm » |
Quote Modify
|
Although I had trouble at first grasping Hippo's beautiful solution, I have to conclude that his solution is actually perfectly clear!
Each cell is associated with exactly one problem solved by both the boy and girl labelling that cell. That's why "we can be sure it's the same problem". Hence each cell in a particular row is associated with exactly one of the at most 6 problems solved by the boy labelling that row. The beauty of Hippo's idea is that, for that row, his lemma applies only to those at most 6 problems and the 21 girls! Sufficient information to show that there are at least 11 girl-colored cells in that row! Looking at more problems than those 6 can only increase the number of girl-colored cells in that row.
Not sure, Joe Fendel, but I think your solution is no different from Hippo's, and is less clear.
|
|
IP Logged |
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Boys and Girls Math Contest
« Reply #12 on: Oct 30th, 2007, 8:46am » |
Quote Modify
|
Mea culpa. ecoist is absolutely correct. The solutions are in essence identical, and I now agree that Hippo's is a more natural, intuitive application of pigeonhole principle. Bravo to both of you!
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print