wu :: forums
wu :: forums - Boys and Girls Math Contest

Welcome, Guest. Please Login or Register.
Oct 31st, 2014, 4:59am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: william wu, Eigenray, Grimbal, SMQ, towr, Icarus, ThudnBlunder)
   Boys and Girls Math Contest
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Boys and Girls Math Contest  (Read 3905 times)
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Boys and Girls Math Contest  
« on: Oct 23rd, 2007, 2:05pm »
Quote Quote Modify 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: male
Posts: 599
Re: Boys and Girls Math Contest  
« Reply #1 on: Oct 24th, 2007, 4:56am »
Quote Quote Modify 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: male
Posts: 1105
Re: Boys and Girls Math Contest  
« Reply #2 on: Oct 24th, 2007, 5:27am »
Quote Quote Modify 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: male
Posts: 13173
Re: Boys and Girls Math Contest  
« Reply #3 on: Oct 24th, 2007, 5:36am »
Quote Quote Modify 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.
Wink
 
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: male
Posts: 1105
Re: Boys and Girls Math Contest  
« Reply #4 on: Oct 24th, 2007, 5:38am »
Quote Quote Modify Modify

Damn you found it. Wink
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
****





   
WWW

Gender: male
Posts: 578
Re: Boys and Girls Math Contest  
« Reply #5 on: Oct 24th, 2007, 5:42am »
Quote Quote Modify Modify

No, it doesn't matter how many questions there are. (I know because I googled the answer...) Embarassed
« Last Edit: Oct 24th, 2007, 6:45am by FiBsTeR » IP Logged
Hippo
Uberpuzzler
*****





   


Gender: male
Posts: 899
Re: Boys and Girls Math Contest  
« Reply #6 on: Oct 24th, 2007, 9:20am »
Quote Quote Modify 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 Smiley
« 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 Quote Modify 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: male
Posts: 13173
Re: Boys and Girls Math Contest  
« Reply #8 on: Oct 29th, 2007, 11:21am »
Quote Quote Modify 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 Quote Modify 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 Quote Modify 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: male
Posts: 405
Re: Boys and Girls Math Contest  
« Reply #11 on: Oct 29th, 2007, 8:13pm »
Quote Quote Modify 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 Quote Modify Modify

Mea culpa.   Embarassed  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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board