2,655 views
2 votes
2 votes

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

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

1 Answer

Best answer
10 votes
10 votes

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 by

Related questions

0 votes
0 votes
1 answer
1
Prince Sindhiya asked Dec 21, 2018
2,439 views
A teacher gives a multiple choice quiz that has 5 questions, each with4 possible answers: a, b, c,d What is the minimum number of students thatmust be in the class in ord...
0 votes
0 votes
0 answers
2
pC asked Jan 15, 2016
1,174 views
The least num of computers required to connect 8 computers to 4 printers to guarantee 4 comp can direct]ly access 4 printer is _____1617192021
2 votes
2 votes
1 answer
3
Sammohan Ganguly asked May 25, 2018
978 views
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$.
1 votes
1 votes
2 answers
4
Sammohan Ganguly asked May 25, 2018
2,798 views
Show that in a group of $n$ people there are two who have identical number of friends in that group.