### Author Topic: Math problem: odd digits and probability  (Read 2703 times)

0 Members and 1 Guest are viewing this topic.

#### Michael_Lee

• LV9 Veteran (Next: 1337)
• Posts: 1019
• Rating: +124/-9
##### Math problem: odd digits and probability
« on: November 11, 2011, 01:36:48 pm »
I was doing a problem for a math competition
Quote
How many five digit integers satisfy the following:
- All the digits are odd
- The difference between adjacent digits is 2
An example of such a number is 13535 or 57979
...and wanted to generalize it to "How many answers satisfy the conditions for n-digits"?

For example, given one digit, there are 5 possibilities {1, 3, 5, 7, 9}...
and given two digits, there are 8 possibilities {13, 31, 35, 53, 57, 75, 79, 97},
etc.

I managed to figure out a solution that didn't involve drawing out ridiculously large probability trees to brute-force the answer, but I want to know if there's an algorithmic or better way to solve the problem.

Here's my solution below (it's an exact copy of an email I sent to my teammates), but I don't really understand why my solution works. (spoiler'd for length).

Spoiler For Spoiler:
So, I was puttering around with Python, trying to find patterns in the problem, and hit upon a method for finding the answer.  The only thing is, I have no clue how it works.It's also kind of difficult to explain without using paper + pencil (or whiteboard + marker, which is much cooler), but I gave it my best shot.(If possible, view this email in a monospace font -- try copying and pasting into notepad)* * *In short,If the answer has one digit, then there are 5 possibilities1 + 1 + 1 + 1 + 1 = 5If the answer has two digits, then there are 8 possibilities1 + 2 + 2 + 2 + 1 = 8If the answer has three digits, then there are 14 possibilities2 + 3 + 4 + 3 + 2 = 14Here are a bunch more possibilities:1   1   1   1   1     = 51   2   2   2   1     = 82   3   4   3   2     = 143   6   6   6   3     = 246   9   12  9   6     = 429   18  18  18  9     = 7218  27  36  27  18    = 12627  54  54  54  27    = 21654  81  108 81  54    = 378If you notice, each number in the sequence is equal to the sum of numbers that are to the left to the right on the row above it.3  6  6  6  3 \   /6  9  12 9  6(9 is the sum of 3 and 6, for example)So basically, this is like Pascal's triangle, except it's more a rectangle with some fiddly bits.* * *If you're wondering what the numbers represent, they equal the number of possibilities each branch in the tree has or the count of the number in the final branch of the tree (that didn't make sense, did it).An example (for three digits):   1          3          5          7          9 .   3      1   5      3   7      5   9      7   ,    1 5    . 3 3 7    1 5 5 9    3 7 7 .    5 9Each layer represents the number of possibilities in the tree.If there is only one digit, there's only1 1 1 1 1 possibilities.If there are two digits, there's1 2 2 2 1possibilities per branch.However, there is exactly1 one2 threes2 fives2 sevensand 1 ninegiven two digits.If there are three digits, there are2 3 4 3 2possibilities per branch.However, there's1 one3 threes4 fives3 sevensand 1 nine in that layer.* * *Isn't this weird?-- Michael.

« Last Edit: November 11, 2011, 01:42:07 pm by Michael_Lee »
My website: Currently boring.

Projects:
Axe Interpreter
> Core: Done
> Memory: Need write code to add constants.
> Graphics: Rewritten.  Needs to integrate sprites with constants.
> IO: GetKey done.  Need to add mostly homescreen IO stuff.
Croquette:
> Stomping bugs
> Internet version: On hold until I can make my website less boring/broken.

#### calc84maniac

• eZ80 Guru
• Coder Of Tomorrow
• LV11 Super Veteran (Next: 3000)
• Posts: 2905
• Rating: +469/-17
##### Re: Math problem: odd digits and probability
« Reply #1 on: November 11, 2011, 01:57:45 pm »
Yeah, you're pretty much defining it recursively based on the last digit of the (n-1)-digit numbers.

Call the number of valid n-digit numbers ending in each digit an, bn, cn, dn, en for 1,3,5,7,9 respectively.

Then you can make the following recursive definitions:
a1 = b1 = c1 = d1 = e1 = 1 (There is one valid 1-digit number ending in each digit)
an = bn-1 (1 can go after 3 only)
bn = an-1 + cn-1 (3 can go after 1 or 5)
cn = bn-1 + dn-1 (5 can go after 3 or 7)
dn = cn-1 + en-1 (7 can go after 5 or 9)
en = dn-1 (9 can go after 7 only)
"Most people ask, 'What does a thing do?' Hackers ask, 'What can I make it do?'" - Pablos Holman

#### phenomist

• LV4 Regular (Next: 200)
• Posts: 132
• Rating: +46/-3
##### Re: Math problem: odd digits and probability
« Reply #2 on: December 01, 2011, 12:16:34 am »
If you need a closed form expression...

Note that {ai}i=1 = {ei}i=1 via symmetry, and likewise {b} = {d}. We can consider the finite state diagram
a <-> b <-> c <-> d <-> e which is symmetric on c.

Now, we may reexpress each recursion:
an+1=bn
bn+1=an+cn
cn+1=2bn

Notably, this means we can express a and c directly in terms of sequence b. So it logically follows that we should try substituting those out in the recursion for b:
bn+1=3bn-1

The characteristic polynomial of this recursion is λn+1=3λn-1 => λ2-3=0.

In other words the roots are λ = sqrt(3) and -sqrt(3). What does this mean?

Well, this means that we can express sequence b in terms of a linear combination of exponential functions, namely sqrt(3)n and (-sqrt(3))n.
In layman terms, bn=A*sqrt(3)n+B*(-sqrt(3))n.

It is not hard to calculate this; we already know that b1=1 and (easily computed) b2=2.

So we just solve a system of linear equations;
1=A*sqrt(3)-B*sqrt(3) => sqrt(3)/3 = A-B

2=3A+3B => 2/3 = A+B
resulting in A=(2+sqrt(3))/6 and B=(2-sqrt(3))/6.

Thus we have
bn=(2+sqrt(3))/6*sqrt(3)n+(2-sqrt(3))/6*(-sqrt(3))n.

But the million dollar question remains. We don't want the value of an, bn, OR cn; we want the sum!

Well, we add 2an+2bn+cn; the 2 is because we copied d and e over. We reexpress the a and c terms into b because we already have a form ready.

So we have
Σn=2bn+4bn-1=[(2+sqrt(3))/6*(2+4/sqrt(3))]*sqrt(3)n+[(2-sqrt(3))/6*(2-4/sqrt(3))]*(-sqrt(3))n

=[4/3+7sqrt(3)/9]*sqrt(3)n+[4/3-7sqrt(3)/9]*(-sqrt(3))n

(Caveat; Σ1=5, not 14/3; this occurs because the formulas for sequence b refers to a term 2 terms in advance, effectively drawing from the -1st term which is obviously invalid)

The sequence goes: 5,8,14,24,42,72,126,216,378,648,1134,...

Notice anything interesting? No?

I'll show it again. 5,8,14,24,42,72,126,216,378,648,1134,...

Ohey, every other term it triples! Partially due to how the structure of the recursion itself (with λ2-3=0 as a characteristic polynomial), but there in fact is a combinatorial interpretation! (Not all the algebraic sludgework QQ)

It all lies in PARITY. In fact, there are two mechanisms syncing together, digit parity and positional parity. While in the traditional sense, parity refers to evenness or oddness of numbers, since all digits are odd that's not going to be of much use. Instead we consider mod 4 parity, which helps separate the digits better (so 159 and 37). Positional parity refers to the evenness/oddness of the positional index of a particular string.

Well, as luck would have it, you're colorbound like a bishop on a chessboard! Congratulations. As a visual:
..13579
A■□■□■
B□■□■□
A = odd position
B = even position

As it turns out, if you start at a black square, you're condemned to the color that you start on, as each consecutive digit means a position change, and since they differ by 2, it's also digit parity change! So the two color-changing operations cancel out and you're back to square one.