Author |
Topic: Math Contest (Read 864 times) |
|
FiBsTeR
Senior Riddler
Gender: 
Posts: 581
|
 |
Math Contest
« on: Mar 23rd, 2009, 4:03pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
Ronno
Junior Member
Gender:
Posts: 140
|
|
Re: Math Contest
« Reply #1 on: Mar 23rd, 2009, 8:04pm » |
Quote Modify
|
Do you mean "In every 10 question math contest with a certain number of students" ?
If so, the pigeonhole principle should work.
|
|
IP Logged |
Sarchasm: The gulf between the author of sarcastic wit and the person who doesn't get it..
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Math Contest
« Reply #2 on: Mar 24th, 2009, 7:39am » |
Quote Modify
|
57? (probably not the intended answer so I've not bothered hiding it)
|
|
IP Logged |
|
|
|
FiBsTeR
Senior Riddler
Gender:
Posts: 581
|
|
Re: Math Contest
« Reply #3 on: Mar 24th, 2009, 1:50pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Math Contest
« Reply #4 on: Mar 24th, 2009, 3:47pm » |
Quote Modify
|
In that case, I suspect the answer is 253 students, but I can so far only prove it as a lower bound, with an upper bound of 337 students.
There exists a set of answers for 252 students, 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 any set of three questions, it is straightforward to show that no contest with greater than 6*56 = 336 students can be non-strange.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Ronno
Junior Member
Gender:
Posts: 140
|
|
Re: Math Contest
« Reply #5 on: Mar 24th, 2009, 7:59pm » |
Quote Modify
|
How do you get the number 252?
(57-1)(10-1)/2?
|
|
IP Logged |
Sarchasm: The gulf between the author of sarcastic wit and the person who doesn't get it..
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Math Contest
« Reply #6 on: Mar 24th, 2009, 10:35pm » |
Quote Modify
|
on Mar 24th, 2009, 7:59pm, Ronno wrote:| How do you get the number 252? |
|
10C5 = 10!/(5!5!).
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Math Contest
« Reply #7 on: Mar 24th, 2009, 10:37pm » |
Quote Modify
|
on Mar 24th, 2009, 3:47pm, SMQ wrote:However, by considering any set of three questions, it is straightforward to show that no contest with greater than 6*56 = 336 students can be non-strange.
--SMQ |
|
Are you doing 3C2 buckets + pigeonhole here? 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?
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Ronno
Junior Member
Gender:
Posts: 140
|
|
Re: Math Contest
« Reply #8 on: Mar 25th, 2009, 3:07am » |
Quote Modify
|
The 57 doesn't matter in the 252? What would the configuration be?
And TenaliRaman, For each 3C2 bucket, there are some two questions that are both correct or both incorrect.
|
|
IP Logged |
Sarchasm: The gulf between the author of sarcastic wit and the person who doesn't get it..
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Math Contest
« Reply #9 on: Mar 25th, 2009, 7:06am » |
Quote Modify
|
on Mar 25th, 2009, 3:07am, Ronno wrote:| The 57 doesn't matter in the 252? |
|
By a happy "coincidence", no, it doesn't, as 8C3 = 56.
Quote:| What would the configuration be? |
|
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.
As to the upper bound, I reasoned as follows: 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.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Math Contest
« Reply #10 on: Mar 26th, 2009, 9:37am » |
Quote Modify
|
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. Any change to that student's answers which increases that student's order also increases the number of holes that student fills.
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 = 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.
Conclusion: 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. Since such a configuration can be shown to exist (see previous post), the question is answered.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
FiBsTeR
Senior Riddler
Gender:
Posts: 581
|
|
Re: Math Contest
« Reply #11 on: Mar 26th, 2009, 2:10pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Math Contest
« Reply #12 on: Mar 31st, 2009, 8:26am » |
Quote Modify
|
So, do we move this to medium? 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Math Contest
« Reply #13 on: Mar 31st, 2009, 8:29am » |
Quote Modify
|
on Mar 31st, 2009, 8:26am, Aryabhatta wrote:| So, do we move this to medium? |
|
Sure, why not. You carry the right side, I'll carry the left.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Math Contest
« Reply #14 on: Mar 31st, 2009, 8:34am » |
Quote Modify
|
on Mar 31st, 2009, 8:29am, towr wrote:
Sure, why not. You carry the right side, I'll carry the left.
|
|
Phew. That was hard work 
|
|
IP Logged |
|
|
|
FiBsTeR
Senior Riddler
Gender:
Posts: 581
|
|
Re: Math Contest
« Reply #15 on: Mar 31st, 2009, 5:07pm » |
Quote Modify
|
You guys are great! 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print