Question and Answers Forum

All Questions      Topic List

Permutation and Combination Questions

Previous in All Question      Next in All Question      

Previous in Permutation and Combination      Next in Permutation and Combination      

Question Number 59021 by mr W last updated on 03/May/19

[Q58885 reposted] How many 4−digit numbers abcd exist which are divisible by 3 and satisfy a≤b≤c≤d?

$$\left[{Q}\mathrm{58885}\:{reposted}\right] \\ $$$${How}\:{many}\:\mathrm{4}−{digit}\:{numbers}\:{abcd}\:{exist} \\ $$$${which}\:{are}\:{divisible}\:{by}\:\mathrm{3}\:{and}\:{satisfy} \\ $$$${a}\leqslant{b}\leqslant{c}\leqslant{d}? \\ $$

Commented by tanmay last updated on 03/May/19

is there any co−relation between this problem and Euler enumeration partition ...

$${is}\:{there}\:{any}\:{co}−{relation}\:{between}\:{this}\:{problem} \\ $$$${and}\:{Euler}\:{enumeration}\:{partition}\:... \\ $$

Commented by mr W last updated on 03/May/19

It′s not as easy as I thought. Please give a try.

$${It}'{s}\:{not}\:{as}\:{easy}\:{as}\:{I}\:{thought}.\:{Please} \\ $$$${give}\:{a}\:{try}. \\ $$

Commented by Kunal12588 last updated on 03/May/19

Commented by Kunal12588 last updated on 03/May/19

I think it may help someone who is trying to solve the problem.

Commented by mr W last updated on 03/May/19

thank you sir! can you give a formula how to calculate the number without knowing the numbers themselves?

$${thank}\:{you}\:{sir}! \\ $$$${can}\:{you}\:{give}\:{a}\:{formula}\:{how}\:{to}\:{calculate}\:{the} \\ $$$${number}\:{without}\:{knowing}\:{the}\:{numbers} \\ $$$${themselves}? \\ $$

Commented by mr W last updated on 03/May/19

my formula (not exactly proved yet) is (C_(9−1) ^(4+9−1) /3)=(C_8 ^(12) /3)=((495)/3)=165 in case of 5−digit numbers it is (C_(9−1) ^(5+9−1) /3)=(C_8 ^(13) /3)=((1287)/3)=429 in case of 6−digit numbers it is (C_(9−1) ^(6+9−1) /3)=(C_8 ^(14) /3)=((3003)/3)=1001 can you check them using your method?

$${my}\:{formula}\:\left({not}\:{exactly}\:{proved}\:{yet}\right)\:{is} \\ $$$$\frac{{C}_{\mathrm{9}−\mathrm{1}} ^{\mathrm{4}+\mathrm{9}−\mathrm{1}} }{\mathrm{3}}=\frac{{C}_{\mathrm{8}} ^{\mathrm{12}} }{\mathrm{3}}=\frac{\mathrm{495}}{\mathrm{3}}=\mathrm{165} \\ $$$$ \\ $$$${in}\:{case}\:{of}\:\mathrm{5}−{digit}\:{numbers}\:{it}\:{is} \\ $$$$\frac{{C}_{\mathrm{9}−\mathrm{1}} ^{\mathrm{5}+\mathrm{9}−\mathrm{1}} }{\mathrm{3}}=\frac{{C}_{\mathrm{8}} ^{\mathrm{13}} }{\mathrm{3}}=\frac{\mathrm{1287}}{\mathrm{3}}=\mathrm{429} \\ $$$$ \\ $$$${in}\:{case}\:{of}\:\mathrm{6}−{digit}\:{numbers}\:{it}\:{is} \\ $$$$\frac{{C}_{\mathrm{9}−\mathrm{1}} ^{\mathrm{6}+\mathrm{9}−\mathrm{1}} }{\mathrm{3}}=\frac{{C}_{\mathrm{8}} ^{\mathrm{14}} }{\mathrm{3}}=\frac{\mathrm{3003}}{\mathrm{3}}=\mathrm{1001} \\ $$$$ \\ $$$${can}\:{you}\:{check}\:{them}\:{using}\:{your}\:{method}? \\ $$

Commented by mr W last updated on 03/May/19

ajfour sir, MJS sir, tanmay sir: can you please also have a look at this problem?

$${ajfour}\:{sir},\:{MJS}\:{sir},\:{tanmay}\:{sir}: \\ $$$${can}\:{you}\:{please}\:{also}\:{have}\:{a}\:{look}\:{at}\:{this} \\ $$$${problem}? \\ $$

Commented by Kunal12588 last updated on 03/May/19

Commented by Kunal12588 last updated on 03/May/19

Commented by Kunal12588 last updated on 03/May/19

