# PIGEON HOLE PRINCIPLE

1 vote
502 views

https://gateoverflow.in/13170/application-of-pigeonhole-principle

WHY 14 IS ADDED ..hOW TWO SEQUENCES ARE RELATED FOR THIS ANSWER??

0
14 is added due to in the question, it is mention that 14 games.

But i also didn't get the solution
0
ok ..but if u find solution than please notify me also

This question is from Rosen and the solution it has is almost same as the one posted in that link. But it wasn't clear to me so I tried to add my interpretation. It might help:

At first two things need to be clarified:

1)

During a month with 30 days, a baseball team plays at least one game a day, but no more than 45 games.

This means no more than 45 games can be played in a month (and not on just 1 day)

2)

Show that there must be a period of some number of consecutive days during which the team must play exactly 14 games .

Over the period of some consecutive days, 14 games will be played.

Let aj be the no. of matches played till jth day which means games played before and on jth day. Lets not confuse it with match played on jth day.

Since its given that at least one match has to be played on 1 day so minimum value of a1 is 1 i.e. only one match is played on day 1.

Similarly, minimum value of a2 is 2 because atleast 1 match has to be played on day 2.

So now we can understand that if I write the series a1,a2,a3....a30 , it will be a strictly increasing one (as ai+1>ai)

Since at most 45 matches can be played in total so for any i (1<=i<=30), ai can be at max 45 (if at all any ai =45 then that i has to be equal 30 because if 45 matches are played till 29th day then min. 46 matches have to played till 30th as min. one match per day which violates the condition given).

So we know that for any i, 1<=ai<=45 (i=1,2,...30)  --> (1)

Now lets add 14 to this inequality expression (The reason will be known a bit later).

1+14<=ai+14<=45+14

=> 15<=ai+14<=59  --> (2)

Take this series :

a1,a2,....,a30, a1+14,a2+14...,a30+14

Here there are 60 terms and none of them can be more than 59 (From inequality (2)).

So we can now relate it to Pigeon Hole problem like there are 60 pigeons (60 terms here) and 59 pigeon holes.

Then atleast two terms have to be same i.e. have to have equal value.

We have already seen that a1,a2,....,a30 this series in strictly increasing so no term can be equal to any other. I call this series S1.

Similarly for the series a1+14,a2+14...,a30+14 this series is also strictly increasing as 14 has been added to all. Lets call this series as S2.

As there are atleast 2 equal terms then both these terms can 't be from S1 or S2. One has to be from Sand the other one from S2.

Let ai be a term in S1 and Let aj be a term in Swhich are equal. ai=aj

Now aj =ak+14 for some k∈[1,30] i.e. belongs to S1.

So, ai=a=> ai=ak+14

This means that after kth day and till ith day there have been 14 matches! In other words, from (k+1)th day till ith day 14 matches have been played. So we proved that there is a period of some number of consecutive days during which the team must play exactly 14 games.

edited
0
here max game can play by a team in 1 day is 45

then why we need to add 15 with it?

but conclusion obviously true

As, we have to play 1 game atleast in a day
1

max game can play by a team in 1 day is 45

@srestha

no more than 45 games can be played in a month (and not on just 1 day)

0
ok, but why adding 14 with 45?

45 is max no of games , na?
0

we have the in-equality as

1 ≤ ai ≤ 45

add 14, all sides ===> (1+14) ≤ ( ai +14) ≤ (45+14) ===> 15 ≤ ( ai +14 ) ≤ 60

0

This means no more than 45 games can be played in a month  (and not on just 1 day)

Since at most 45 matches can be played then for any day i  , ai can be maximum 45

## THESE TWO LINES ARE CONFUSING ME ...HOW IT CAN BE POSSIBLE.?

0

@eyeamgj

Since at most 45 matches can be played then for any day i  , ai can be maximum 45

you are right.the sentence isn't well formed..I am changing it.. Thanks :)

I meant that "Since at most 45 matches can be played in total so for any i (1<=i<=30), ai can be at max 45".

0
@MiniPanda

Here $45$ is max number of game played.

Then by 59 means what?? Is it mean 59 game playedatmost??

If yes, how $59$ can be played when max is 45??
0

@srestha

14 is being added as the part of proving the result..It doesn't mean 59 games are played at most. Since we have to prove that there is a sequence of some consecutive days where 14 games are played that is why adding 14 came as a step towards deriving the result..

1<=ai<=45 This is the one we got after following the conditions of the question.

Now we can add anything to this inequality (like if x<y then x+6<y+6)

Similarly here we added 14 whose reason we come to know at the end.

0
@MiniPanda

I know inequality.

But, what is meaning of adding something which has no meaning :P
0
@srestha
The addition of 14 helped us to finally get the result.. It does have significance here..please check the remaining part

## Related questions

1
482 views
A teacher gives a multiple choice quiz that has 5 questions, each with 4 possible answers: a, b, c,d What is the minimum number of students that must be in the class in order to guarantee that at least 4 answer sheets will be identical? how to do this problem
Prove that out of hundred whole numbers one will always have $15$ of them such that the difference between any two of these $15$ numbers is divisible by $7$.
Show that in a group of $n$ people there are two who have identical number of friends in that group.