My Math Forum  

Go Back   My Math Forum > High School Math Forum > Elementary Math

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


Thanks Tree1Thanks
  • 1 Post By romsek
Reply
 
LinkBack Thread Tools Display Modes
April 5th, 2018, 01:14 PM   #1
lua
Member
 
Joined: Jan 2018
From: Belgrade

Posts: 50
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.
lua is offline  
 
April 5th, 2018, 03:14 PM   #2
Math Team
 
Joined: Oct 2011
From: Ottawa Ontario, Canada

Posts: 13,110
Thanks: 910

Quote:
Originally Posted by lua View Post
2008-digit numbers
WHAT does that mean?
Denis is offline  
April 5th, 2018, 03:30 PM   #3
Senior Member
 
romsek's Avatar
 
Joined: Sep 2015
From: USA

Posts: 2,091
Thanks: 1087

Quote:
Originally Posted by Denis View Post
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.
Thanks from Denis
romsek is offline  
April 5th, 2018, 08:50 PM   #4
lua
Member
 
Joined: Jan 2018
From: Belgrade

Posts: 50
Thanks: 2

Quote:
Originally Posted by romsek View Post
a number that is 2008 digits long... seems pretty clear
Yes, that's it. Sorry if my english isn't clear enough.
lua is offline  
April 5th, 2018, 09:43 PM   #5
lua
Member
 
Joined: Jan 2018
From: Belgrade

Posts: 50
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?
lua is offline  
April 6th, 2018, 01:50 AM   #6
lua
Member
 
Joined: Jan 2018
From: Belgrade

Posts: 50
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.
lua is offline  
April 6th, 2018, 10:13 AM   #7
Senior Member
 
romsek's Avatar
 
Joined: Sep 2015
From: USA

Posts: 2,091
Thanks: 1087

Quote:
Originally Posted by lua View Post
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.
romsek is offline  
April 6th, 2018, 12:09 PM   #8
lua
Member
 
Joined: Jan 2018
From: Belgrade

Posts: 50
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
lua is offline  
Reply

  My Math Forum > High School Math Forum > Elementary Math

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





Copyright © 2018 My Math Forum. All rights reserved.