Thoughts on Pigeonhole + Math awards + New contrib
by shiningsunnyday, May 24, 2016, 1:46 PM
Let's start with some good ol' Pigeonhole Principal problems from Interm CP and 102 shall we?
First, a direct application:
Sometimes, the boxes aren't so easily identifiable. It's up to you to play around a bit. A good way to do so is to partition your "boxes" into groups. Here's a simple application:
Sometimes, the boxes are really tricky to quantify:
Here's a problem with an almost-identical solution, except with an extra twist.
Once again, a counter-example must be given when dealing with maximums/minimums.
There're a few more nice problems which I planned on adding in this post but I didn't get to solve. Perhaps I'll stop being lazy and do them soon?
So yesterday I received my math certificates for this year. It's attached below. Overall, it sums up the misery of my contest season this year pretty well. Ah, how nice it would be had I gotten that JMO qualification... The Canadian ones are pretty self-explanatory. Nothing worth mentioning, honestly. *Cries*
Next year is the big year, I guess. I didn't expect things to turn out this way. I mean, if I had gotten that JMO qualification, my dad wouldn't be hollering me like I've been lollygagging my way through the whole semester, nothing to show besides a 3.5 GPA. *Continues to rant* I mean, so many 'if's. If... if... if... No one gets me at all. Everything just so terr--
*Suddenly, music starts playing in the background.*
Wait, what's that sound?
Hey AoPS, say somethin' to her, holler at her.
Wait, what's going on?
I got one question.
What?
How does she fit all that math, in her head?
She?
Someone new is contribin' to my big fat blog.
Who?
Wiggle wiggle wiggle.
Wiggle wiggle wiggle.
Wiggle wiggle wiggle.
*Music music music music music music music music*
*Body starts to shake uncontrollably*
Kong-tri-buter kong-tri-buter
Of this blog
Got me dazin' at your math skills all day long
If I ask you to be contrib of my blog
I can make you famous on ey-oh P.S.
She's it, baby
Never takes math for granted
Give her a problem and she's right on it
Woah
I can't stand it
Anyways... Y'all know who's contribin' to my nice cool (wait that sounds weird) blog.
Yadayadayada [clearly not out of ideas as to not make the ending of this blog post look awkward]
Let's give it up to our blog's newest contributor, WIII WII WI WI WIIII
GGGGGULLLLL GULLLL ULLL OHHH GIGGLE? WHAT? GGGGOLLLDDD GOOOO LOL
WAMMMMMMMMMMMMMMMMMMMMMMMMMM!!!!!!!!
holes, then we can guarantee at least one hole contains 
pigeons.
pigeons and 
holes. Note that 
which implies that if we try to stuff holes with 
pigeons each, we'll run out of holes first. If we try to stuff holes with 
we must have some holes with 
pigeons rounded up. In other words, guarantee 
pigeons in a single hole.
But wait! What if, say, 
Uh oh, clearly 
does not apply anymore. Fortunately, we can prevent these cases in which 
as desired.First, a direct application:
Interm CP wrote:
A pen-pal club has 12 members. In August, each member of the club sends a letter to 6 of the other members, chosen at random.
(a) Prove that some pair of members of the club will send each other letters.
(b) In September, each member of the club sends a letter to only 5 of the other members. Does the conclusion from part (a) still hold? Why or why not?
(a) Prove that some pair of members of the club will send each other letters.
(b) In September, each member of the club sends a letter to only 5 of the other members. Does the conclusion from part (a) still hold? Why or why not?
and 
letters sent, respectively. Consider the 
members as vertices of a graph. Note that there're 
edges. An edge corresponds to a letter. Clearly at least one edge will be used twice in the first case, corresponding to a pair of members sending each other letters, but this is not guaranteed in the second case since 
Sometimes, the boxes aren't so easily identifiable. It's up to you to play around a bit. A good way to do so is to partition your "boxes" into groups. Here's a simple application:
P6 of 102 wrote:
Twenty five boys and twenty five girls sit around a table. Prove that it is always possible to find a person both of whose neighbors are girls.
chairs into 
girls and 
girls. The only possible ways the 
each of which satisfy the problem condition, so we're done.
Sometimes, the boxes are really tricky to quantify:
Putnam wrote:
A certain college has 
students and offers 
courses. Each student can enroll in any or all of the courses, or none at all (which is a real waste of tuition). Prove or disprove: there must exist 
students and 
courses, such that either all students are in both courses, or all students are in neither course.
students and offers 
courses. Each student can enroll in any or all of the courses, or none at all (which is a real waste of tuition). Prove or disprove: there must exist 
students and 
courses, such that either all students are in both courses, or all students are in neither course.
boxes for pairs of classes both of which a student is enrolled in, and 
boxes for pairs of classes both of which a student isn't enrolled in. Now consider a random student that enrolls in 
classes. The student will fill up 
of the 
boxes. Now note that 
so we can guarantee that every student will fill up at least 
balls total in the 
balls because 
while 
Here's a problem with an almost-identical solution, except with an extra twist.
HMMT wrote:
Somewhere in the universe, 
students are taking a 
-question math competition. Their collective performance is called laughable if, for some pair of questions, there exist 
students such that either all of them answered both questions correctly or none of them answered both questions correctly. Compute the smallest such that the performance must be laughable, no matter how the students performed on the competition.
students are taking a 
-question math competition. Their collective performance is called laughable if, for some pair of questions, there exist 
students such that either all of them answered both questions correctly or none of them answered both questions correctly. Compute the smallest such that the performance must be laughable, no matter how the students performed on the competition.Once again, a counter-example must be given when dealing with maximums/minimums.
Interm CP wrote:
Sam’s band has 6 members, but only 4 of them play together in a concert. Additionally, no 3 members can play together in more than one performance. How many concerts can Sam’s band give, at most?
and 
WLOG let the first performance be of members 
To make sure no three members repeat, we must sub in 
and 
before the next concert. If we only sub in one, say 
the 
triplet will be repeated. So the next performance will be a two element subset of 
WLOG let the second performance be of 
Similarly, the next concert must be contain 
It can't have 
or 
in it cause that will conflict with performance 
so we see the third performance must be 
If we apply our logic once more, the next performance should feature 
But we can't feature any of 
because that would conflict with either performance 
or performance 
so the max we can do is 
Person 
triplets, but every time he goes to a concert (which has 
individual performances, we must have exactly four people participating in 
contradiction.
and 
Note that the only way for this to work is for each concert to feature a three element subset of 
Why? Because if not, then we must have at least one performance featuring all four of 
and we can easily see that a triplet will be repeated. We must have 
in concert 
in concert 
in concert There're a few more nice problems which I planned on adding in this post but I didn't get to solve. Perhaps I'll stop being lazy and do them soon?
So yesterday I received my math certificates for this year. It's attached below. Overall, it sums up the misery of my contest season this year pretty well. Ah, how nice it would be had I gotten that JMO qualification... The Canadian ones are pretty self-explanatory. Nothing worth mentioning, honestly. *Cries*
Next year is the big year, I guess. I didn't expect things to turn out this way. I mean, if I had gotten that JMO qualification, my dad wouldn't be hollering me like I've been lollygagging my way through the whole semester, nothing to show besides a 3.5 GPA. *Continues to rant* I mean, so many 'if's. If... if... if... No one gets me at all. Everything just so terr--
*Suddenly, music starts playing in the background.*
Wait, what's that sound?
Hey AoPS, say somethin' to her, holler at her.
Wait, what's going on?
I got one question.
What?
How does she fit all that math, in her head?
She?
Someone new is contribin' to my big fat blog.
Who?
Wiggle wiggle wiggle.
Wiggle wiggle wiggle.
Wiggle wiggle wiggle.
*Music music music music music music music music*
*Body starts to shake uncontrollably*
Kong-tri-buter kong-tri-buter
Of this blog
Got me dazin' at your math skills all day long
If I ask you to be contrib of my blog
I can make you famous on ey-oh P.S.
She's it, baby
Never takes math for granted
Give her a problem and she's right on it
Woah
I can't stand it
Anyways... Y'all know who's contribin' to my nice cool (wait that sounds weird) blog.
Yadayadayada [clearly not out of ideas as to not make the ending of this blog post look awkward]
Let's give it up to our blog's newest contributor, WIII WII WI WI WIIII
GGGGGULLLLL GULLLL ULLL OHHH GIGGLE? WHAT? GGGGOLLLDDD GOOOO LOL
WAMMMMMMMMMMMMMMMMMMMMMMMMMM!!!!!!!!
Attachments:
This post has been edited 1 time. Last edited by shiningsunnyday, May 24, 2016, 1:49 PM
Srsly where do you come up with all this??
because that looks way better. 
makes intuitive sense as well.
May 2018
April 2018