# #Permuatation

1 vote
1.2k views
How many different sums can be formed with the following coins: 5 rupee, 1 rupee, 50 paisa, 25 paisa, 10 paisa, 3 paisa, 2 paisa and 1 paisa?

is it $2^{8}-2$ ?
0
Yes, answer should be $224$
1
Answer should be 224.
0
Yes, answer should be $224$,i've forgot to write the next part & add it

Answer should be $2^8 - 32 = 224$

Of Course we have to subtract some repeated/duplicated combinations from $2^8$(Which is the maximum possible combinations)

Now we will get duplicates by Only $1,2,3 \,\,Paisa\,\,Coins$

i.e. We need to find the Combinations where $3$ can be replaced with $1,2$

APPROACH 1 :

The Idea is that We can always replace $1\,\,and\,\,2\,\,paisa \,\,Coins$ with the $3\,\,Paisa\,\,Coin$ and get the same Sum. So, When We replace $1\,\,and\,\,2\,\,paisa \,\,Coins$ with the $3\,\,Paisa\,\,Coin$, We are getting same sum But with One less Coin. hence we fall from $n \,\,coins$ in hand to $n-1$ coins in hand but with the same Sum.  Bases on this Idea, The following answer is Proposed :

Let's find out such combinations :

A. Selecting Zero Coin    //No problem so far

B. Selecting One Coin .  //No problem here also

C. Selecting Two Coins : Coming to Selecting Two coins, We can see that when we select $2,1$ we get Sum as $3$ which is already there in $A$ Row.

D. Selecting Three Coins : When Two of these Three coins are $1,2\,\,Paisa\,Coins$ we can replace them with $3\,Paisa\,\,Coin$ and the resulting sum is already there in Row $C$ .... So, When Two of the Selected Three coins are $1,2$ we have $5$ possibilities to choose the third coin (We can not select $3 Paisa$ as the Third Coin)

E. Selecting Four Coins : When Two of these Four coins are $1,2 \,Paisa\,\,Coins$ we can replace them with $3\,Paisa \,\,Coin$ and the resulting sum is already there in Row $D$ .... So, When Two of the Selected Four coins are $1,2\,Paisa\,Coins$ we have $\binom{5}{2}$ possibilities to choose the Other Two coin (We can not select $3 Paisa$ as any of the rest Two Coin)

F. Selecting Five Coins : When Two of these Five coins are $1,2 \,Paisa\,\,Coins$ we can replace them with $3\,Paisa \,\,Coin$ and the resulting sum is already there in Row $E$ .... So, When Two of the Selected Five coins are $1,2\,Paisa\,Coins$ we have $\binom{5}{3}$ possibilities to choose the Other Three coins (We can not select $3 Paisa$ as any of the rest Three Coins)

G. Selecting Six Coins : When Two of these Six coins are $1,2 \,Paisa\,\,Coins$ we can replace them with $3\,Paisa \,\,Coin$ and the resulting sum is already there in Row $F$ .... So, When Two of the Selected Six coins are $1,2\,Paisa\,Coins$ we have $\binom{5}{4}$ possibilities to choose the Other Four coins (We can not select $3 Paisa$ as any of the rest Four Coins)

H. Selecting Seven Coins : When Two of these Seven coins are $1,2 \,Paisa\,\,Coins$ we can replace them with $3\,Paisa \,\,Coin$ and the resulting sum is already there in Row $G$ .... So, When Two of the Selected Seven coins are $1,2\,Paisa\,Coins$ we have $\binom{5}{5}$ possibilities to choose the Other Five coins (We can not select $3 Paisa$ as any of the rest Five Coins)

So, Number of Duplicate Cases are (From the above $A \,\,to\,\,H$ Points) = $1+5+10+10+5+1 = 32$

Hence We have Our answer = $256-32 = 224$

APPROACH 2 :

As @Soumya Suggested,

Repeated sums can be obtained only when either 3 paisa coin or (2+1)paisa coins is there in the selected coins.
$2^8$ sums can be possible and among them 2^5 (Cases where 3 paisa coin is not selected and (2+1) paisa both coins are selected) are repeated.

$2^8 - 2^5 = 224$

Thanks to @Soumya for Suggesting Such a Straight and Short way.

1
hey .. u seems correct .. but you wrote tough language :P , for under standing purpose

