My Math Forum One problem in combinatorics

 Elementary Math Fractions, Percentages, Word Problems, Equations, Inequations, Factorization, Expansion

April 5th, 2018, 01:14 PM   #1
Member

Joined: Jan 2018

Posts: 46
Thanks: 2

One problem in combinatorics

Quote:
 How many 2008-digit numbers, such that no single digit is 3 and number is divisible by 3, are there?
I know thet number is divisible by 3 if the sum of its digits is divisible by 3, but have no idea what to do next.

April 5th, 2018, 03:14 PM   #2
Math Team

Joined: Oct 2011

Posts: 12,760
Thanks: 860

Quote:
 Originally Posted by lua 2008-digit numbers
WHAT does that mean?

April 5th, 2018, 03:30 PM   #3
Senior Member

Joined: Sep 2015
From: USA

Posts: 2,009
Thanks: 1042

Quote:
 Originally Posted by Denis WHAT does that mean?
a number that is 2008 digits long... seems pretty clear

The answer to this question is, for an $n$ digit number there are

$N_n = 3^{2n-1}$

numbers satisfying the two constraints.

so

$N_{2008} = 3^{4015} \approx 4.383668447186213\times 10^{1915}$

I'm still trying to figure out how to show it.

April 5th, 2018, 08:50 PM   #4
Member

Joined: Jan 2018

Posts: 46
Thanks: 2

Quote:
 Originally Posted by romsek a number that is 2008 digits long... seems pretty clear
Yes, that's it. Sorry if my english isn't clear enough.

 April 5th, 2018, 09:43 PM #5 Member   Joined: Jan 2018 From: Belgrade Posts: 46 Thanks: 2 I came up with an idea. If I choose (fix) first 2007 digits, i must choose 2008th digit so to satisfy the condition that the sum of digits is divisible with 3. So, in how many ways can I choose first 2007 digits? I can choose first digit in 8 ways (it can't be 0 or 3). Every other digit from 2nd to 2007th I can choose in 9 ways (it can't be 3). So number of ways to fix first 2007 digits is: $\displaystyle 8 \cdot 9 \cdot ... \cdot 9 = 8 \cdot 9^{2006}$ But how many ways can I choose last digit?
 April 6th, 2018, 01:50 AM #6 Member   Joined: Jan 2018 From: Belgrade Posts: 46 Thanks: 2 I think I found the solution. Whatever the sum of the first 2007 digits is, it can be represented as one of the following: $\displaystyle 3 \cdot k -2$, $\displaystyle 3 \cdot k -1$ or $\displaystyle 3 \cdot k$, where $\displaystyle k$ is natural number. In the first case, the sum od all digits to be divisible by 3, we add 2 for 2008th digit. Similarly, in the second case, 2008th digit is 1, and in the third case, 2008th digit is 0. So, the 2008th digit can be chosen in three ways. Now, there are $\displaystyle 3 \cdot 8 \cdot 9^{2006}$ numbers which satisfy constranints given in the problem.
April 6th, 2018, 10:13 AM   #7
Senior Member

Joined: Sep 2015
From: USA

Posts: 2,009
Thanks: 1042

Quote:
 Originally Posted by lua I think I found the solution. Whatever the sum of the first 2007 digits is, it can be represented as one of the following: $\displaystyle 3 \cdot k -2$, $\displaystyle 3 \cdot k -1$ or $\displaystyle 3 \cdot k$, where $\displaystyle k$ is natural number. In the first case, the sum od all digits to be divisible by 3, we add 2 for 2008th digit. Similarly, in the second case, 2008th digit is 1, and in the third case, 2008th digit is 0. So, the 2008th digit can be chosen in three ways. Now, there are $\displaystyle 3 \cdot 8 \cdot 9^{2006}$ numbers which satisfy constranints given in the problem.
you're ignoring the fact that none of the number are allowed to have 3 appearing as a digit.

I highly recommend you work this out for a shorter length number, say 3 or 4 digits, and then apply that result to the general $n$ length number.

I'm pretty confident in the result of post 3.

 April 6th, 2018, 12:09 PM #8 Member   Joined: Jan 2018 From: Belgrade Posts: 46 Thanks: 2 So, we have two formulas. First formula claims that there are $\displaystyle N_{n}=3^{2n-1}$ such numbers. Second formula claims that there are $\displaystyle N_{n}=3 \cdot 8 \cdot 9^{n-2}$ such numbers. For $\displaystyle n=2$, all numbers are given down: $\displaystyle \begin{matrix} 12 \ 21 \ 42 \ 51 \ 60 \ 72 \ 81 \ 90\\ 15 \ 24 \ 45 \ 54 \ 66 \ 75 \ 84 \ 96\\ 18 \ 27 \ 48 \ 57 \ 69 \ 78 \ 87 \ 99 \end{matrix}$ So, there are 24 such 2-digits numbers. First formula claims that there are $\displaystyle N_{n}=3^{2 \cdot 2-1}=3^{3}=27$ such 2-digits numbers. Second formula claims that there are $\displaystyle N_{n}=3 \cdot 8 \cdot 9^{2-2}=3 \cdot 8 \cdot 1=24$ such 2-digits numbers. Having this in mind, I think second formula is OK, but the way to it is false. Namely, whatever sum of the previous digits is, I have 3 ways for last digit. If the sum of the previous digits is in the form of $\displaystyle 3k-2$, I have 3 potential numbers for the last digit: 2, 5 or 8. When the sum of the previous digits is in the form of $\displaystyle 3k-1$, that are digits 1, 4 or 7. And, if the sum of the previous digits is in the form of $\displaystyle 3k$, these digits are: 0, 6 or 9. That is why in any case I can choose last digit in 3 ways. Last edited by lua; April 6th, 2018 at 12:49 PM. Reason: Correcting the proof

 Tags combinatorics, problem

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post oldatlantian Number Theory 5 May 10th, 2015 12:02 AM Jakarta Algebra 12 February 6th, 2013 05:50 PM Jakarta Algebra 4 May 4th, 2012 11:35 AM midin Algebra 4 December 13th, 2010 03:48 PM mtdim Applied Math 1 May 2nd, 2010 04:33 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top