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. Sherlock Homes agree to pay for Dr. Watson only if he tells all the possible
combinations of coins that can be used to pay for the ticket.
How many combinations are possible if the fare is 50 paise ?
A. 52
B. 49
C. 45
D. 44

• 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
• 8 years agoHelpfull: Yes(22) No(1)
• 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.
• 8 years agoHelpfull: Yes(9) No(0)
• i have give the solution but anyone know how to solve in short cut way??
• 8 years agoHelpfull: Yes(2) No(0)
• 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..
• 8 years agoHelpfull: Yes(2) No(2)
• 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
• 8 years agoHelpfull: Yes(0) No(1)