0

Sherlock Holmes and Dr Watson travel from X to Y via metro.

They have enough coins of 1,5,10,25 paisa. Sherlock Holmes agrees to pay for Dr Watson only if he tells all possible combinations of coins that can be used to pay for the ticket.

Q1 How many Combinations are possible,if Fare is 50 paisa.

Q2 How many combinations are possible if they get an international discount of 10% i.e fare of 45p.

My Approach:

These are all the different combinations of coins I found.

Case1:(1,10) paisa coins with 1 paisa 10 coins and 10 paisa 4 coins

Case2:(1,5) paisa coins with 1 paisa 5 coins and 5 paisa 9 coins

Case3:(1,25) paisa coins with 1 paisa 0 coins and 25 paisa 2 coins(may be)

Case4:(5,10) paisa coins with 5 paisa 2 coins and 10 paisa 4 coins

Case5:(5,25) paisa coins with 5 paisa 0 coins and 25 paisa 2 coins(may be)

Case6:(10,25) paisa coins with 10 paisa 0 coins and 25 paisa 2 coins

Case7:(1,5,10) paisa coins with 1 paisa 5 coins and 10 paisa 4 coins and 5 paisa 5 coins

Case8:(1,5,10,25) paisa coins with 1 paisa 5 coins and 10 paisa 3 coins and 5 paisa 3 coins

Q Is this a good approach to solve this problem? What are the other combinations if I could not found it.

Community
  • 1
justin takro
  • 1,288

2 Answers2

5

If we had only 1er coins, then there'd always be exactly one way to pay.

If we have only 1er and 5er coins, then to pay $5n$ paisa, we have $n+1$ ways: Use between $0$ and $n$ (inclusive) 5ers and fill with 1ers.

To pay $5n$ paisas with 1ers, 5ers and 10ers, there are (cf. above) $n+1$ ways without a 10er, $n-1$ ways (if that is still $\ge0$) with one 10er, $n-3$ ways (if $\ge0$) with two 10ers, and so on. So if $n=2k$ is even, this is $(2k+1)+(2k-1)+(2k-3)+\ldots +5+3+1=(k+1)^2$ and if $n=2k-1$ is odd, it is $2k+(2k-2)+(2k-4)+\ldots +6+4+2=k(k+1)$.

Finally, to pay $50=5\cdot 10$ paisas with 1ers, 5ers, 10ers, 25ers, we can use no 25er in $(5+1)^2$ ways, one 25er in $3\cdot 4$ ways, two 25ers in exactly $1$ way. In total: $49$ ways.

On the other hand, to pay $45=5\cdot 9$ paisas with 1ers, 5ers, 10ers, 25ers, we can use no 25er in $5\cdot 6$ ways, or one 25er in $(2+1)^2$ ways. In total: $39$ ways.

Hagen von Eitzen
  • 374,180
  • How n-1 with one 10er.Does that mean we did not need 1er? – justin takro Aug 26 '15 at 12:14
  • How we get n+1 ways(given in second line)Can you please elaborate? – justin takro Oct 10 '15 at 11:02
  • @justintakro There are $n+1$ numbers from $0$ to $n$ (inclusive). - And if we use one10er, we effectively replace $5n$ with $5(n-2)$ to be payed with 5ers and 1ers, so effectively adding a 10er decreases $n$ y two, which is why $n+1$ becomes $(n-2)+1=n-1$ and so on. – Hagen von Eitzen Oct 10 '15 at 14:26
2

If you want to list the combinations, I'd suggest being a bit more systematic. Use tables.

$$\boxed{\begin{array}{l|llll}50\text p & 25\text{p}&10\text{p}&5\text{p}&1\text{p} \\\hline & 2 \\ & 1 & 2 & 1 \\ & 1 & 2 & & 5 \\ & 1 & 1 & 3 \\ & 1 & 1 & 2 & 5 \\ & 1 & 1 & 1 & 10 \\ & 1 & 1 & & 15 \\ & 1 & & 5 \\ \vdots & & \ddots & & \vdots \\ & & & & 50 \end{array}}\;\boxed{ \begin{array}{l|llll}45\text p & 25\text{p}&10\text{p}&5\text{p}&1\text{p} \\\hline & 1 & 2 \\ & 1 & 1 & 2 \\ & 1 & 1 & 1 & 5 \\ & 1 & 1 & & 10 \\ & 1 & & 2 & \\ & 1 & & 1 & 5 \\ & 1 & & & 10 \\ & & 4 & 1 \\ \vdots & & \ddots & & \vdots \\ & & & & 45 \end{array}}$$

Graham Kemp
  • 129,094