Latest Elitmus Aptitude Question SOLUTION: Sherlock Homes and Dr. Watson have to travel from Rajeev Gandhi chowk to Indira Gandhi International Airport via the metro. They have enough coins of 1, 5, 10 and 25 paise. Sherloc

Let the number of 1, 5, 10 and 50 paise coins required are x, y, z and w respectively.
So when paid total amount is: x + 5y + 10z + 25w, which is equal to the fare paid.
So, x + 5y + 10z + 25w = 50
The number of non negative integral solution of this equation will be equal to the
number of ways the fare can be paid.
x + 5y + 10z + 25w = 50
In this equation w can be either 0, 1 or 2
Case 1: When w is 2
No other coins are required to pay
So there is only one way to pay: (0, 0, 0, 2)
Total no of ways : 1
Case 2: When w is 1
x + 5y + 10z = 25
In this case z can have only three values possible: 0, 1 or 2
Case I: When z is 0
x + 5y = 25
possible values are: (25, 0, 0, 1), (20, 1, 0, 1), (15, 2, 0, 1), (10, 3, 0, 1),
(5, 4, 0, 1), (0, 5, 0, 1)
Case II: When z is 1
x + 5y = 15
possible values are: (15, 0, 1, 1), (10, 1, 1, 1), (5, 2, 1, 1), (0, 3, 1, 1)
Case III: When z is 2
x + 5y = 5
possible values are: (5, 0, 2, 1), (0, 1, 2, 1)
Total no of ways : 12
Case 3: When w is 0
x + 5y + 10z = 50
In this case z can have only three values possible: 0, 1, 2, 3, 4 or 5
Case I: When z is 0
x + 5y = 50
possible values are: (50, 0, 0, 0), (45, 1, 0, 0), (40, 2, 0, 0), (35, 3, 0, 0),
(30, 4, 0, 0), (25, 5, 0, 0), (20, 6, 0, 0), (15, 7, 0, 0), (10, 8, 0, 0), (5, 9, 0, 0),
(0, 10, 0, 0)
Case II: When z is 1
x + 5y = 40
possible values are: (40, 0, 1, 0), (35, 1, 1, 0), (30, 2, 1, 0), (25, 3, 1, 0),
(20, 4, 1, 0), (15, 5, 1, 0), (10, 6, 1, 0), (5, 7, 1, 0), (0, 8, 1, 0)
Case III: When z is 2
x + 5y = 30
possible values are: (30, 0, 2, 0), (25, 1, 2, 0), (20, 2, 2, 0), (15, 3, 2, 0),
(10, 4, 2, 0), (5, 5, 2, 0), (0, 6, 2, 0)
Case IV: When z is 3
x + 5y = 20
possible values are: (20, 0, 3, 0), (15, 1, 3, 0), (10, 2, 3, 0), (5, 3, 3, 0), (0,
4, 3, 0)
Case V: When z is 4
x + 5y = 10
possible values are: (10, 0, 4, 0), (5, 1, 4, 0), (0, 2, 4, 0)
Case VI: When z is 5

1 2 3 4 5 6 7 8 9
x + 5y = 0
possible values are: (0, 0, 5, 0)
Total no of ways : 36
So total no of ways = 1 + 12 + 36 = 49

Arrange the combinations of the coins in the decreasing order of denominations :

Case 1: when there is 2 25pc coin - 1 ways

Case 2: when there is 1 25pc coin and
(1) 2 10pc coin - nos of 5pc coin will range from 1 to 0 i.e 2 combinations
(2) 1 10pc coin - nos of 5pc coin will range from 3 to 0 i.e 4 combinations
(3) 0 10pc coin - nos of 5pc coin will range from 5 to 0 i.e 6 combinations

Case 3: when there is no 25 pc coins and
(1) 5 10pc coin - 1 ways
(2) 4 10pc coin - nos of 5pc coin will range from 2 to 0 i.e 3 combinations
(3) 3 10pc coin - nos of 5pc coin will range from 4 to 0 i.e 5 combinations
(4) 2 10pc coin - nos of 5pc coin will range from 6 to 0 i.e 7 combinations
(5) 1 10pc coin - nos of 5pc coin will range from 8 to 0 i.e 9 combinations
(6) 0 10pc coin - nos of 5pc coin will range from 10 to 0 i.e 11 combinations

So a total 49 different combinations.

i have give the solution but anyone know how to solve in short cut way??

my solution is select 2number from 4 given 4c2 after chosing 2 number take 3 permutation as 1
4c2*3!=48 and 1 for all remaning number
4c2*3!+1=48+1=49..

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 5n5n paisa, we have n+1n+1 ways: Use between 00 and nn (inclusive) 5ers and fill with 1ers.

To pay 5n5n paisas with 1ers, 5ers and 10ers, there are (cf. above) n+1n+1 ways without a 10er, n−1n−1 ways (if that is still ≥0≥0) with one 10er, n−3n−3 ways (if ≥0≥0) with two 10ers, and so on. So if n=2kn=2k is even, this is (2k+1)+(2k−1)+(2k−3)+…+5+3+1=(k+1)2(2k+1)+(2k−1)+(2k−3)+…+5+3+1=(k+1)2 and if n=2k−1n=2k−1 is odd, it is 2k+(2k−2)+(2k−4)+…+6+4+2=k(k+1)2k+(2k−2)+(2k−4)+…+6+4+2=k(k+1).

Finally, to pay 50=5⋅1050=5⋅10 paisas with 1ers, 5ers, 10ers, 25ers, we can use no 25er in (5+1)2(5+1)2 ways, one 25er in 3⋅43⋅4 ways, two 25ers in exactly 11 way. In total: 4949 ways.

On the other hand, to pay 45=5⋅945=5⋅9 paisas with 1ers, 5ers, 10ers, 25ers, we can use no 25er in 5⋅65⋅6 ways, or one 25er in (2+1)2(2+1)2 ways. In total: 3939 ways.

Originally Answered by : Hagen von Eitzen
Source : http://math.stackexchange.com/questions/1410188/how-many-combinations-are-possible-if-fare-is-50-paisa