Question

pigeonhole

2. Show that if 7 numbers was chosen from 1 to 12, any 2 of it will add to 13.

3. How many friend you should have to ensure that at least 5 of them have the same birth month?

4. 6 persons collect their money and the amount is RM 21.61. Show that at least one of them must have RM 3.61.

Answer 1

solution:

2)

  Let pigeons be the number selected from { 1,2,....,12 }

   Define Six pigeon holes corresponding six sets :

{1,12} , {2,11} ,{3,10} , {4,9} , { 5,8} , {6,7}

Notice that the sum of numbers in each set is equal to 13

By pigeonhole principle 1(simple version):Pigeonhole Principle Concept: If n items are put into m containers, with n > m, then at least one container must contain more than one item

If we have to choose 7 numbers the we must take atleast 2 numbers belonging to one set

Thus any 2 of seven numbers will definately add upto 13

3) Extended pigeon hole principle: Let 'n' be the no.of pigeons and 'm' be the no.of pigeonholes.If n pigeons are assigned to m pigeonholes  then atleast 1 contains  ⌊(n−1)/m⌋+1 pigeons.

Here, No.of pigeons = No.of friends = ?

No.of pigeonholes = No.of months in a year = 12

By  Extended pigeon hole principle

⌊(n−1)/m⌋+1 = 5

   ⌊(n−1)/12⌋ = 4

n-1 = 48

n = 49

49 friends should be their to ensure at least 5 of them have the same birth month

4) By Pigeonhole principle (PHP2): If n (or) more pigeons are distributed amone K>0 pigeonholes.Then atleast one pigeonhole contains atleast Pigeons

Here, No.of pigeons = Total amount (n)= 21.61

No.of pigeonholes = No.of persons(k) = 6

Here , = 4

consider n/k, which is less than or equal to

Here,n/k = 3.60

If each member contains 3.60

Then 6 members contains 21.60 which means one member contains 0.01 extra

   Atleast one of them must have RM 3.61