Author 
Topic: Boys and Girls Math Contest (Read 3381 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291


Boys and Girls Math Contest
« on: Oct 23^{rd}, 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 24^{th}, 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 24^{th}, 2007, 5:27am » 
Quote Modify

on Oct 24^{th}, 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 24^{th}, 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: 13145


Re: Boys and Girls Math Contest
« Reply #3 on: Oct 24^{th}, 2007, 5:36am » 
Quote Modify

on Oct 24^{th}, 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 24^{th}, 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 24^{th}, 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: 578


Re: Boys and Girls Math Contest
« Reply #5 on: Oct 24^{th}, 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 24^{th}, 2007, 6:45am by FiBsTeR » 
IP Logged 



Hippo
Uberpuzzler
Gender:
Posts: 899


Re: Boys and Girls Math Contest
« Reply #6 on: Oct 24^{th}, 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 2110=11 is the lower bound for the number of problems colored by the opposite sex. Uf, fast like in 17

« Last Edit: Oct 25^{th}, 2007, 11:25am by Hippo » 
IP Logged 



Joe Fendel
Full Member
Posts: 158


Re: Boys and Girls Math Contest
« Reply #7 on: Oct 29^{th}, 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: 13145


Re: Boys and Girls Math Contest
« Reply #8 on: Oct 29^{th}, 2007, 11:21am » 
Quote Modify

on Oct 29^{th}, 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 29^{th}, 2007, 11:31am » 
Quote Modify

on Oct 29^{th}, 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 29^{th}, 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 cosolved some problem which was solved by FEWER than 2 other boys. We'll put a pink dot in the cell if they cosolved 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 cosolved 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 cosolved 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 29^{th}, 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 girlcolored cells in that row! Looking at more problems than those 6 can only increase the number of girlcolored 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 30^{th}, 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 



