wu :: forums « wu :: forums - Boys and Girls Math Contest » Welcome, Guest. Please Login or Register. Sep 25th, 2016, 12:05pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Grimbal, ThudnBlunder, william wu, towr, SMQ, Eigenray, Icarus)    Boys and Girls Math Contest « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Boys and Girls Math Contest  (Read 5464 times)
william wu

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: 13385
 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: 578
 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: 911
 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: 13385
 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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »