In this lesson, we will be taking something
called "Combinatorics". It is generally the nemesis of many
students, especially the ones who do not understand why do we
need to arrange something, and that too in some weird way. Well I
have sympathy for you, but no matter how chaotic our lives be, we
still like to maintain some order, and therein comes the concept
of ordering, arranging, partitioning and so on. And all of it
come together to make a branch of mathematics called
Combinatorics.
It will be injustice to combinatorics, if I
write just once lesson, so I will try to write a few more, for
the moment, I will pick up one of the darling principles of
Combinatorics, known as Pigeon-Hole Principle.
Theorem 1: if n+1 pigeons fly
to n holes, there must be a pigeonhole containing at least two
pigeons
Well this theorem, look apparently simple and
trivial, but its extremely powerful. Lets take a test of
it.
Example 1: Let A be any set of nineteen
integers chosen from the arithmetic progression 1,4, . . . ,100.
Prove that there must be two distinct integers in A whose sum is
104.
Now how do we go about this? remember n and n+1.
The hint is to make n+1=19. Something clicked?
see we have 34 numbers of the form 3k+1, from 1
to 100. If we do not want a sum of 104, we will break them in the
sets of 2 integers whose sum is 104
{4,100},{7,97}..{49,55} and {1}, {52}. Clearly
we have 16 two element sets and 2 one element set.
So if we make a set of 19 integers, we will have
to pick both the integers from atleast one of the two element
sets, which will give us a sum of 104.
We are done here.
If you still have doubts, let me explain
again, suppose you are four friends ( boys) and there are three
girls. And each one of you like a girl out of the three. So at
least one of the girls will be liked by two
boys.
Lets solved a more involved example, wherein we
need not prove a thing, but find a thing. Some people may be
feeling cat does not want us to prove but find. Here is how we do
that.
Example 2: Let there be n balls with
Ram. he decides to colour one ball with colour 1, two balls with
colour 2 and so on upto, fifty balls with colour 50. At the end
of it , all n balls are used, and no ball is coloured twice. Ram
then draws balls from the lot at random, without replacement.
What is is the minimum number of balls that he must draw in order
to gurantee drawing 10 balls of the same
color?
What the hell is his problem. Why coloring and
then taking out. Stupid chap. Let us help him with the math
now.
see if he picks all the balls with colors which
are less than 10 it will come upto (1+2+3..+9)=45.
Now for the worst case he will pick 9 balls each
from rest of the balls, which is 41 * 9
so total is . (avoid multiplying, be
watchful)
now if he picks one more ball, atleast one of
the set will be of 10. so we are done
he needs to draw 414+1=415 balls.
I would like to thank Mr. David Santos, as I have used his book on number system to make this lesson, but I have tried to add my own flavor to it.
Post Comments
hassan_k said – Sat, 15 Nov 2008 13:24:04 -0000 ( Flag Edit Link )
This is just amazing. I should thank Sureshbala for his invaluable contribution.