Quantrex Quantrex AcademyJEE · NEET · NDA PYQs with solutions Open app
Olympiad workbook
Exam
Olympiad workbook
Subject
IOQM
Chapter
Permutation and Combination

Olympiad workbook · IOQM · Permutation and Combination

In the land of Binary, the unit of currency is called Ben and...

In the land of Binary, the unit of currency is called Ben and currency notes are available in denominations 1,2 , 22,23,…2^2, 2^3, \ldots. Bens. The rules of the Government of Binary stipulate that one can not use more than two notes of any one denomination in any transaction. For example, one can give a change for 2 Bens in two ways: 2 one Ben notes or 1 two Ben note. For 5 Ben one can give 1 one Ben note and 1 four Ben note or 1 one Ben note and 2 two Ben notes. Using 5 one Ben notes or 3 one Ben notes and 1 two Ben notes for a 5 Ben transaction is prohibited. Find the number of ways in which one can give change for 100 Bens, following the rules of the Government.

Correct answer

19

Step-by-step solution

1,2,22………1,2,2^2 \ldots \ldots \ldots. ∴a+2b+4c+…=1000≤a≤2,0≤b≤2……\therefore a+2 b+4 c+\ldots=100 \quad 0 \leq a \leq 2,0 \leq b \leq 2 \ldots \ldots a=0↓b+2c+…=50\begin{aligned} & a=0 \\ & \downarrow \\ & b+2 c+\ldots=50 \end{aligned} or, a=12(b+2c+…)=99⇒a=1 (not possible) \begin{aligned} & a=1 \\ & 2(b+2 c+\ldots)=99 \\ & \Rightarrow a=1 \text { (not possible) }\end{aligned} a=2↓b+2c+……=49⇒c+2d+……=24\begin{aligned} & a=2 \\ & \downarrow \\ & b+2 c+\ldots \ldots=49 \\ & \Rightarrow c+2 d+\ldots \ldots=24 \end{aligned}  Let number of solutions be a100\text { Let number of solutions be } a_{100} \begin{aligned} & a_{100}=a_{50}+a_{24} \\ & \quad \downarrow \\ & \begin{aligned} a_{100}= & \left(a_{25}+a_{24}\right)+a_{24}=a_{25}+2 a_{24} \\ & \downarrow \\ = & a_{12}+2\left(a_{12}+a_5\right) \end{aligned} \end{aligned}=3a12+2a5=3(a6+a2)+2(a2)=5a2+3a6=5a2+3(a3+a2)=8a2+3a3\begin{aligned} & =3 \mathrm{a}_{12}+2 \mathrm{a}_5 \\ & =3\left(a_6+a_2\right)+2\left(a_2\right) \\ & =5 a_2+3 a_6 \\ & =5 a_2+3\left(a_3+a_2\right) \\ & =8 a_2+3 a_3 \end{aligned}ForFora_3Let,Let,a+2 b+4 c=3a=1 \Rightarrow 2 b+4 c=2⇒b+2c=1⇒b=1,c=0\begin{aligned} & \Rightarrow b+2 c=1 \\ & \Rightarrow b=1, c=0\end{aligned}(1,1,0)onlyonesolutiononly one solution\therefore a_3=1ForFora_2::a+2b=2(0,1)(2,0)∴a2=2\begin{aligned} & a+2 b=2 \\ & (0,1)(2,0) \quad \therefore a_2=2 \end{aligned}∴a100=8(2)+3(1)=19 ways \begin{aligned} \therefore a_{100} & =8(2)+3(1) \\ & =19 \text { ways }\end{aligned}$
Practice Permutation and Combination on Quantrex Academy →

More from Permutation and Combination

All Permutation and Combination questions Full Permutation and Combination list All Olympiad workbook PYQs