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

holly– Mon, 25 Jun 2012 09:40:10 -0000i dont think it will be maximum because maximum can go any number beyond 415 and between the total number of balls available

Shuvajit– Wed, 16 Jan 2013 21:33:26 -0000the question said "guarantee"!!!