
Elementary Math Fractions, Percentages, Word Problems, Equations, Inequations, Factorization, Expansion 
 LinkBack  Thread Tools  Display Modes 
April 5th, 2018, 01:14 PM  #1  
Member Joined: Jan 2018 From: Belgrade Posts: 55 Thanks: 2  One problem in combinatorics Quote:
 
April 5th, 2018, 03:14 PM  #2 
Math Team Joined: Oct 2011 From: Ottawa Ontario, Canada Posts: 14,597 Thanks: 1038  
April 5th, 2018, 03:30 PM  #3 
Senior Member Joined: Sep 2015 From: USA Posts: 2,496 Thanks: 1371  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^{2n1}$ 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 From: Belgrade Posts: 55 Thanks: 2  
April 5th, 2018, 09:43 PM  #5 
Member Joined: Jan 2018 From: Belgrade Posts: 55 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: 55 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,496 Thanks: 1371  Quote:
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: 55 Thanks: 2 
So, we have two formulas. First formula claims that there are $\displaystyle N_{n}=3^{2n1}$ such numbers. Second formula claims that there are $\displaystyle N_{n}=3 \cdot 8 \cdot 9^{n2}$ 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 2digits numbers. First formula claims that there are $\displaystyle N_{n}=3^{2 \cdot 21}=3^{3}=27$ such 2digits numbers. Second formula claims that there are $\displaystyle N_{n}=3 \cdot 8 \cdot 9^{22}=3 \cdot 8 \cdot 1=24$ such 2digits 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 3k2$, 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 3k1$, 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  

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