wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Math Contest
        
(Message started by: FiBsTeR on Mar 23rd, 2009, 4:03pm)
Title: Math Contest
Post by FiBsTeR on Mar 23rd, 2009, 4:03pm
I needed a hint to solve this on my own but I'm putting this in easy because you guys are much smarter than I am! I hope you'll excuse the nested quantifiers: feel free to post clearer phrasings.

-----

In a ten-question math contest, there exists a pair of questions such that there exist 57 students such that all of them answered the two questions correctly or none of them answered the two questions correctly. Find the smallest possible number of students at the contest.
Title: Re: Math Contest
Post by Ronno on Mar 23rd, 2009, 8:04pm
Do you mean "In every 10 question math contest with a certain number of students" ?

If so, the pigeonhole principle should work.
Title: Re: Math Contest
Post by rmsgrey on Mar 24th, 2009, 7:39am
57? (probably not the intended answer so I've not bothered hiding it)
Title: Re: Math Contest
Post by FiBsTeR on Mar 24th, 2009, 1:50pm
Oh shoot, thanks to both of you. The original post is incorrectly phrased, I apologize. It should be like this (similar to what Ronno asked):

-----

A ten-question math contest is called strange if there exists a pair of questions such that there exist 57 students such that all of them answered the two questions correctly or none of them answered the two questions correctly. Find the smallest possible number of students at the contest such that the contest is necessarily strange.
Title: Re: Math Contest
Post by SMQ on Mar 24th, 2009, 3:47pm
In that case, I suspect the answer is [hide]253 students[/hide], but I can so far only prove it as a lower bound, with an upper bound of [hide]337 students[/hide].

There exists a set of answers for [hide]252 students[/hide], unique up to rearrangement, such that the contest is not strange.  Changing any single answer from this configuration results in a strange contest.  It seems likely that no non-strange contests exist with more students, but I have not so far been able to show it.  However, by considering [hide]any set of three questions[/hide], it is straightforward to show that no contest with greater than [hide]6*56 = 336 students[/hide] can be non-strange.

--SMQ
Title: Re: Math Contest
Post by Ronno on Mar 24th, 2009, 7:59pm
How do you get the number [hide]252[/hide]?

[hide](57-1)(10-1)/2[/hide]?
Title: Re: Math Contest
Post by SMQ on Mar 24th, 2009, 10:35pm

on 03/24/09 at 19:59:47, Ronno wrote:
How do you get the number [hide]252[/hide]?

[hide]10C5 = 10!/(5!5!)[/hide].

--SMQ
Title: Re: Math Contest
Post by TenaliRaman on Mar 24th, 2009, 10:37pm

on 03/24/09 at 15:47:56, SMQ wrote:
However, by considering [hide]any set of three questions[/hide], it is straightforward to show that no contest with greater than [hide]6*56 = 336 students[/hide] can be non-strange.

--SMQ

Are you doing [hide]3C2 buckets + pigeonhole[/hide] here? [hide]If yes then are you saying that each bucket corresponds to both questions being answered correct or both questions being answered incorrect? If it is any of the above, then aren't you missing the case when one is answered correct and other incorrect?[/hide]

-- AI
Title: Re: Math Contest
Post by Ronno on Mar 25th, 2009, 3:07am
The 57 doesn't matter in the [hide]252[/hide]? What would the configuration be?

And TenaliRaman, For each [hide]3C2 bucket[/hide], there are some two questions that are both correct or both incorrect.
Title: Re: Math Contest
Post by SMQ on Mar 25th, 2009, 7:06am

on 03/25/09 at 03:07:36, Ronno wrote:
The 57 doesn't matter in the [hide]252[/hide]?

By a happy "coincidence", no, it doesn't, as [hide]8C3 = 56[/hide].


Quote:
What would the configuration be?

[hide]Each of the students has a different one of the 252 possible ways to answer five questions correctly and five questions incorrectly.  This leads to each pair of questions having 8C3 = 56 students who answered both questions correctly, 8C3 = 56 students who answered both questions incorrectly, 8C4 = 70 students who answered only the first question correctly, and 8C4 = 70 students who answered only the second question correctly.[/hide]

As to the upper bound, I reasoned as follows: [hide]Consider a contest with only three questions.  Each of the three possible pairings of questions can have at most 56 students who answered both questions correctly and 56 students who answered both questions incorrectly.  Furthermore, each student must have answered at least one pair of questions either both correctly or both incorrectly.  Thus a non-strange contest with three (or more) questions can have at most 6*56 = 336 students.[/hide]

--SMQ
Title: Re: Math Contest
Post by SMQ on Mar 26th, 2009, 9:37am
Proof by pigeon hole:

Consider the groups of students who answered any given pair of questions correctly, together with the groups of students who answered any given pair of questions incorrectly.  Each group can have up to 56 students before the contest becomes strange. Since there are 10C2 = 45 possible pairs of questions, each with two groups, there are 2*45*56 = 5040 "holes" available to be filled by students.

Lemma: Let a given student's "order" be the larger of the number of questions that student answered correctly or the number of questions that student answered incorrectly.  [hide]Any change to that student's answers which increases that student's order also increases the number of holes that student fills.[/hide]

Proof: The number of holes a given student fills is the number of pairs of questions that student answered either both correctly or both incorrectly [hide]= cC2 + n-cC2 = nC2 - c(n-c) where n is the number of questions and c is the number answered correctly.  The lemma follows from the observation that nC2 is constant and c(n-c) is parabolic centered at n/2.[/hide]

Conclusion: [hide]The minimal number of holes a student can fill is 20, therefore the maximum number of students in a non-strange contest is 5040/20 = 252.[/hide]  Since such a configuration can be shown to exist (see previous post), the question is answered.

--SMQ
Title: Re: Math Contest
Post by FiBsTeR on Mar 26th, 2009, 2:10pm
Nice! As for the source of the problem, this was the last (and by tradition hardest) combinatorics problem given at the Harvard-MIT Mathematics Tournament in 2006. See here (http://web.mit.edu/hmmt/www/).
Title: Re: Math Contest
Post by Aryabhatta on Mar 31st, 2009, 8:26am
So, do we move this to medium?  :P
Title: Re: Math Contest
Post by towr on Mar 31st, 2009, 8:29am

on 03/31/09 at 08:26:49, Aryabhatta wrote:
So, do we move this to medium?  :P
Sure, why not. You carry the right side, I'll carry the left.
Title: Re: Math Contest
Post by Aryabhatta on Mar 31st, 2009, 8:34am

on 03/31/09 at 08:29:48, towr wrote:
Sure, why not. You carry the right side, I'll carry the left.


Phew. That was hard work :)
Title: Re: Math Contest
Post by FiBsTeR on Mar 31st, 2009, 5:07pm
You guys are great!  ;D


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