GATE CSE 2014 Set 1 | Question: 49

Question

A pennant is a sequence of numbers, each number being $1$ or $2$. An $n-$pennant is a sequence of numbers with sum equal to $n$. For example, $(1,1,2)$ is a $4-$pennant. The set of all possible $1-$pennants is ${(1)}$, the set of all possible $2-$pennants is ${(2), (1,1)}$ and the set of all $3-$pennants is ${(2,1), (1,1,1), (1,2)}$. Note that the pennant $(1,2)$ is not the same as the pennant $(2,1)$. The number of $10-$pennants is________

Comments

..

---

$\color{red}{\text{Detailed Video Solution of this GATE question}}$(Click Below):

https://youtu.be/K8fQPHG3JII (Multiple Ways to Solve)

$\color{red}{\text{Complete Recurrence Relation Playlist}}$(Click Below):

Complete Recurrence Relations Playlist 

Answer 1

Let us denote number of $n-$pennants by $f(n)$, so $f(10)$ is number of ${10}$-pennants.

A ${10}-$pennant means sum of numbers in sequence is ${10}$. If we look at any $9-$pennant, we can make it a ${10}-$pennant by adding $1$ into that sequence. Similarly, we can make any $8-$pennant a ${10}-$pennant by adding $2$ into that sequence.

So all ${10}-$pennants can be formed by $8-$pennants and $9-$pennants, and no other pennant (since we can add only $1$ or $2$ into a sequence)

So $f(10) = f(9) + f(8)$

This is in fact a Fibonacci sequence, in which $f(1) = 1, f(2) = 2$, so this sequence becomes

$1, 2, 3, 5, 8, 13, 21, 34, 55, 89\ldots$

So $f(10) = 89.$

Comments

Any reason why this turn to fibonacci sequence or its just coincidence/observation ...finding all possible permutation and then arrange it also gave same result but it will be very difficult if they ask F(50) so anyone can provide why this behavior of fibonnacci no occur it will be a great help ...

---

Best solution.Thanks :)

---

yes its sum of 2 previous but its base condition is not same fib series ,in fib series f(0)=0 f(1)=1 , f(2)= 1,but here f(1) = 1 , f(2)= 2 .. so it gives result of fib by shifting 1 term rt ?

---

best explanation @happy mittal

---

I still don't understand how f(10) = f(9) + f(8). What am I missing here?

---

yes me too @commenter commenter

Did you understand this?

---

yes me too @commenter commenter

Did you understand this?

can you please explain this to me

---

another method

(1,1,1,1,1,1,1,1,1,1) ===>10C0

(1,1,1,1,1,1,1,1,2)===>9C1

(1,1,1,1,1,1,2,2)===>8C2

(1,1,1,1,,2,2,2)===>7C3

(1,1,2,2,2,2)===>6C4

(2,2,2,2,2)===>5C5

10C0 + 9C1 + 8C2 + 7C3 + 6C4 + 5C5=89

---

Any approach to solving this question using generating functions?

---

Yes, if you can observe that it is fibonaci series then you can use it generating func and solve.

---

Not best answer

Answer 2

Numbers could be any one of

$\{(1,1,1,1,1,1,1,1,1,1),(1,1,1,1,1,1,1,1,2),(1,1,1,1,1,1,2,2),$
$(1,1,1,1,2,2,2),(1,1,2,2,2,2),(2,2,2,2,2)\}$

So, the number of ${10}$ pennants $=1+ \frac{9!}{8!} + \frac{8!}{6!2!} +\frac{7!}{4!3!} + \frac{6!}{2!4!} +1 =89.$

Comments

No, thinking like this might be easy.

Say , u have bought $10$ same type mobile phone from a company.

Now, u like a  iPhone , which cost $2$ mobile of previously purchased.

So, u gave previously purchased $2$ phone, to get one new iPhone.

Now, compare mobile phone as  '1'

and iPhone as '2'

So, when removing 2 phones and adding 1 phone, total phone will be $\left ( 10-2+1 \right )=9$ phones total

Now arrange among them in $\frac{9!}{8!\times 1!}$ ways.$=\binom{9}{1}$ ways

 

---

This should be choosen as the best answer thanx @sreshta

---

This is the way better and exam oriented solution . This should be the best answer.

Answer 3

For calculating no of 4 - pennants , we have to take cases :

Case 1 : We have 2 2's :

So in this case no of ways the 2 2's can be permuted = 2! / 2! = 1

Case 2 : We have 4 1's :

So in this case no of ways the 4 1's can be permuted = 4! / 4! = 1

Case 2 : We have 2 1's  and 1  2:

So here we have 3 objects with 1 repetition i.e. corresponding to no of 1's which is 2 in this case.

No of ways if have 2 1's and 1 2 to make sum = 4   :   3! / (2)!   = 3

With this all possibilities are exhausted to get the sum of 4 using 1 and 2 only.

Hence total no of 4 pennants = 1 + 1 + 3  = 5

Proceeding in the similar manner , we get no of 5 pennants = 8 

                                                            no of 6 pennants = 13

hence following the fibonacci series.

Hence no of  7 pennants  =   21

          no of  8 pennants  =   34

          no of  9 pennants  =   55

Finally no of 10 pennants  = 89

Hence no of 10 pennants = 89.

In such questions , which seem to be of non trivial nature we should try to form the solution of a smaller problem and construct the solution of larger problem using the smaller problem .

Answer 4

If the pennant has all 1s, then the no. of such pennants = 1

If the pennant has a single 2 and remaining 1s, then it would be of the form x2y, and no. of such pennants will be no. of solutions of the equation x+y = 8 which is $\binom{8+2-1}{8} = \binom{9}{8} = 9$  

If the pennant has two 2 and remaining 1s, then it would be of the form x2y2z, and no. of such pennants will be no. of solutions of the equation x+y+z = 6 which is $\binom{6+3-1}{6} = \binom{8}{6} = 28$

If the pennant has three 2 and remaining 1s, then it would be of the form w2x2y2z, and no. of such pennants will be no. of solutions of the equation w+x+y+z = 4 which is $\binom{4+4-1}{4} = \binom{7}{4} = 35$

If the pennant has four 2 and a single 1, then it would be of the form v2w2x2y2z, and no. of such pennants will be no. of solutions of the equation v+w+x+y+z = 2 which is $\binom{2+5-1}{2} = \binom{6}{2} = 15$

If the pennant has all 2s, then no. of such pennants = 1.

 

Total = 1+9+28+35+15+1 = 89

Comments

appriciatable work brother :)