Number Theory Giveaway

Probability Level 3

How many 5-digit numbers are there such that every 2 neighbouring digits differ by 3?

45 48 46 43

Lil Phil by Lil Phil , 21, Antarctica

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Chris Lewis
Jul 3, 2019

The simplest option would be to write some code and check all 5 5 -digit numbers.

A slightly nicer approach is to see what happens when we vary the number of digits. Let's call these numbers 3 3 -diffs, and define f ( n , d ) f(n,d) to be the number of 3 3 -diffs with n n digits that end with the digit d d .

As an example, f ( 2 , 4 ) = 2 f(2,4)=2 - these are 14 14 and 74 74 .

We have f ( 1 , d ) = 1 f(1,d)=1 for d = 1 , … , 9 d=1,\ldots,9 . Because we don't want to allow numbers that start with 0 0 , it's helpful to define f ( 1 , 0 ) = 0 f(1,0)=0 .

We can then work out f ( n + 1 , d ) f(n+1,d) for each d d as follows:

f ( n + 1 , 0 ) = f ( n , 3 ) f ( n + 1 , 1 ) = f ( n , 4 ) f ( n + 1 , 2 ) = f ( n , 5 ) f ( n + 1 , 3 ) = f ( n , 0 ) + f ( n , 6 ) f ( n + 1 , 4 ) = f ( n , 1 ) + f ( n , 7 ) f ( n + 1 , 5 ) = f ( n , 2 ) + f ( n , 8 ) f ( n + 1 , 6 ) = f ( n , 3 ) + f ( n , 9 ) f ( n + 1 , 7 ) = f ( n , 4 ) f ( n + 1 , 8 ) = f ( n , 5 ) f ( n + 1 , 9 ) = f ( n , 6 ) \begin{aligned} f(n+1,0)&=f(n,3)\\ f(n+1,1)&=f(n,4)\\ f(n+1,2)&=f(n,5)\\ f(n+1,3)&=f(n,0)+f(n,6)\\ f(n+1,4)&=f(n,1)+f(n,7)\\ f(n+1,5)&=f(n,2)+f(n,8)\\ f(n+1,6)&=f(n,3)+f(n,9)\\ f(n+1,7)&=f(n,4)\\ f(n+1,8)&=f(n,5)\\ f(n+1,9)&=f(n,6)\\ \end{aligned}

(essentially we're counting how many 3 3 -diffs with n n digits we can add a d d onto - this is why we had to be careful with f ( 1 , 0 ) f(1,0) ). It's now easy to draw up a table of these f ( n , d ) f(n,d) values. The sum of these when n = 5 n=5 is 45 \boxed{45} .

There are various shortcuts and generalisations we can make about the function f f (for example, f ( n , 1 ) = f ( n , 2 ) = f ( n , 7 ) = f ( n , 8 ) f(n,1)=f(n,2)=f(n,7)=f(n,8) for all n n ); we could even explicitly solve for the function f f . But since we're only after 5 5 digits, a table seems a good enough approach.

I suspect there's a good combinatorial method; the problem also has some similarities with random walks.

0 Helpful 0 Interesting 0 Brilliant 0 Confused
Kyle T
Jul 3, 2019 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
<?php
$c = 0;
for($i=10000;$i<100000;$i++){
    $a = str_split($i);
    if(abs($a[0]-$a[1])==3 && abs($a[1]-$a[2])==3 && abs($a[2]-$a[3])==3 && abs($a[3]-$a[4])==3){
        echo $i.'<br>';
        $c++;
    }
}
echo 'answer: '.$c;

/*
14141
14147
14741
14747
25252
25258
25852
25858
30303
30363
30369
36303
36363
36369
36963
36969
41414
41474
47414
47474
52525
52585
58525
58585
63030
63036
63630
63636
63696
69630
69636
69696
74141
74147
74741
74747
85252
85258
85852
85858
96303
96363
96369
96963
96969
answer: 45
*/
?>

0 Helpful 0 Interesting 0 Brilliant 1 Confused

Its pretty ugly but here's a regex that you can use to test against all of the 5 digit numbers as well:
^(0(?=(3|$))|1(?=(4|$))|2(?=(5|$))|3(?=(0|6|$))|4(?=(1|7|$))|5(?=(2|8|$))|6(?=(3|9|$))|7(?=(4|$))|8(?=(5|$))|9(?=(6|$)))+$

Kyle T - 1 year, 11 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...