what i got .. its like if sum is 13 paisa .. it could be using 2 coin like 10+3 or i could be using 3 coins 10+2+1 rt.. like wise
0
one more thing selection of 0 coin should not be case so its 255-32 rt
2
Sir, I am also getting 224.
Repeated sums can be obtained only when either 3 paisa coin or (2+1)paisa coins is there in the selected coins.
$2^8$ sums can be possible and among them $2^5$ (Cases where 3 paisa coin is not selected and (2+1) paisa both coins are selected) are repeated.

$2^8-2^5=224$

PS- Sorry for showing laziness in typing . :(
2

but you wrote tough language :P

I will give a Summary of the answer i.e. What is the idea behind the answer. Which will help Students understanding and solving  this question further themselves. Thanks for pointing this point. Since Spoon-feeding is not a good thing for learning, An Idea or Hint will give more intuition to the students who are  really willing to work it out.

selection of 0 coin should not be case

From the Question it doesn't seem like it. When I have these coins on the Table and I don't pick any of them then I have a Sum of $O$ Money in my pocket. Which is Valid right. People do have a Sum of $0$ money in their pocket sometimes.

1

Sorry for showing laziness in typing

From your answer It seems like you're lazier than me. :P But It's a good thing. A Hint is enough. If you don't mind I'd like to add your approach to my answer to give students multiple ways to think.

0
haha.. :P

Yes, sure. You can add it :)
1 vote

We have total of $8$ coins.

Now, to form different sums--

We can select either $1$ coin OR $2$ coins OR $3$ coins OR $4$ coins OR $5$ coins OR $6$ coins OR $7$ coins OR $8$ coins.

Number of ways of selecting $1$ coin from $8$ coins = $^8C_1$

Number of ways of selecting $2$ coins from $8$ coins = $^8C_2$

Number of ways of selecting $3$ coins from $8$ coins = $^8C_3$

Number of ways of selecting $4$ coins from $8$ coins = $^8C_4$

Number of ways of selecting $5$ coins from $8$ coins = $^8C_5$

Number of ways of selecting $6$ coins from $8$ coins = $^8C_6$

Number of ways of selecting $7$ coins from $8$ coins = $^8C_7$

Number of ways of selecting $8$ coins from $8$ coins = $^8C_8$

∴ Total no. of ways of selecting coins = $^8C_1$ +$^8C_2$ + $^8C_3$ + $^8C_4$ + $^8C_5$ + $^8C_6$ + $^8C_7$ + $^8C_8$

= $8+ 28+56+70+56+28+8+1$

= $255$

But, when we select $2$ coins out of $8$ coins $\rightarrow$ there we get a pair of coins $(2 \text{ paisa},1 \text{ paisa})$

& the sum of that pair of paise will be $3$

We already have $3$ paisa as a individual coin. So, we need to delete the pairs we have to find the different sums possible out of the given coins.

Now, we have to find out how many pairs are there, which we counted multiple times.

• When we select $2$ coins out of $8$ we've counted $(10+3) = 13 \text{ paisa},(25+3) = 28 \text{ paisa}, (50+3)=53 \text{ paisa},$ $\text{(1 Rs+3 paisa) = 1 Rs. 3 paisa., (5 Rs. + 3 Paisa) = 5 rs. 3 Paisa.}$
• When we select $3$ coins out of $8$ coins then also we've counted $\text{(10 + 2 + 1) = 13 paisa, (25 + 2 + 1) = 28 paisa, (50 + 2 + 1) = 53 paisa, }$ $\text{(1 Rs. + 2 p + 1 p) = 1 Rs. 3 Paisa, (5 Rs + 2 p + 1 p) = 5 Rs. 3 Paisa.}$
• Similarly, when we select $4$ coins out of $8$ coins,$5$ coins out of $8$ coins we've counted this sums mulple times. So, we need to remove those sums.

∴ Multiple times counted sums = $^5C_1+^5C_2+^5C_3+^5C_4+^5C_5 = 5+10+10+5+1 = 31$

∴ $\color{Green}{\text{No. of different sums can be formed with the following coins: 5 rupee, 1 rupee,}}$ $\color{Green}{\text{ 50 paisa, 25 paisa, 10 paisa, 3 paisa, 2 paisa and 1 paisa will be}}$ $\color{Gold}{255-31 = 224}$

edited
1
If You don't consider $0$ as a valid sum then your answer should be 223. You must (Whether you consider $0$ as a valid sum or not) subtract 32 combinations.