But i also didn't get the solution

Dark Mode

eyeamgj
asked
in Combinatory
Nov 5, 2018

1,154 views
2 votes

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

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

9 votes

Best answer

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 a_{j} be the no. of matches played till j^{th} day which means games played **before and on** j^{th} day. Lets not confuse it with match played on j^{th} day.

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

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

So now we can understand that if I write the series a_{1},a_{2},a_{3}....a_{30} , it will be a strictly increasing one (as a_{i+1}>a_{i})

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

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

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

1+14<=a_{i}+14<=45+14

=> 15<=a_{i}+14<=59 --> (2)

Take this series :

a_{1},a_{2},....,a_{30}, a_{1}+14,a_{2}+14...,a_{30}+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 a_{1},a_{2},....,a_{30} this series in strictly increasing so no term can be equal to any other. I call this series S_{1}.

Similarly for the series a_{1}+14,a_{2}+14...,a_{30}+14 this series is also strictly increasing as 14 has been added to all. Lets call this series as S_{2}.

As there are atleast 2 equal terms then both these terms can 't be from S_{1} or S_{2}. One has to be from S_{1 }and the other one from S_{2}.

Let a_{i} be a term in S_{1 }and_{ }Let a_{j} be a term in S_{2 }which are equal. a_{i}=a_{j}

Now a_{j} =a_{k}+14 for some kâ[1,30] i.e. belongs to S_{1}.

So, a_{i}=a_{j }=> **a _{i}=a_{k}+14**

This means that after k^{th} day** and** till i^{th }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.

@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<=a_{i}<=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