edited by
11,247 views
63 votes
63 votes
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________
edited by

14 Answers

Best answer
129 votes
129 votes
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.$
edited by
159 votes
159 votes
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.$
edited by
13 votes
13 votes

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 .

edited by
13 votes
13 votes
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
Answer:

Related questions

31 votes
31 votes
6 answers
1
gatecse asked Sep 15, 2014
8,641 views
When a point inside of a tetrahedron (a solid with four triangular surfaces) is connected by straight lines to its corners, how many (new) internal planes are created wit...
60 votes
60 votes
6 answers
2
go_editor asked Sep 28, 2014
12,380 views
Let ܵ$S$ denote the set of all functions $f:\{0,1\}^4 \to \{0,1\}$. Denote by $N$ the number of functions from S to the set $\{0,1\}$. The value of $ \log_2 \log_2N $ is...
100 votes
100 votes
10 answers
4