wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> hard >> Boys and Girls Math Contest
(Message started by: william wu on Oct 23rd, 2007, 2:05pm)

Title: Boys and Girls Math Contest
Post by william wu on Oct 23rd, 2007, 2:05pm
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

Title: Re: Boys and Girls Math Contest
Post by Ghost Sniper on Oct 24th, 2007, 4:56am
How many problems are there? Or does it not matter?

Title: Re: Boys and Girls Math Contest
Post by DC1E2L on Oct 24th, 2007, 5:27am

on 10/24/07 at 04:56:49, 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.

Title: Re: Boys and Girls Math Contest
Post by towr on Oct 24th, 2007, 5:36am

on 10/24/07 at 05:27:01, 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.

Title: Re: Boys and Girls Math Contest
Post by DC1E2L on Oct 24th, 2007, 5:38am
Damn you found it. ;)

Title: Re: Boys and Girls Math Contest
Post by FiBsTeR on Oct 24th, 2007, 5:42am
No, it doesn't matter how many questions there are. (I know because I googled the answer...)  :-[

Title: Re: Boys and Girls Math Contest
Post by Hippo on Oct 24th, 2007, 9:20am
[hide]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 :)
[/hide]

Title: Re: Boys and Girls Math Contest
Post by Joe Fendel on Oct 29th, 2007, 10:41am
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?

Title: Re: Boys and Girls Math Contest
Post by towr on Oct 29th, 2007, 11:21am

on 10/29/07 at 10:41:49, 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..

Title: Re: Boys and Girls Math Contest
Post by Joe Fendel on Oct 29th, 2007, 11:31am

on 10/29/07 at 11:21:14, 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.

Title: Re: Boys and Girls Math Contest
Post by Joe Fendel on Oct 29th, 2007, 1:07pm
I think that this same approach works if we just tweak it a bit.  

[hideb]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.[/hideb]

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.

Title: Re: Boys and Girls Math Contest
Post by ecoist on Oct 29th, 2007, 8:13pm
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.

Title: Re: Boys and Girls Math Contest
Post by Joe Fendel on Oct 30th, 2007, 8:46am
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!



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