Menu Close

How-many-numbers-in-the-range-1-10-n-1-are-divisible-by-9-digit-repetitions-are-not-allowed-

Tinku Tara 0 Comments
Pin




Question Number 118043 by prakash jain last updated on 14/Oct/20
How many numbers in the range [1,10^n −1] are divisible by 9? digit repetitions are not allowed.
$$\mathrm{How}\:\mathrm{many}\:\mathrm{numbers}\:\mathrm{in}\:\mathrm{the}\:\mathrm{range} \\ $$$$\left[\mathrm{1},\mathrm{10}^{{n}} −\mathrm{1}\right]\:\mathrm{are}\:\mathrm{divisible}\:\mathrm{by}\:\mathrm{9}? \\ $$$$\mathrm{digit}\:\mathrm{repetitions}\:\mathrm{are}\:\mathrm{not}\:\mathrm{allowed}. \\ $$
Commented by mr W last updated on 15/Oct/20
without repetition means max. 10 digits are allowed, i.e. n≤10. 10 digit numbers: 0+1+2+..+9=45 ✓ ⇒(9/(10))×10!=9×9! 9 digit numbers: 1+2+..+9=45 ✓ ⇒9! 0+1+2+..+8=36 ✓ ⇒(8/9)×9!=8×8! ⇒9!+8×8!=17×8! 8 digit numbers: without 0+9 ⇒8! without 1+8,2+7,3+6,4+5 ⇒4×(7/8)×8!=4×7×7! ⇒8!+4×7×7!=36×7! 7 digit numbers: without 0+1+8,0+2+7,0+3+6,0+4+5 ⇒4×7! without 1+8+9,2+7+9,3+6+9,4+5+9 ⇒4×(6/7)×7!=4×6×6! without 1+2+6,1+3+5 ⇒2×(6/7)×7!=2×6×6! without 2+3+4 ⇒(6/7)×7!=6×6! ⇒(4×7+4×6+2×6+6)6!=10×7! 6 digit numbers: without 0+1+2+6,0+1+3+5,0+2+3+4 ⇒3×6! without 1+2+6+8,1+3+5+9,2+3+4+9 ⇒3×(5/6)×6!=3×5×5! ⇒3(6+5)5!=33×5! 5 digit numbers: 9+8+7+2+1 9+8+6+3+1 9+8+5+4+1 9+8+5+3+2 9+7+6+4+1 9+7+6+3+2 9+7+5+4+2 9+6+5+4+3 ......
$${without}\:{repetition}\:{means}\:{max}. \\ $$$$\mathrm{10}\:{digits}\:{are}\:{allowed},\:{i}.{e}.\:{n}\leqslant\mathrm{10}. \\ $$$$ \\ $$$$\mathrm{10}\:{digit}\:{numbers}: \\ $$$$\mathrm{0}+\mathrm{1}+\mathrm{2}+..+\mathrm{9}=\mathrm{45}\:\checkmark \\ $$$$\Rightarrow\frac{\mathrm{9}}{\mathrm{10}}×\mathrm{10}!=\mathrm{9}×\mathrm{9}! \\ $$$$ \\ $$$$\mathrm{9}\:{digit}\:{numbers}: \\ $$$$\mathrm{1}+\mathrm{2}+..+\mathrm{9}=\mathrm{45}\:\checkmark \\ $$$$\Rightarrow\mathrm{9}! \\ $$$$\mathrm{0}+\mathrm{1}+\mathrm{2}+..+\mathrm{8}=\mathrm{36}\:\checkmark \\ $$$$\Rightarrow\frac{\mathrm{8}}{\mathrm{9}}×\mathrm{9}!=\mathrm{8}×\mathrm{8}! \\ $$$$\Rightarrow\mathrm{9}!+\mathrm{8}×\mathrm{8}!=\mathrm{17}×\mathrm{8}! \\ $$$$ \\ $$$$\mathrm{8}\:{digit}\:{numbers}: \\ $$$${without}\:\mathrm{0}+\mathrm{9}\:\Rightarrow\mathrm{8}! \\ $$$${without}\:\mathrm{1}+\mathrm{8},\mathrm{2}+\mathrm{7},\mathrm{3}+\mathrm{6},\mathrm{4}+\mathrm{5}\:\Rightarrow\mathrm{4}×\frac{\mathrm{7}}{\mathrm{8}}×\mathrm{8}!=\mathrm{4}×\mathrm{7}×\mathrm{7}! \\ $$$$\Rightarrow\mathrm{8}!+\mathrm{4}×\mathrm{7}×\mathrm{7}!=\mathrm{36}×\mathrm{7}! \\ $$$$ \\ $$$$\mathrm{7}\:{digit}\:{numbers}: \\ $$$${without}\:\mathrm{0}+\mathrm{1}+\mathrm{8},\mathrm{0}+\mathrm{2}+\mathrm{7},\mathrm{0}+\mathrm{3}+\mathrm{6},\mathrm{0}+\mathrm{4}+\mathrm{5}\:\Rightarrow\mathrm{4}×\mathrm{7}! \\ $$$${without}\:\mathrm{1}+\mathrm{8}+\mathrm{9},\mathrm{2}+\mathrm{7}+\mathrm{9},\mathrm{3}+\mathrm{6}+\mathrm{9},\mathrm{4}+\mathrm{5}+\mathrm{9}\:\Rightarrow\mathrm{4}×\frac{\mathrm{6}}{\mathrm{7}}×\mathrm{7}!=\mathrm{4}×\mathrm{6}×\mathrm{6}! \\ $$$${without}\:\mathrm{1}+\mathrm{2}+\mathrm{6},\mathrm{1}+\mathrm{3}+\mathrm{5}\:\Rightarrow\mathrm{2}×\frac{\mathrm{6}}{\mathrm{7}}×\mathrm{7}!=\mathrm{2}×\mathrm{6}×\mathrm{6}! \\ $$$${without}\:\mathrm{2}+\mathrm{3}+\mathrm{4}\:\Rightarrow\frac{\mathrm{6}}{\mathrm{7}}×\mathrm{7}!=\mathrm{6}×\mathrm{6}! \\ $$$$\Rightarrow\left(\mathrm{4}×\mathrm{7}+\mathrm{4}×\mathrm{6}+\mathrm{2}×\mathrm{6}+\mathrm{6}\right)\mathrm{6}!=\mathrm{10}×\mathrm{7}! \\ $$$$ \\ $$$$\mathrm{6}\:{digit}\:{numbers}: \\ $$$${without}\:\mathrm{0}+\mathrm{1}+\mathrm{2}+\mathrm{6},\mathrm{0}+\mathrm{1}+\mathrm{3}+\mathrm{5},\mathrm{0}+\mathrm{2}+\mathrm{3}+\mathrm{4}\:\Rightarrow\mathrm{3}×\mathrm{6}! \\ $$$${without}\:\mathrm{1}+\mathrm{2}+\mathrm{6}+\mathrm{8},\mathrm{1}+\mathrm{3}+\mathrm{5}+\mathrm{9},\mathrm{2}+\mathrm{3}+\mathrm{4}+\mathrm{9}\:\Rightarrow\mathrm{3}×\frac{\mathrm{5}}{\mathrm{6}}×\mathrm{6}!=\mathrm{3}×\mathrm{5}×\mathrm{5}! \\ $$$$\Rightarrow\mathrm{3}\left(\mathrm{6}+\mathrm{5}\right)\mathrm{5}!=\mathrm{33}×\mathrm{5}! \\ $$$$ \\ $$$$\mathrm{5}\:{digit}\:{numbers}: \\ $$$$\mathrm{9}+\mathrm{8}+\mathrm{7}+\mathrm{2}+\mathrm{1} \\ $$$$\mathrm{9}+\mathrm{8}+\mathrm{6}+\mathrm{3}+\mathrm{1} \\ $$$$\mathrm{9}+\mathrm{8}+\mathrm{5}+\mathrm{4}+\mathrm{1} \\ $$$$\mathrm{9}+\mathrm{8}+\mathrm{5}+\mathrm{3}+\mathrm{2} \\ $$$$\mathrm{9}+\mathrm{7}+\mathrm{6}+\mathrm{4}+\mathrm{1} \\ $$$$\mathrm{9}+\mathrm{7}+\mathrm{6}+\mathrm{3}+\mathrm{2} \\ $$$$\mathrm{9}+\mathrm{7}+\mathrm{5}+\mathrm{4}+\mathrm{2} \\ $$$$\mathrm{9}+\mathrm{6}+\mathrm{5}+\mathrm{4}+\mathrm{3} \\ $$$$ \\ $$$$…… \\ $$
Commented by prakash jain last updated on 15/Oct/20
Thanks sir. It looks listing is the only possible way. I thought I had seen a closed forum expression somewhere but was not able to derive.
$$\mathrm{Thanks}\:\mathrm{sir}. \\ $$$$\mathrm{It}\:\mathrm{looks}\:\mathrm{listing}\:\mathrm{is}\:\mathrm{the}\:\mathrm{only}\:\mathrm{possible}\:\mathrm{way}. \\ $$$$\mathrm{I}\:\mathrm{thought}\:\mathrm{I}\:\mathrm{had}\:\mathrm{seen}\:\mathrm{a}\:\mathrm{closed}\:\mathrm{forum} \\ $$$$\mathrm{expression}\:\mathrm{somewhere}\:\mathrm{but}\:\mathrm{was}\:\mathrm{not} \\ $$$$\mathrm{able}\:\mathrm{to}\:\mathrm{derive}. \\ $$
Answered by floor(10²Eta[1]) last updated on 24/Dec/20
from 1 to 10^n −1 we have ((10^n −1)/9) multiples of 9 (considering the numbers with the same digits) so let′s calculate how many numbers have the same digits and are divisible by 9 [aa...a] (n digits) a.n≡0(mod9), a∈[1,9] ∧ n≥2 a∈{1, 2, 4, 5, 7, 8}⇒n=9k, k≥1 a∈{3, 6}⇒n=3k, k≥1 a=9⇒n=k≥2 2 digits: (99) 3 digits: (333, 666, 999) 4 digits: (9999) 5 digits: (99999) 6 digits: (333333, 666666, 999999) [...] 9 digits: (11...1, 22...2, 33...3, ..., 99..9) 2 digits to 9 digits: 5+3.2+9=20 cases 10 digits to 19: 7+3.2+9=22 cases from 1 to x we have x−⌊(x/3)⌋numbers that are coprime with 3 (because ⌊(x/3)⌋ is the number of multiples of 3, from 1 to x) from 2 to x we have (x−⌊(x/3)⌋−1)+3(⌊(x/3)⌋−⌊(x/9)⌋)+9⌊(x/9)⌋ x−1+2⌊(x/3)⌋+6⌊(x/9)⌋numbers that are divisible by 9 and have the same digits from 2 digits to n digits we have n−1+2⌊(n/3)⌋+6⌊(n/9)⌋ numbers that have the same digits and are divisible by 9 Ans: ((10^n −1)/9)−(n−1+2⌊(n/3)⌋+6⌊(n/9)⌋)
$$\mathrm{from}\:\mathrm{1}\:\mathrm{to}\:\mathrm{10}^{\mathrm{n}} −\mathrm{1}\:\mathrm{we}\:\mathrm{have}\:\frac{\mathrm{10}^{\mathrm{n}} −\mathrm{1}}{\mathrm{9}}\:\mathrm{multiples}\:\mathrm{of}\:\mathrm{9} \\ $$$$\left(\mathrm{considering}\:\mathrm{the}\:\mathrm{numbers}\:\mathrm{with}\:\mathrm{the}\:\mathrm{same}\:\mathrm{digits}\right) \\ $$$$\mathrm{so}\:\mathrm{let}'\mathrm{s}\:\mathrm{calculate}\:\mathrm{how}\:\mathrm{many}\:\mathrm{numbers}\:\mathrm{have}\: \\ $$$$\mathrm{the}\:\mathrm{same}\:\mathrm{digits}\:\mathrm{and}\:\mathrm{are}\:\mathrm{divisible}\:\mathrm{by}\:\mathrm{9} \\ $$$$\left[\mathrm{aa}…\mathrm{a}\right]\:\left(\mathrm{n}\:\mathrm{digits}\right) \\ $$$$\mathrm{a}.\mathrm{n}\equiv\mathrm{0}\left(\mathrm{mod9}\right),\:\mathrm{a}\in\left[\mathrm{1},\mathrm{9}\right]\:\wedge\:\mathrm{n}\geqslant\mathrm{2} \\ $$$$\mathrm{a}\in\left\{\mathrm{1},\:\mathrm{2},\:\mathrm{4},\:\mathrm{5},\:\mathrm{7},\:\mathrm{8}\right\}\Rightarrow\mathrm{n}=\mathrm{9k},\:\mathrm{k}\geqslant\mathrm{1} \\ $$$$\mathrm{a}\in\left\{\mathrm{3},\:\mathrm{6}\right\}\Rightarrow\mathrm{n}=\mathrm{3k},\:\mathrm{k}\geqslant\mathrm{1} \\ $$$$\mathrm{a}=\mathrm{9}\Rightarrow\mathrm{n}=\mathrm{k}\geqslant\mathrm{2} \\ $$$$\mathrm{2}\:\mathrm{digits}:\:\left(\mathrm{99}\right) \\ $$$$\mathrm{3}\:\mathrm{digits}:\:\left(\mathrm{333},\:\mathrm{666},\:\mathrm{999}\right) \\ $$$$\mathrm{4}\:\mathrm{digits}:\:\left(\mathrm{9999}\right) \\ $$$$\mathrm{5}\:\mathrm{digits}:\:\left(\mathrm{99999}\right) \\ $$$$\mathrm{6}\:\mathrm{digits}:\:\left(\mathrm{333333},\:\mathrm{666666},\:\mathrm{999999}\right) \\ $$$$\left[…\right] \\ $$$$\mathrm{9}\:\mathrm{digits}:\:\left(\mathrm{11}…\mathrm{1},\:\mathrm{22}…\mathrm{2},\:\mathrm{33}…\mathrm{3},\:…,\:\mathrm{99}..\mathrm{9}\right) \\ $$$$\mathrm{2}\:\mathrm{digits}\:\mathrm{to}\:\mathrm{9}\:\mathrm{digits}:\:\mathrm{5}+\mathrm{3}.\mathrm{2}+\mathrm{9}=\mathrm{20}\:\mathrm{cases} \\ $$$$\mathrm{10}\:\mathrm{digits}\:\mathrm{to}\:\mathrm{19}:\:\mathrm{7}+\mathrm{3}.\mathrm{2}+\mathrm{9}=\mathrm{22}\:\mathrm{cases} \\ $$$$\mathrm{from}\:\mathrm{1}\:\mathrm{to}\:\mathrm{x}\:\mathrm{we}\:\mathrm{have} \\ $$$$\mathrm{x}−\lfloor\frac{\mathrm{x}}{\mathrm{3}}\rfloor\mathrm{numbers}\:\mathrm{that}\:\mathrm{are}\:\mathrm{coprime}\:\mathrm{with}\:\mathrm{3} \\ $$$$\left(\mathrm{because}\:\lfloor\frac{\mathrm{x}}{\mathrm{3}}\rfloor\:\mathrm{is}\:\mathrm{the}\:\mathrm{number}\:\mathrm{of}\:\mathrm{multiples}\:\mathrm{of}\:\mathrm{3},\:\mathrm{from}\:\mathrm{1}\:\mathrm{to}\:\mathrm{x}\right) \\ $$$$\mathrm{from}\:\mathrm{2}\:\mathrm{to}\:\mathrm{x}\:\mathrm{we}\:\mathrm{have} \\ $$$$\left(\mathrm{x}−\lfloor\frac{\mathrm{x}}{\mathrm{3}}\rfloor−\mathrm{1}\right)+\mathrm{3}\left(\lfloor\frac{\mathrm{x}}{\mathrm{3}}\rfloor−\lfloor\frac{\mathrm{x}}{\mathrm{9}}\rfloor\right)+\mathrm{9}\lfloor\frac{\mathrm{x}}{\mathrm{9}}\rfloor \\ $$$$\mathrm{x}−\mathrm{1}+\mathrm{2}\lfloor\frac{\mathrm{x}}{\mathrm{3}}\rfloor+\mathrm{6}\lfloor\frac{\mathrm{x}}{\mathrm{9}}\rfloor\mathrm{numbers}\:\mathrm{that}\:\mathrm{are}\:\mathrm{divisible} \\ $$$$\mathrm{by}\:\mathrm{9}\:\mathrm{and}\:\mathrm{have}\:\mathrm{the}\:\mathrm{same}\:\mathrm{digits} \\ $$$$\mathrm{from}\:\mathrm{2}\:\mathrm{digits}\:\mathrm{to}\:\mathrm{n}\:\mathrm{digits}\:\mathrm{we}\:\mathrm{have} \\ $$$$\mathrm{n}−\mathrm{1}+\mathrm{2}\lfloor\frac{\mathrm{n}}{\mathrm{3}}\rfloor+\mathrm{6}\lfloor\frac{\mathrm{n}}{\mathrm{9}}\rfloor\:\mathrm{numbers}\:\mathrm{that}\:\mathrm{have} \\ $$$$\mathrm{the}\:\mathrm{same}\:\mathrm{digits}\:\mathrm{and}\:\mathrm{are}\:\mathrm{divisible}\:\mathrm{by}\:\mathrm{9} \\ $$$$ \\ $$$$\mathrm{Ans}: \\ $$$$\frac{\mathrm{10}^{\mathrm{n}} −\mathrm{1}}{\mathrm{9}}−\left(\mathrm{n}−\mathrm{1}+\mathrm{2}\lfloor\frac{\mathrm{n}}{\mathrm{3}}\rfloor+\mathrm{6}\lfloor\frac{\mathrm{n}}{\mathrm{9}}\rfloor\right) \\ $$$$ \\ $$

Pin

Leave a Reply

Your email address will not be published. Required fields are marked *