Sir MrW you are correct with 5-digit numbers There are 429 such numbers. but for 6-digit number they are total 1005.

Answered by Rasheed.Sindhi last updated on 03/May/19

I don′t know any formula.I want to think about ′process′ of determining required number.Although I′m not sure of my process being useful at this stage. I think upto three digits we need not be anxious about divisibility of 3. It′s only fixation of one digit which makes the number divisible by 3. So upto abc we should consider only one condition that is a≤b≤c. The fourth digit (unit) d may be fixed in such a way that it makes the number multiple of 3 along with d≥c. Particularily if a_0 b_0 c_(0 ) is any of such permutations and d is unit digit then for 3m>a_0 +b_0 +c_0 &1≤3m−(a_0 +b_0 +c_0 )≤9: d≥c ∧ d=3m−(a_0 +b_0 +c_0 ) For example if abc=112 According to the condition d≥c , the candidates for d are 2,3,4,...,9 but only 2,5 & 8 are such which make the number divisible by 3. So three numbers (1122,1125 & 1128) can be made from 112 The limitation of the process is this that we have to compose all the three digit numbers abc with condition a≤b≤c So this is not a good method to determine number of the required numbers. However it may be used to construct numbers under the given conditions

$${I}\:{don}'{t}\:{know}\:{any}\:{formula}.{I}\:{want}\:{to} \\ $$$${think}\:{about}\:'{process}'\:{of}\:{determining} \\ $$$${required}\:{number}.{Although}\:{I}'{m}\:{not} \\ $$$${sure}\:{of}\:{my}\:{process}\:{being}\:\:{useful}\:{at} \\ $$$${this}\:{stage}. \\ $$$${I}\:{think}\:{upto}\:{three}\:{digits}\:{we}\:{need}\:{not} \\ $$$${be}\:{anxious}\:{about}\:{divisibility}\:{of}\:\mathrm{3}. \\ $$$${It}'{s}\:{only}\:{fixation}\:{of}\:{one}\:{digit}\:{which} \\ $$$${makes}\:{the}\:{number}\:{divisible}\:{by}\:\mathrm{3}. \\ $$$${So}\:{upto}\:{abc}\:{we}\:{should}\:{consider}\:{only}\:{one} \\ $$$${condition}\:{that}\:{is}\:{a}\leqslant{b}\leqslant{c}. \\ $$$${The}\:{fourth}\:{digit}\:\left({unit}\right)\:{d}\:{may}\:{be}\:{fixed} \\ $$$${in}\:{such}\:{a}\:{way}\:{that}\:{it}\:{makes}\:{the}\:{number} \\ $$$${multiple}\:{of}\:\:\mathrm{3}\:{along}\:{with}\:{d}\geqslant{c}. \\ $$$${Particularily}\:{if}\:{a}_{\mathrm{0}} {b}_{\mathrm{0}} {c}_{\mathrm{0}\:} {is}\:{any}\:{of}\:{such} \\ $$$${permutations}\:{and}\:{d}\:{is}\:{unit}\:{digit}\:{then} \\ $$$${for}\:\mathrm{3}{m}>{a}_{\mathrm{0}} +{b}_{\mathrm{0}} +{c}_{\mathrm{0}} \:\&\mathrm{1}\leqslant\mathrm{3}{m}−\left({a}_{\mathrm{0}} +{b}_{\mathrm{0}} +{c}_{\mathrm{0}} \:\right)\leqslant\mathrm{9}: \\ $$$$\:\:\:\:\:\:\:\:\:{d}\geqslant{c}\:\:\:\wedge\:\:{d}=\mathrm{3}{m}−\left({a}_{\mathrm{0}} +{b}_{\mathrm{0}} +{c}_{\mathrm{0}} \:\right) \\ $$$$ \\ $$$${For}\:{example}\:{if}\:{abc}=\mathrm{112} \\ $$$${According}\:{to}\:{the}\:{condition}\:{d}\geqslant{c}\:,\:{the} \\ $$$${candidates}\:{for}\:{d}\:{are}\:\mathrm{2},\mathrm{3},\mathrm{4},...,\mathrm{9}\:{but} \\ $$$${only}\:\mathrm{2},\mathrm{5}\:\&\:\mathrm{8}\:{are}\:{such}\:{which}\:{make} \\ $$$${the}\:{number}\:{divisible}\:{by}\:\mathrm{3}.\:{So}\:{three} \\ $$$${numbers}\:\left(\mathrm{1122},\mathrm{1125}\:\&\:\mathrm{1128}\right)\:{can}\:{be}\: \\ $$$${made}\:{from}\:\mathrm{112} \\ $$$${The}\:{limitation}\:{of}\:{the}\:{process}\:{is}\:{this} \\ $$$${that}\:{we}\:{have}\:{to}\:{compose}\:{all}\:{the}\:{three} \\ $$$${digit}\:{numbers}\:{abc}\:{with}\:{condition} \\ $$$${a}\leqslant{b}\leqslant{c}\: \\ $$$${So}\:{this}\:{is}\:{not}\:{a}\:{good}\:{method}\:{to}\:{determine} \\ $$$${number}\:{of}\:{the}\:{required}\:{numbers}. \\ $$$${However}\:{it}\:{may}\:{be}\:{used}\:{to}\:{construct} \\ $$$${numbers}\:{under}\:{the}\:{given}\:{conditions} \\ $$

