I encountered the following problem for homework- An "oddie" is a 3 digit number with all 3 digits odd. How many "oddies" are divisible by 3?
There are 125 "oddies" and 300 3-digit numbers divisible by 3, but I still have no idea how to solve this. Please give me a hint or something to start me off with.
$\endgroup$3 Answers
$\begingroup$Hint: is there a way to check that a number is divisible by 3, based on its digits?
$\endgroup$ $\begingroup$Hint: Enumerate the 25 digit pairs that an oddie can start with: 11, 13, 15, …, 99, and group them into columns according to the sum of the two digits.
Each initial pair can be completed with a third digit in some number of ways; the number of ways depends only on which column the initial pair is in. Count the number of pairs in each column, and multiply by the number of possible completions for that column. Add up the result for each column.
I believe that this will take only a few minutes, since there are only 25 initial pairs.
$\endgroup$ $\begingroup$The number of numbers which have k digits ranges from $10^{k-1}$ to $10^k-1$. The divisibility through 3 is checked by taking the sum of the digits and checking that sum for divisibility through 3. $10^{k-1}$ has a digit sum of 1; $10^{k-1}+1$ has a digit sum of 2; so the first number in the interval divisible through 3 is $10^{k-1}+2$, and the last is (all-9's) $10^k-1$, and each 3rd is also divisble.
The number of numbers with all-odd digits (1, 3, 5, 7, or 9) in the interval$[10^{k-1},10^k-1]$ is $5^k$. (This is obvious, because we obtain all numbers in the interval with $k$ increasing by 1 by placing any of the 5 numbers 1, 3, 5,7 or 9 in front of the numbers of the previous interval.)
The following enumeration is recursive: To get the set of numbers for $k$ consider the numbers in the interval for $k-1$with all-odd digits. Denote by $D_{k,d}$ the number of odd numbers in the interval $[10^{k-1},10^k-1]$which have a remainder $\equiv d \pmod 3$, so $D_{1,0}=2$ from 3 and 9, $D_{1,1}=2$from 1 and 7, $D_{1,2}=1$ from 5. and $D_{k,0}+D_{k,1}+D_{k,2}=5^k$. Placing a 1 in front of a numbers moves the set of numbers in these remainder classes from $D_{k,0}$ to $D_{k+1,1}$, from $D_{k,1}$ to $D_{k+1,2}$and from $D_{k,2}$ to $D_{k+1,0}$. A similar argument holds for placing a 3, a 5, a 7 or a 9 in front of these numbers:$$ D_{k+1,0} = 2D_{k,0} + D_{k,1} + 2D_{k,2};$$$$ D_{k+1,1} = 2D_{k,0} + 2D_{k,1} + D_{k,2};$$$$ D_{k+1,2} = 1D_{k,0} + 2D_{k,1} + 2D_{k,2}.$$Solving this linear system of equations gives $D_{k,0} = 2,8,41,208,...$ with $3D_{k,0}=5^k+b(k)$, with $D_{k,0} = 6D_{k-1,0}-6D_{k-2,0}+5D_{k-3,0}$and $b(k)=1,-1,-2,-1,1,2,...$ ($k\ge 1$) is an auxiliary simple sequence with period length 6.
$\endgroup$
