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

5 votes
5 votes
Lets’ understand and solve it by forming a story of an old man who has to repay his loan of amount $n$ pesos. Old man is a daily wage worker who when works on double shift gets’ double the wage than usual. Out of that wage he can save $1$ peso or $2$ pesos depending on how many shifts he worked. So on daily basis he goes to bank to repay the leftover loan with saved amount of peso(s). Also, what amount he paid a day earlier is independent of what he will pay today.

At the end of repayment old man will get the bill summary stating the order in which the loan was paid off. We need to find that how many such orders can exist of bill summary.

Let $\displaystyle{T(n)}$ be the number of orders to pay loan of amount $n$ using $1$ and $2$ peso(s). If on first day he pays $1$ peso then loan amount left would be $n-1$ and we would need to find $T(n-1)$, but he can also pay $2$ pesos on first day and then we would need to find $T(n-2)$.

Now, Either $T(n-1)$ can happen or $T(n-2)$ on first day but not both. Hence we would need to sum the count from both the possibilities.

$T(n) = T(n-1)+T(n-2)$

where,

$T(1) = 1$

$T(2) = 2$

$T(3) = 3$

So, T(n) is sum of last two predecessors, just like it happens in Fibonacci series and we want $10^{th}$ term.

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

$T(10) = \bf{89}$
4 votes
4 votes
This is quite straight forward if we think of the set elements as combination of 1s and 2s where elements are repeated or are similar.

Number of ways of arranging n elements when some number us repeated q1 time,  another q2 time... and so on is n!/q1! *q2!

For this problem,  in any set element we need combination of 1s and 2s. If we find all possible combinations we have our answer...

First,  we can have two 1s and Four 2s. Number of different arrangements = 6!/(2!*4!)  = 15

Then Four 1s and Three 2s. Number of different arrangements = 7!/(4!*3!) = 35

Then,  Six 1s and Two 2s. Number of different arrangements = 8!/(6!*2!) = 28

Then we have,  Eight 1s and One 2. Number of different arrangements = 9!/8! = 9

Finally,  we have 1 possible combination of ten 1s and 1 possible combination of five 2s.

Total different combinations = number of ten pennants = 15 + 35 + 28 + 9 + 1 + 1 = 89.
3 votes
3 votes
1-pennant {(1)} - #1

2-pennant {(1,1),(2)} - #2

3-pennant {(1,1,1),(1,2),(2,1)} - #3

4-pennant {(1,1,1,1),(2,2),(1,1,2),(1,2,1),(2,1,1)} - #5

5-pennant {(1,1,1,1,1),(2,1,1,1),(1,2,1,1),(1,1,2,1),
            (1,1,1,2),(2,2,1),(2,1,2),(1,2,2)} - #8

If one observe carefully they are the terms(part of) a Fibonacci series. (0,1,1,2,3,5,8,13 ....). Hence the # of 10-pennant is the 12th term of the series ie. 89
1 votes
1 votes

No of ways 10- pennant can be formed is:

1. 5(2's), 0(1's)=1 way

2. 4(2's), 2(1's)=6C4=15

3. 3(2's), 4(1's)=7C3=35

4. 2(2's), 6(1's)=8C2=28

5. 1(2's), 8(1's)=9C1= 9

6. 0(2's), 10(1's)=1 way

Total = 1+15+35+28+9+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