Answered by Rasheed.Sindhi last updated on 04/May/19

Case-1: When a+b+c+d=3 No possibility because 1111 is the smallest number under condition a≤b≤c≤d Case-2: When a+b+c+d=6 Case-3: When a+b+c+d=9 Case-12: When a+b+c+d=36 ........ .......

$${Case}-\mathrm{1}:\:{When}\:{a}+{b}+{c}+{d}=\mathrm{3} \\ $$$${No}\:{possibility}\:{because}\:\mathrm{1111}\:{is}\:{the} \\ $$$${smallest}\:{number}\:{under}\:{condition} \\ $$$${a}\leqslant{b}\leqslant{c}\leqslant{d} \\ $$$$ \\ $$$${Case}-\mathrm{2}:\:{When}\:{a}+{b}+{c}+{d}=\mathrm{6} \\ $$$$ \\ $$$${Case}-\mathrm{3}:\:{When}\:{a}+{b}+{c}+{d}=\mathrm{9} \\ $$$$ \\ $$$${Case}-\mathrm{12}:\:{When}\:{a}+{b}+{c}+{d}=\mathrm{36} \\ $$$$\:\:\:........ \\ $$$$\:\:\:\:....... \\ $$$$ \\ $$

Commented by mr W last updated on 03/May/19

thank you Rasheed sir for sharing your thoughts!

$${thank}\:{you}\:{Rasheed}\:{sir}\:{for}\:{sharing} \\ $$$${your}\:{thoughts}! \\ $$

Commented by mr W last updated on 03/May/19

the question is indeed to find how many solutions we have for the equation a+b+c+d=3k with k=2...12 and 1≤a≤b≤c≤d≤9

$${the}\:{question}\:{is}\:{indeed}\:{to}\:{find}\:{how} \\ $$$${many}\:{solutions}\:{we}\:{have}\:{for}\:{the} \\ $$$${equation} \\ $$$${a}+{b}+{c}+{d}=\mathrm{3}{k}\:{with}\:{k}=\mathrm{2}...\mathrm{12}\:{and} \\ $$$$\mathrm{1}\leqslant{a}\leqslant{b}\leqslant{c}\leqslant{d}\leqslant\mathrm{9} \\ $$

Commented by Rasheed.Sindhi last updated on 03/May/19

The problem goes to “number of partitions” under some conditions. For example: In how many ways 6 can be partitioned in four parts a,b,c,d such that 1≤a,b,c,d≤9 & a≤b≤c≤d

$${The}\:{problem}\:{goes}\:{to}\:``{number}\:{of} \\ $$$${partitions}''\:{under}\:{some}\:{conditions}. \\ $$$${For}\:{example}:\:{In}\:{how}\:{many}\:{ways} \\ $$$$\mathrm{6}\:{can}\:{be}\:{partitioned}\:{in}\:{four}\:{parts} \\ $$$${a},{b},{c},{d}\:{such}\:{that} \\ $$$$\:\:\:\:\:\:\mathrm{1}\leqslant{a},{b},{c},{d}\leqslant\mathrm{9}\:\&\:{a}\leqslant{b}\leqslant{c}\leqslant{d} \\ $$

Commented by Rasheed.Sindhi last updated on 04/May/19

Sir I want to do the same.I thought that if we be able to determine the number of partitions of an integer n (in this case n=6,9,...36) in k parts (in our case k=4) we can solve our problem.

$${Sir}\:{I}\:{want}\:{to}\:{do}\:{the}\:{same}.{I}\:{thought} \\ $$$${that}\:{if}\:{we}\:{be}\:{able}\:{to}\:{determine}\:{the} \\ $$$${number}\:{of}\:{partitions}\:{of}\:{an}\:{integer}\:{n} \\ $$$$\left({in}\:{this}\:{case}\:\:{n}=\mathrm{6},\mathrm{9},...\mathrm{36}\right)\:{in}\:{k}\:{parts} \\ $$$$\left({in}\:{our}\:{case}\:{k}=\mathrm{4}\right)\:{we}\:{can}\:{solve}\:{our} \\ $$$${problem}. \\ $$

Terms of Service

Privacy Policy

Contact: info@tinkutara.com