Paying with cash - part III

Probability Level 4

At a gas station I had to pay $53.78 with cash for gas, whiskey and sandwich. With plenty of pennies, nickels, dimes, quarters and paper money ($1 bill, $5 bills, $10 bills, $20 bills) in my pockets I can pay in any possible way $53 with paper bills, 78 cents with coins. In how many different ways can I pay with the exact amount of money?

576 6776 7890 3024

A Former Brilliant Member by A Former Brilliant Member

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

1 Helpful 0 Interesting 0 Brilliant 0 Confused

6 = 2 6 ∗ 3 2 = 18 ∗ 16 ; 3024 = 2 4 ∗ 3 3 ∗ 7 = 56 ∗ 54 ; 6776 = 2 3 ∗ 7 ∗ 1 1 2 = 56 ∗ 121 ; 7890 = 2 ∗ 3 ∗ 5 ∗ 263. 6=2^6*3^2=18*16;~~~~3024=2^4*3^3*7=56*54;~~~~6776=2^3*7*11^2=56*121;~~~~7890=2*3*5*263. 3 $ o f 53 $ a n d 3 c e n t s o f 78 c e n t s w i l l b e i n c l u d e d i n a l l p a y m e n t s , s o s u f f i c e t o l o o k a t 50 $ a n d 75 c e n t s . D i v i d e 53 $ p a y m e n t s i n t o t h r e e g r o u p s A , B , C , a n d 78 c e n t s i n t o f o u r g r o u p s W , X , Y , Z . m g r o u p i s t h e m a x i m u m p o s s i b l e 5 $ b i l l s o r n i c k e l s i n t h e g i v e n g r o u p . T h i s i s w h e n t h e p a y m e n t h a s n o 10 $ i n 53 $ o r n o d i m e i n 78 c e n t s . A . . . . . . . I t c o n t a i n s n o 20 $ b i l l s : − N e e d 53 $ ∴ c o n t r i b u t i o n b y 10 $ b i l l s + 5 $ b i l l s s h o u l d b e f r o m 0 $ t o 50 $ a n d t h e s h o r t f a l l f r o m 53 $ i s s u p p l i e d b y 1 $ b i l l s . t t h e n u m b e r o f 10 $ b i l l s w o u l d b e f r o m 0 t o 5. C o r r e s p o n d i n g f t h e n u m b e r o f 5 $ b i l l s w o u l d b e f r o m 0 t o ( 10 − 2 t ) . m A = 10. B . . . . . . . I t c o n t a i n s o n e 20 $ b i l l s : − N e e d 33 $ ∴ c o n t r i b u t i o n b y 10 $ b i l l s + 5 $ b i l l s s h o u l d b e f r o m 0 $ t o 30 $ a n d t h e s h o r t f a l l f r o m 33 $ i s s u p p l i e d b y 1 $ b i l l s . t w o u l d b e f r o m 0 t o 3. C o r r e s p o n d i n g f w o u l d b e f r o m 0 t o ( 6 − 2 t ) . m B = 6. C . . . . . . . I t c o n t a i n s t w o 20 $ b i l l s : − N e e d 13 $ ∴ C o n t r i b u t i o n b y 10 $ b i l l s + 5 $ b i l l s s h o u l d b e f r o m 0 $ t o 10 $ a n d t h e s h o r t f a l l f r o m 13 $ i s s u p p l i e d b y 1 $ b i l l s . t w o u l d b e f r o m 0 t o 1. C o r r e s p o n d i n g f w o u l d b e f r o m 0 t o ( 2 − 2 t ) . m C = 2. W . . . . . . . I t c o n t a i n s n o Q u a r t e r : − N e e d 78 c e n t s ∴ C o n t r i b u t i o n b y d i m e s + n i c k e l s s h o u l d b e f r o m 0 t o 75. a n d t h e s h o r t f a l l f r o m 78 c e n t s i s s u p p l i e d b y p e n n i e s . t t h e n u m b e r o f d i m e s w o u l d b e f r o m 0 t o 7. C o r r e s p o n d i n g f t h e n u m b e r o f n i c k e l s w o u l d b e f r o m 0 t o ( 15 − 2 t ) . m A = 15. X . . . . . . . I t c o n t a i n s o n e Q u a r t e r : − N e e d 53 c e n t s ∴ C o n t r i b u t i o n b y d i m e s + n i c k e l s s h o u l d b e f r o m 0 t o 50. a n d t h e s h o r t f a l l f r o m 78 c e n t s i s s u p p l i e d b y p e n n i e s . t w o u l d b e f r o m 0 t o 5. C o r r e s p o n d i n g f w o u l d b e f r o m 0 t o ( 10 − 2 t ) . m A = 10. Y . . . . . . . I t c o n t a i n s t w o Q u a r t e r : − N e e d 28 c e n t s ∴ C o n t r i b u t i o n b y d i m e s + n i c k e l s s h o u l d b e f r o m 0 t o 25. a n d t h e s h o r t f a l l f r o m 78 c e n t s i s s u p p l i e d b y p e n n i e s . t w o u l d b e f r o m 0 t o 2. C o r r e s p o n d i n g f w o u l d b e f r o m 0 t o ( 5 − 2 t ) . m A = 5. Z . . . . . . . I t c o n t a i n s t h r e e Q u a r t e r : − N e e d 3 c e n t s ∴ T h e r e a r e n o d i m e s o r n i c k e l s b u t t h r e e p e n n i e s . m A = 1. 3 \$~of~53 \$ ~and~3 cents~of~78 cents ~will~be~included~in~all~payments,~so~suffice ~to~look~at ~50 \$~and~75 cents.\\ ~~~\\ Divide~53 \$~payments~~into~three~groups~~A,~B,~C, ~and~78~cents~into~four~groups~~W,~X,~Y,~Z.\\ m_{group}~is~the~maximum~possible ~5 \$~bills~or~nickels~ in~the~given~group. This~is~when~the~payment~has~no~10 \$~in~53 \$~ or~no~dime~in~78 cents.\\ {\Huge \color{#20A900}{A}}.......It~contains~no~20 \$~bills:-~~Need~53 \$~~~~~~~\therefore~contribution~by~10 \$~bills+5 \$~bills~should ~be~from~0 \$~to~50 \$\\ and ~the~short~fall~from~53 \$~is~supplied~by~1 \$~bills. \\ ~t~the~number~of~10 \$ ~bills~would~be~from~0 ~to~5.~~Corresponding~f~the~number~of~5 \$ ~bills~would~be~from~0 ~to~(10-2t).~~~~ ~~~ m_A~=\color{#3D99F6}{10}.~\\ {\Huge \color{#20A900}{B}}.......It~contains~one~20 \$~bills:-~~Need~33 \$~~~~~~~\therefore~contribution~by~10 \$~bills+5 \$~bills~should ~be~from~0 \$~to~30 \$~\\ and ~the~short~fall~from~33 \$~is~supplied~by~1 \$~bills. \\ ~t~would~be~from~0 ~to~3.~~Corresponding~f~would~be~from~0 ~to~(6-2t).~~~~ ~~~ m_B~=\color{#3D99F6}{6}.~\\ {\Huge \color{#20A900}{C}}.......It~contains~two~20 \$~bills:-~~Need~13 \$~~~~~~~\therefore~Contribution~by~10 \$~bills+5 \$~bills~should ~be~from~0 \$~to~10 \$~\\ and ~the~short~fall~from~13 \$~is~supplied~by~1 \$~bills. \\ ~t~would~be~from~0 ~to~1.~~Corresponding~f~would~be~from~0 ~to~(2-2t).~~~~ ~~~ m_C~=\color{#3D99F6}{2}.~\\ {\Huge \color{#20A900}{W}}.......It~contains~no~Quarter:-~~Need~78 cents ~~~~~~~\therefore~Contribution~by~dimes+ nickels~should ~be~from~0~to~75.\\ and ~the~short~fall~from~78 cents~is~supplied~by~pennies. \\ ~t~the~number~of~dimes~would~be~from~0 ~to~7.~~Corresponding~f~the~number~of~nickels~would~be~from~0 ~to~(15-2t).~~~~ ~~~ m_A~=\color{#3D99F6}{15}.~\\ {\Huge \color{#20A900}{X}}.......It~contains~one~Quarter:-~~Need~53 cents ~~~~~~~\therefore~Contribution~by~dimes+ nickels~should ~be~from~0~to~50.\\ and ~the~short~fall~from~78 cents~is~supplied~by~pennies. \\ ~t~would~be~from~0 ~to~5.~~Corresponding~f~would~be~from~0 ~to~(10-2t).~~~~ ~~~ m_A~=\color{#3D99F6}{10}.~\\ {\Huge \color{#20A900}{Y}}.......It~contains~two~Quarter:-~~Need~28 cents ~~~~~~~\therefore~Contribution~by~dimes+ nickels~should ~be~from~0~to~25.\\ and ~the~short~fall~from~78 cents~is~supplied~by~pennies. \\ ~t~would~be~from~0 ~to~2.~~Corresponding~f~would~be~from~0 ~to~(5-2t).~~~~ ~~~ m_A~=\color{#3D99F6}{5}.~\\ {\Huge \color{#20A900}{Z}}.......It~contains~three~Quarter:-~~Need~3 cents ~~~~~~~\therefore~There~are~no~dimes~or~ nickels~but~three~pennies.~~~ ~~~~~~~~~~~m_A~=\color{#3D99F6}{1}.~\\
N t h e n u m b e r o f w a y s w e c a n p a y , d e p e n d s o n m g r o u p . F o r e v e n m g r o u p , N = ( m g r o u p 2 + 1 ) 2 . F o r o d d m g r o u p , N = ( m g r o u p + 1 2 ) 2 + m g r o u p + 1 2 N A = ( 10 2 + 1 ) 2 = 36 N B = ( 6 2 + 1 ) 2 = 16. N C = ( 2 2 + 1 ) 2 = 4..................................... N 53 = 36 + 16 + 4 = 56. N W = ( 15 + 1 2 ) 2 + 15 + 1 2 = 64 + 8 = 72 N X = ( 10 2 + 1 ) 2 = 36. N Y = ( 5 + 1 2 ) 2 + 5 + 1 2 = 9 + 3 = 12 N Z = 1................... N 78 = 72 + 36 + 12 + 1 = 121. N~the~ number~of ~ways~we~can~pay,~depends~on~m_{group}.\\ For~even~m_{group},~N=\left(\dfrac{ m_{group}} 2 +1 \right )^2.\\ For~odd~m_{group},~N=\left (\dfrac{ m_{group}+1} 2 \right )^2+ \dfrac{ m_{group}+1} 2\\ ~~~\\ N_A=\left(\dfrac {10} 2 +1 \right )^2=36~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~N_B=\left(\dfrac 6 2 +1 \right )^2=16.\\ N_C=\left(\dfrac 2 2 +1 \right )^2=4 .....................................N_{53}=36+16+4=56.\\ N_W=\left (\dfrac{15+1}2 \right )^2+ \dfrac{ 15+1} 2=64+8=72~~~~~~~~~~~~~ N_X=\left(\dfrac{10} 2 +1 \right )^2=36.\\ N_Y=\left ( \dfrac {5+1} 2 \right )^2+ \dfrac{ 5+1} 2=9+3=12~~~~~~~~~~~~~N_Z=1...................N_{78}=72+36+12+1=121.\\ ~~~ \\
N 56 ∗ 121 = 6776 N_{56*121}=\Large \color{#D61F06}{6776}
B e l o w f i n d d e t a i l e d e x p l a n a t i o n . I f I g e t t i m e I w i l l m a k e i t o r d e r l y Below ~find~detailed~explanation.~~If~I~get~time~I~will~make~it~orderly 6 = 2 6 ∗ 3 2 = 18 ∗ 16 ; 3024 = 2 4 ∗ 3 3 ∗ 7 = 56 ∗ 54 ; 6776 = 2 3 ∗ 7 ∗ 1 1 2 = 56 ∗ 121 ; 7890 = 2 ∗ 3 ∗ 5 ∗ 263. L e t p ⟹ p e n n i e s . . . . . . . . . . n ⟹ n i c k e l s . . . . . . . . . . d ⟹ d i m s . . . . . . . . . q ⟹ Q u a r t e r s . V a r i o u s c o m b i n a t i o n s o f 20 $ , 10 $ , a n d 5 $ b i l l s c a n a d d u p f r o m 5 $ t o 50 $ i n m u l t i p l e s o f 5 $ . p l u s p 1 $ b i l l c a n g i v e a t o t a l o f 53 $ . ∴ i t i s s u f f i c i e n t t o f i x 20 $ , 10 $ a n d 5 $ b i l l s . n . m m e a n s n o f m $ . D i v i d e 0 $ t o 50 $ i n t o t h r e e g r o u p s A , B , C . A 0.20 + t . 10 + f . 5 + p . 1. C o n t r i b u t i o n o f 10 a n d 5 $ b i l l s i s 0 $ t o 50 $ i n m u l t i p l e s o f 5 $ . t t h e r a n g e o f 10 $ b i l l s i s t = 0 t o 5. f t h e r a n g e o f 5 $ b i l l s i s f = 0 t o ( 10 − 2 t ) t h a t i s 0.5 t o ( 10 − 2 t ) . 5 p w o u l d c o n t r i b u t e t o t h e s h o r t f a l l f r o m 53 $ a s s h o w n i n t a b l e f o r A i n d e t a i l . B 1.20 + t . 10 + f . 5 + p . 1. C o n t r i b u t i o n o f 10 a n d 5 $ b i l l s i s 0 $ t o 30 $ i n m u l t i p l e s o f 5 $ . t = 0 t o 3. f = 0 t o ( 6 − 2 t ) p w o u l d c o n t r i b u t e t o t h e s h o r t f a l l f r o m 33 $ a s i n t a b l e f o r B . C 2.20 + t . 10 + f . 5 p + p . 1. C o n t r i b u t i o n o f 10 a n d 5 $ b i l l s i s $ . 0 $ t o 10 $ i n m u l t i p l e s o f 5 $ . t = 0 t o 1. f = 0 t o ( 2 − 2 t ) p w o u l d c o n t r i b u t e t o t h e s h o r t f a l l f r o m 13 $ a s i n t a b l e f o r C . 6=2^6*3^2=18*16;~~~~3024=2^4*3^3*7=56*54;~~~~6776=2^3*7*11^2=56*121;~~~~7890=2*3*5*263.\\ Let~p \implies pennies..........n \implies nickels..........d \implies dims.........q \implies Quarters.\\ Various~combinations~of~~~~20 ~\$,~10~\$,~and~5 ~\$~bills~~~can~add~up~~from~5~\$~to~50~\$~in ~multiples~of~5~\$.\\ ~plus~p~1~\$~bill~can~give~a~total~of~53~\$.\\ \therefore~it~is~sufficient~to~fix~~~20 ~\$,~10~\$~and~5 ~\$~~bills. \\ ~~ \\ n.m~~means~~n~of~m~\$.\\ ~~~\\ Divide~0~\$~~to~~50~\$~~~into~three~groups~A,~B,~C.\\ A~~~~~0.20+t.10+f.5+p.1.~~Contribution~of~10~and~5~\$~bills~~is~~0~\$~to~50~\$~~in ~multiples~of~5~\$. \\ ~~~~~~~~t~the~range~of~10~\$~bills~is~~t=0~~to~~5.\\ ~~~~~~~~f~the~range~of~5~\$~bills~is~~f=0~~to~~(10-2t)~that~is~0.5~~to~~(10-2t).5\\ ~~~~~~~~p~would~contribute~to~the~short~fall~from~53~\$~~~as~shown~in~table~for~A~in~detail.\\ B~~~~~1.20+t.10+f.5+p.1.~~Contribution~of~10~and~5~\$~bills~~is~~~0~\$~to~30~\$~~in ~multiples~of~5~\$.~~~~~t=0~to~3.~~~f=0~to~(6-2t)\\ ~~~~~~~~p~would~contribute~to~the~short~fall~from~33~\$~~as~in~~table~for~B. \\ C~~~~~2.20+t.10+f.5p+p.1.~~Contribution~of~10~and~5~\$~bills~~is~~~~\$.0~\$~to~10~\$~~in ~multiples~of~5~\$.~~~ ~~t=0~to~1.~~~f=0~to~(2-2t)~~~\\ p~would~contribute~to~the~short~fall~from~13~\$~~~as~in~~table~for~C. \\ ~~\\

G r o u p N u m b e r o f t = N u m b e r o f f = N u m b e r o f N u m b e r o f W a y s 20 $ + 10 $ + 5 $ + 1 $ A 0 0 0 53 1 1 48 2 2 43 3 3 38 4 4 33 5 5 28 6 6 23 7 7 18 8 8 13 9 9 8 10 10 3 11 1 0 43 1 1 38 2 2 33 3 3 28 4 4 23 5 5 18 6 6 13 7 7 8 8 8 3 9 2 0 33 1 1 28 2 2 23 3 3 18 4 4 13 5 5 8 6 6 3 7 3 0 23 1 1 18 2 2 13 3 3 8 4 4 3 5 4 0 13 1 1 8 2 2 3 3 5 0 3 1 B 1 0 0 33 1 1 28 2 2 23 3 3 18 4 4 13 5 5 8 6 6 3 7 1 0 23 1 1 18 2 2 13 3 3 8 4 4 3 5 2 0 13 1 1 8 2 2 3 3 3 0 3 1 C 2 0 0 13 1 1 8 2 2 3 3 1 0 3 1 \begin{array}{ l | c | c|c|c|r} \hline Group&Number ~of &t=Number~of &f=Number~of& Number~of&Ways \\ \hline & \color{#D61F06}{20~\$}+ &\color{#3D99F6}{10~\$}+ & 5~\$+ &1~\$ \\ \hline \\ \Huge~\color{#20A900}{A} &\color{#D61F06}{0}\\ & &\color{#3D99F6}{0} & 0 & 53&1 \\ & & & 1 & 48&2 \\ & & & 2& 43 &3\\ && &3 & 38&4 \\ & & &4 & 33&5 \\ & & & 5 & 28&6 \\ && & 6 & 23&7 \\ & &&7 & 18&8 \\ & && 8&13&9 \\ && & 9& 8&10 \\ & &&10 & 3&11 \\ ~~~ \\ &&\color{#3D99F6}{1} & 0 & 43&1 \\ && & 1 & 38&2\\ && & 2& 33 &3\\ & &&3 & 28&4 \\ & & &4 &23&5 \\ && & 5 &18&6 \\ & & & 6 &13&7 \\ & &&7 &8&8 \\ & & & 8&3&9 \\ ~~ \\ & &\color{#3D99F6}{2} & 0 & 33&1 \\ & & & 1 & 28&2 \\ & & & 2& 23 &3\\ && &3 &1 8&4 \\ & & &4 &13&5\\ & && 5 &8&6 \\ & & & 6 &3&7 \\ ~~ \\ &&\color{#3D99F6}{3}& 0 & 23&1 \\ & & & 1 & 18&2 \\ & & & 2& 13 &3\\ && &3 & 8&4\\ & & &4 &3&5 \\ ~~ \\ &&\color{#3D99F6}{4}& 0 &13&1\\ & & & 1 & 8&2 \\ & && 2& 3 &3\\ ~~~\\ & &\color{#3D99F6}{5} & 0 &3&1\\ ~~\\ \Huge~\color{#20A900}{B} &\color{#D61F06}{1}\\ &&\color{#3D99F6}{0}& 0 & 33&1 \\ & & & 1 & 28&2 \\ & && 2& 23 &3\\ & & &3 & 18&4 \\ & & &4 & 13&5 \\ && & 5 &8&6 \\ & && 6 & 3&7 \\ ~~~\\ &&\color{#3D99F6}{1}& 0 & 23&1\\ & & & 1 & 18&2\\ & && 2& 13 &3\\ & & &3 & 8&4\\ && &4 &3&5\\ ~~~\\ & &\color{#3D99F6}{2} & 0 &13&1\\ && & 1 & 8&2 \\ & && 2& 3 &3\\ ~~\\ &&\color{#3D99F6}{3}& 0 &3&1\\ ~~~~ \\ \Huge~\color{#20A900}{C} &\color{#D61F06}{2}\\ &&\color{#3D99F6}{0} & 0 & 13&1 \\ && & 1 & 8&2 \\ & && 2& 3 &3\\ ~~~\\ &&\color{#3D99F6}{1}& 0 & 3&1 \\ \hline \end{array} \\ \\ ~~\\~~\\
A = 11 + 9 + 7 + 5 + 3 + 1 = 36 = ( 10 2 + 1 ) 2 . B = 7 + 5 + 3 + 1 = 16 = ( 6 2 + 1 ) 2 . C = 3 + 1 = 4 = ( 2 2 + 1 ) 2 . N o t e : I f i n a g r o u p , m t h e m a x i m u m 5 $ b i l l ( o r n i c k e l s ) c a n c o n t r i b u t e i s e v e n , t h e n t h e n u m b e r o f w a y s = ( m 2 + 1 ) 2 . I f i n a g r o u p , m t h e m a x i m u m 5 $ b i l l ( o r n i c k e l s ) c a n c o n t r i b u t e i s o d d , t h e n t h e n u m b e r o f w a y s = ( m + 1 2 ) 2 + m + 1 2 = 1 4 ∗ ( m 2 + 4 m + 3 ) . A=11+9+7+5+3+1=36=\left (\dfrac {10} 2 +1 \right )^2.\\ B= 7+5+3+1=16=\left (\dfrac 6 2+1 \right )^2. \\ C=3+1=4=\left (\dfrac 2 2+1 \right )^2.\\ Note~:If~in ~~a ~group,~~~m~the~maximum~5~\$~bill~(or ~ nickels)~can~contribute~is~ { \color{#BA33D6}{even}},\\ then~~the~ number ~of~ways=\left (\dfrac m 2 +1 \right )^2.\\ If~in ~~a ~group,~~~m~the~maximum~5~\$~bill~(or ~ nickels)~can~contribute~is~ { \color{#BA33D6}{odd}},\\ then~~the~ number ~of~ways=\left (\dfrac{ m+1}2 \right )^2+ \dfrac{ m+1} 2=\frac 1 4*(m^2+4m+3).
36 + 16 + 4 = 56 \Large 36+16+4=\color{#EC7300}{56}

⟹ w e h a v e 56 w a y s t o g e t 53 $ . \implies~we~have~{ \color{#EC7300}{56}}~ways~to~get~53~\$.\\
Total ways to get 53.78 $ ={ ways we get for 53 $= 56}*{ways we get .78 $.}
It is easy to see that . 78 $ w a y s a r e m o r e t h a n w a y s o f 53 $ . ~\color{#3D99F6}{~.78~ \$ ~ways ~are~ more~ than ~ways~ of ~53 \$. }

576 a n d 7890 a r e n o t d i v i s i b l e b y 56. S o c a n n o t b e t h e s o l u t i o n . 3024 56 = 54 < 56. S o c a n n o t b e t h e s o l u t i o n . I f t h e s o l u t i o n i s i n t h e g i v e n o p t i o n s 6776 m u s t b e t h e s o l u t i o n . H o w e v e r o n t h e s a m e b a s e s b e l o w i s s h o r t p r o o f o f 121 w a y s w e c a n g e t 0.78 c e n t s . 576 ~and~7890~are~not~divisible~by~56. So~can~not~be~the~solution.\\ \dfrac{3024}{56}=54<56.~~ So~can~not~be~the~solution.\\ If~the~solution~is~in~the~given~options~~~\large { \color{#BA33D6}{6776}}~~~must~be~the~solution.\\ However~on~the~same~bases~below~ is~short~proof~of~121~ways~we~can~get~0.78~cents.\\

L e t p ⟹ p e n n i e s . . . . . . . . . . n ⟹ n i c k e l s . . . . . . . . . . d ⟹ d i m s . . . . . . . . . q ⟹ Q u a r t e r s . G r o u p W n o Q u a r t e r . . . . . . . . . . t . d + f . n = 0 t o 75 c e n t s . + n e c e s s a r y n i c k e l s = 78 c e n t s . G r o u p X o n e Q u a r t e r . . . . . . . . t . d + f . n = 0 t o 50 c e n t s . + n e c e s s a r y n i c k e l s = 78 c e n t s . G r o u p Y t w o Q u a r t e r . . . . . . . . t . d + f . n = 0 t o 25 c e n t s . + n e c e s s a r y n i c k e l s = 78 c e n t s . G r o u p Z t h r e e Q u a r t e r . . . . . . t . d + f . n = 0 c e n t + 3 n i c k e l s = 78 c e n t s . G r o u p N u m b e r o f q t = N u m b e r o f d f = N u m b e r o f n W a y s W 0 0 0. n t o 15. n 16 1 0. n t o 13. n 14 2 0. n t o 11. n 12 3 0. n t o 9. n 10 4 0. n t o 7. n 8 5 0. n t o 5. n 6 6 0. n t o 3. n 4 7 0. n t o 1. n 2 72 X 1 0 0. n t o 10. n 11 1 0. n t o 8. n 9 2 0. n t o 6. n 7 3 0. n t o 4. n 5 4 0. n t o 2. n 3 5 0. n 1 36 Y 2 0 0. n t o 5. n 6 1 0. n t o 3. n 4 2 0. n t o 1. n 2 12 Z 3 0 0. n 1 Let~p \implies pennies..........n \implies nickels..........d \implies dims.........q \implies Quarters.\\ Group~W~no~Quarter..........t.d+f.n=~0~~to~~75~cents.~+~necessary~nickels= 78 cents. \\ Group~X~one~Quarter........t.d+f.n=~0~~to~~50~cents.~+~necessary~nickels= 78 cents. \\ Group~Y~two~Quarter........t.d+f.n=~0~~to~~25~cents.~+~necessary~nickels= 78 cents. \\ Group~Z~three~Quarter......t.d+f.n=~0~cent~+~3~nickels= 78 cents. \\ ~~~\\ ~~~\\ \begin{array}{ l | c | c|c|c|r} \hline Group&Number ~of~q &t=Number~of ~d &f=Number~of~n& Ways \\ \hline \Huge~\color{#20A900}{W} &\color{#D61F06}{0}\\ & &\color{#3D99F6}{0}& 0.n~to~15.n&16\\ & &\color{#3D99F6}{1}& 0.n~to~13.n&14\\ & &\color{#3D99F6}{2}& 0.n~to~11.n&12\\ & &\color{#3D99F6}{3}& 0.n~to~9.n&10\\ & &\color{#3D99F6}{4}& 0.n~to~7.n&8\\ & &\color{#3D99F6}{5}& 0.n~to~5.n&6\\ & &\color{#3D99F6}{6}& 0.n~to~3.n&4\\ & &\color{#3D99F6}{7}& 0.n~to~1.n&2\\ \hline & & & &72\\ \hline \Huge~\color{#20A900}{X} &\color{#D61F06}{1}\\ & &\color{#3D99F6}{0}& 0.n~to~10.n&11\\ & &\color{#3D99F6}{1}& 0.n~to~8.n&9\\ & &\color{#3D99F6}{2}& 0.n~to~6.n&7\\ & &\color{#3D99F6}{3}& 0.n~to~4.n&5\\ & &\color{#3D99F6}{4}& 0.n~to~2.n&3\\ & &\color{#3D99F6}{5}& ~~~0.n~~~&1\\ \hline & & & &36\\ \hline \Huge~\color{#20A900}{Y} &\color{#D61F06}{2}\\ & &\color{#3D99F6}{0}& 0.n~to~5.n&6\\ & &\color{#3D99F6}{1}& 0.n~to~3.n&4\\ & &\color{#3D99F6}{2}& 0.n~to~1.n&2\\ \hline & & & &12\\ \hline \Huge~\color{#20A900}{Z} &\color{#D61F06}{3}&\color{#3D99F6}{0}&0.n&1 \\ \hline \end{array}\\~~~ \\

W + X + Y + Z = 72 + 36 + 12 + 1 = 121 56 ∗ 121 = 6776. W+X+Y+Z=72+36+12+1=\Large \color{#EC7300}{121}\\ \Huge 56*121=\color{#D61F06}{6776}.

Details shown in table ABC could be shortened as in WXYZ and 1 $ column can be eliminated.

L e t n . m m e a n s n o f m $ a n d n . c o i n m e a n s n o f g i v e n c o i n . S i n c e 3 $ o f 53 $ w i l l b e i n c l u d e d i n a l l p a y m e n t s , s u f f i c e t o l o o k a t t h e w a y s t o p a y 50 $ . S i m i l a r l y s u f f i c e t o c o n s i d e r o n l y 75 c e n t s , s i n c e a l l p a y m e n t s w i l l h a v e 3 p e n n i e s i n i t . D i v i d e 53 $ p a y m e n t s i n t o t h r e e g r o u p s A , B , C , a n d 78 c e n t s i n t o f o u r g r o u p s W , X , Y , Z . m g r o u p i s t h e n u m b e r o f 5 $ b i l l s w h e n i n t h e g r o u p , c o n t r i b u t i o n o f 20 l s + m g r o u p . 5 + 3.1 = 53 $ . m g r o u p i s t h e n u m b e r o f n i c k e l s w h e n i n t h e g r o u p , c o n t r i b u t i o n o f Q u a r t e r s + m g r o u p . 5 + 3.1 = 78 c e n t s . A . . . . . I t c o n t a i n s n o 20 $ b i l l s : − . . . . ∴ 0 $ ≤ ( t . 10 + f . 5 ) ≤ 50 $ i n m u l t i p l e s o f 5 $ + 1 $ b i l l s = 53 $ . 0 ≤ t ≤ 5 i s t h e r a n g e o f 10 $ b i l l s . 0 ≤ f ≤ 10 i s t h e r a n g e o f 5 $ b i l l s . m A = 10. B . . . . . I t c o n t a i n s o n e 20 $ b i l l . ∴ 0 $ ≤ ( t . 10 + f 5 ) ≤ 30 $ i n m u l t i p l e s o f 5 $ + 1 $ b i l l s = 53 $ . 0 ≤ t ≤ 3 i s t h e r a n g e o f 10 $ b i l l s . 0 ≤ f ≤ 6 i s t h e r a n g e o f 5 $ b i l l s . m B = 6. C . . . . I t c o n t a i n s t w o 20 $ b i l l s : ∴ 0 $ ≤ ( t . 10 + f 5 ) ≤ 10 $ i n m u l t i p l e s o f 5 $ , + 1 $ b i l l s = 53 $ . 0 ≤ t ≤ 1 i s t h e r a n g e o f 10 $ b i l l s . 0 ≤ f ≤ 2 i s t h e r a n g e o f 5 $ b i l l s . m C = 2. W . . . . . I t c o n t a i n s n o Q u a r t e r s : − ∴ 0 c e n t ≤ ( t . d i m e + f . n i c k e l ) ≤ 75 c e n t i n m u l t i p l e s o f 5 c e n t s + p e n n i e s = 78 c e n t s . 0 ≤ t ≤ 7 i s t h e r a n g e o f d i m e s . 0 ≤ f ≤ 15 i s t h e r a n g e o f n i c k e l s . m W = 15. X . . . . . I t c o n t a i n s o n e Q u a r t e r : − ∴ 0 c e n t ≤ ( t . d i m e + f . n i c k e l ) ≤ 50 c e n t i n m u l t i p l e s o f 5 c e n t s + p e n n i e s = 78 c e n t s . 0 ≤ t ≤ 5 i s t h e r a n g e o f d i m e s . 0 ≤ f ≤ 10 i s t h e r a n g e o f n i c k e l s . m X = 10. Y . . . . . I t c o n t a i n s t w o Q u a r t e r s : − ∴ 0 c e n t ≤ ( t . d i m e + f . n i c k e l ) ≤ 25 c e n t i n m u l t i p l e s o f 5 c e n t s + p e n n i e s = 78 c e n t s . 0 ≤ t ≤ 2 i s t h e r a n g e o f d i m e s . 0 ≤ f ≤ 5 i s t h e r a n g e o f n i c k e l s . m Y = 15. Z . . . . . I t c o n t a i n s t h r e e Q u a r t e r s : − S o o n l y o n e w a y o f p a y m e n t , 3. Q u a r t e r + 3. p e n n i e s . m Z = 1. Let~n.m~~means~~n~of~m \$~and~n.coin~means~n~of~given~coin.\\ ~~~\\ Since~3 \$~of~53 \$ ~will~be~included~in~all~payments,~suffice ~to~look~at ~the~ways~to~pay~50 \$.\\ Similarly~suffice~to~consider~only~75~ cents,~since~all~payments~will~have~3~pennies~in~it.\\ ~~~\\ Divide~53 \$~payments~~into~three~groups~~A,~B,~C, ~and~78~cents~into~four~groups~~W,~X,~Y,~Z.\\ m_{group}~is~the~number~of~5 \$~bills~when~in~the~group,~contribution~of~20 ls~~+m_{group}.5+3.1 =53 \$. \\ m_{group}~is~the~number~of~nickels~when~in~the~group,~contribution~of~Quarters~+m_{group}.5+3.1 =78 cents. \\ {\Huge \color{#20A900}{A}}.....It~contains~no~20 \$~bills:-....\therefore~~0\$ \leq ( t.10+f.5 ) \leq 50 \$~~in ~multiples~of~5 \$+1 \$~bills=53 \$. \\ ~~~~~0 \leq t \leq 5~is~the~range~of~10 \$~bills.~~~~0 \leq f \leq 10 ~is~the~range~of~5 \$~bills.~~~~ m_A~=\color{#3D99F6}{10}.~\\ {\Huge \color{#20A900}{B}}.....It~contains~one~20 \$ ~bill.~\therefore~0\$ \leq ( t.10+f5 ) \leq 30 \$~~in ~multiples~of~5 \$+~1 \$~bills=53 \$. \\ ~~~~~0 \leq t \leq 3~is~the~range~of~10 \$~bills.~~~~0 \leq f \leq 6 ~is~the~range~of~5 \$~bills.~~~~ m_B~=\color{#3D99F6}{6}.~\\ {\Huge \color{#20A900}{C}}....It~contains~two~20 \$~bills:\therefore~0\$ \leq ( t.10+f5 ) \leq 10 \$~~in ~multiples~of~5 \$,+~1 \$~bills=53 \$. \\ ~~~~~0 \leq t \leq 1~is~the~range~of~10 \$~bills.~~~~0 \leq f \leq 2 ~is~the~range~of~5 \$~bills.~~~~ m_C~=\color{#3D99F6}{2}.~\\ {\Huge \color{#20A900}{W}}.....It~contains~no~Quarters:-\\ \therefore~~0~cent \leq ( t.dime+f.nickel ) \leq 75 cent~in ~multiples~of~5~cents+pennies =78~cents.\\ ~~~~~0 \leq t \leq 7~is~the~range~of~dimes.~~~~0 \leq f \leq 15 ~is~the~range~of~nickels.~~~~ m_W~=\color{#3D99F6}{15}.\\ {\Huge \color{#20A900}{X}}.....It~contains~one~Quarter:-\\ \therefore~~0~cent \leq ( t.dime+f.nickel ) \leq 50 cent~in ~multiples~of~5~cents+pennies =78~cents.\\ ~~~~~0 \leq t \leq 5~is~the~range~of~dimes.~~~~0 \leq f \leq 10 ~is~the~range~of~nickels.~~~~ m_X~=\color{#3D99F6}{10}.\\ {\Huge \color{#20A900}{Y}}.....It~contains~two~Quarters:-\\ \therefore~~0~cent \leq ( t.dime+f.nickel ) \leq 25 cent~in ~multiples~of~5~cents+pennies =78~cents.\\ ~~~~~0 \leq t \leq2~is~the~range~of~dimes.~~~~0 \leq f \leq 5 ~is~the~range~of~nickels.~~~~ m_Y~=\color{#3D99F6}{15}.\\ {\Huge \color{#20A900}{Z}}.....It~contains~three~Quarters:-~~~So~only~one~way~of~payment,~3.Quarter+3.pennies. ~m_Z~=\color{#3D99F6}{1}.~\\ ~~\\
N t h e n u m b e r o f w a y s w e c a n p a y , d e p e n d s o n m g r o u p . F o r e v e n m g r o u p , N = ( m g r o u p 2 + 1 ) 2 . F o r o d d m g r o u p , N = ( m g r o u p + 1 2 ) 2 + m g r o u p + 1 2 N A = ( 10 2 + 1 ) 2 = 36 N B = ( 6 2 + 1 ) 2 = 16. N C = ( 2 2 + 1 ) 2 = 4..................................... N 53 = 36 + 16 + 4 = 56. N W = ( 15 + 1 2 ) 2 + 15 + 1 2 = 64 + 8 = 72 N X = ( 10 2 + 1 ) 2 = 36. N Y = ( 5 + 1 2 ) 2 + 5 + 1 2 = 9 + 3 = 12 N Z = 1................... N 78 = 72 + 36 + 12 + 1 = 121. N~the~ number~of ~ways~we~can~pay,~depends~on~m_{group}.\\ For~even~m_{group},~N=\left(\dfrac{ m_{group}} 2 +1 \right )^2.\\ For~odd~m_{group},~N=\left (\dfrac{ m_{group}+1} 2 \right )^2+ \dfrac{ m_{group}+1} 2\\ ~~~\\ N_A=\left(\dfrac {10} 2 +1 \right )^2=36~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~N_B=\left(\dfrac 6 2 +1 \right )^2=16.\\ N_C=\left(\dfrac 2 2 +1 \right )^2=4 .....................................N_{53}=36+16+4=56.\\ N_W=\left (\dfrac{15+1}2 \right )^2+ \dfrac{ 15+1} 2=64+8=72~~~~~~~~~~~~~ N_X=\left(\dfrac{10} 2 +1 \right )^2=36.\\ N_Y=\left ( \dfrac {5+1} 2 \right )^2+ \dfrac{ 5+1} 2=9+3=12~~~~~~~~~~~~~N_Z=1...................N_{78}=72+36+12+1=121.\\ ~~~ \\
N 56 ∗ 121 = 6776 N_{56*121}=\Large \color{#D61F06}{6776}

Niranjan Khanderia - 2 years, 5 months ago

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...