7
$\begingroup$

Given $N \le 10^9$, determine how many numbers of length $N$ are possible with the following constraint: the adjacent digits of the number should have an absolute difference of $1$.

For eg, for $N = 3$, numbers starting with $1$ are $101,121,123$. For $N =4$, numbers starting with $1$ are $1210,1212,1232,1234$.

My approach to this problem is: first digit could be anything from $1$ to $9$. The second digit could be firstDigit$+1$ or firstDigit $-1$. And so on, if we do, we get the total number of possible numbers are $9\cdot2^{N-1}$. But the catch is, we must subtract those numbers with digit less that $0$ or greater than $9$.

I am stuck here. How to get a formula to subtract these numbers from the total. Or is there a better approach to solve this problem?

$\endgroup$
  • $\begingroup$ would be better if the downvoters could give a reason for. $\endgroup$ – Laura Smith Sep 27 '15 at 8:04
7
$\begingroup$

I try a different approach: I write a $10 \times 10$ transition matrix (one dimension per digit, like a markov chain, but this time it is not about the probabilities, but about counting the number of possibilities) where each entry $a_{ij}$ says whether we can go from digit $j$ to digit $i$. Lets say that the top left entry has indices $(0,0)$ just for this example (I know this is not usually done like this) This matrix looks as follows:

$A= \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{pmatrix}$

If we want to know what the next digit could be if we are at $n=4$ we just multiply the matrix $A$ with the vector $e_4 = (0,0,0,0,1,0,0,0,0,0)^t$ (the one is in the fourth position when beginning counting at 0. Then we get the vector $$Ae_4 = (0,0,0,1,0,1,0,0,0,0)^t$$.

After two steps (so for the third digit) we get the following vector:

$$A^2e_4 = (0,0,1,0,2,0,1,0,0,0)^t$$

and so forth. So the $n$th entry of this vector says how many numbers have the digit $n$ as their third digit (=after two steps).

So the total of the new possibilities of those numbers is just the sum of the entries of the new vector. This is if we just take only one step (transition from one to the next digit). So when we want to get the possibilities of the next step, we just have to multiply with $A$ one more time.

As we want all combinations with all starting numbers we have to use the starting vector $v=(0,1,1,1,1,1,1,1,1,1)^t$ (since we cannot start with the digit 0 as @Mathmo123 mentioned (Thanks!))

In total we have $N-1$ transitions, so $v$ needs to be multiplied by $A^{N-1}$. For $N=9$ get:

$$A^8 v = (56,126,153,208,208,228,201,181,125,70)^t$$

Which makes a total of 1556. Or for $N=3$ we get

$$A^2 v = (1,3,3,4,4,4,4,4,3,2)$$

which makes a total of $32$.

Edit

If you want the total of all combinations from $N=1,...,10^9$ we can make use of the geometric series.

We want to sum up all the solutions from all those $N$, then we get (let m=10^9$ be the maximal exponent):

$Iv+Av+A^2v+A^3v+...+A^mv = (I+A+A^2+A^3+...+A^m )v = (I-A)^{-1}(I-A^{m+1}) v$

Of course here we still need a fair amount of matrix multiplication, especially for calculating $A^{m+1}$.

Appendix

PS: Of course I did not calculate this by hand, I just quickly did it in Octave/Matlab:

a=diag(ones(9,1),-1);
a=a+a'; %now we have our finished matrix a
e4 = [0,0,0,0,1,0,0,0,0,0]'; 
%the two explaining examples
disp(a*e4);   
disp(a^2*e4);
%our resulting vector:
 v = ones(10,1);
v(1)=0;
disp(a^8 * v);
%the total for N=9
disp( sum(a^8 * v));
$\endgroup$
  • $\begingroup$ @Mathmo123 Thank you very much for pointing this out, I now corrected my answer! $\endgroup$ – flawr Sep 26 '15 at 20:52
  • $\begingroup$ Thanks guys. Could there be a possible one liner instead of matrix multiplication? $\endgroup$ – Laura Smith Sep 26 '15 at 21:03
  • $\begingroup$ I am sorry, I could not come up with another way, but I am sure there is another way! I just added a solution for summing up all the solutions. $\endgroup$ – flawr Sep 26 '15 at 21:26
  • $\begingroup$ I don't think there's a really easy formula. That matrix can be diagonalized so you can represent the solutions using eigenvalue powers, that would be a "closed formula", and it looks hairy. $\endgroup$ – gus Sep 26 '15 at 21:30
  • $\begingroup$ The matrix is the sum of a very simple upper triangular matrix and a very simple lower triangular matrix. It might be possible to develop an explicit formula. Don't try for an explicit formula for the matrix power itself, but for the solution vector, I would think. $\endgroup$ – saulspatz Sep 27 '15 at 0:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.