[superprismatic]

A very good random number generator (RNG)

produces the digits 0,1,2, and 3 uniformly.

Two such digits are generated and added

together to produce a key which is used

to encipher the first digit of a 12-digit

number. Two more digits are generated,

added together, then added to the previous

key modulo 10 to produce another key which

is used to encipher the second digit of the

12-digit number. This continues until all

the digits of the 12-digit number are

enciphered. Encipherment of each digit

consists of adding it to its key modulo 10.

Here is a sample encription of the 12-digit

number 993662969236:

RNG    Key    Plain Digit    Cipher

3 0     3         9            2

1 3     7         9            6

2 2     1         3            4

3 1     5         6            1

1 2     8         6            4

1 2     1         2            3

0 3     4         9            3

3 0     7         6            3

1 1     9         9            8

2 1     2         2            4

3 1     6         3            9

1 2     9         6            5

[/code]


Note that, with the exception of the first

key digit, key is produced by adding the

two outputs of the RNG to the key used for

the previous digit.



Suppose that the 12-digit numbers to be

enciphered are made by choosing each digit

independently from the distribution:

[code]

Digit   Probability

  0        .07

  1        .02

  2        .19

  3        .18

  4        .15

  5        .01

  6        .14

  7        .09

  8        .03

  9        .12

You are presented with the cipher

843386775967. What is the most probable

12-digit number which could have been

enciphered (in the above manner) to

produce it?

Note also that, even though the RNG choses

uniformly, the sum of two such digits does

not follow a uniform distribution. Also

keep in mind the way the 12-digit plain

digits are formed.

Have fun!

[superprismatic]

I just realized that the question I posed

in the OP is a bit ambiguous. I think that

there are two possible interpretations of

my question:

#1. This was the one I intended. You know

the method of encipherment. You are given

the cipher (843386775967). You stand to

receive a large reward if you can guess

the original 12-digit number. In this

scenario, you need to take into account

how likely the key sequence is as well as

how likely the 12-digit number looks in

light of its known distribution.

#2. This is not what I intended, but is

valid nonetheless. Here, you are to find

the most probable 12-digit number

(according to its known distribution)

which can be made from the given cipher

using any particular valid key sequence.

The actual probability of the key sequence

is inconsequential as long as it is not 0.

I think, however, that this is just as

difficult to answer as #1.

[Guest]

Tough Question!!!

I think i have a solution:

Number: 462926426622

The main problem is that the probability of each number is based on the probability of previous numbers, you'd have to write an A-Star type algorithm to determine with absolute certainty which is the best possible solution.

That being said if we assume the first number based on it's highest probability, and then the second based on assuming the first number is right, third assuming the second is right, we can come up with a solution:

Good one! Tough Question!!

EDIT: I just realize that the probabilities in the above table were not normalized. A better heading for the table would be "Product of Digit/RND Number probabilities")

Edited July 7, 2010 by littlej

[bushindo]

Tough Question!!!

I think i have a solution:

Number: 462926426622

The main problem is that the probability of each number is based on the probability of previous numbers, you'd have to write an A-Star type algorithm to determine with absolute certainty which is the best possible solution.

That being said if we assume the first number based on it's highest probability, and then the second based on assuming the first number is right, third assuming the second is right, we can come up with a solution:

Good one! Tough Question!!

EDIT: I just realize that the probabilities in the above table were not normalized. A better heading for the table would be "Product of Digit/RND Number probabilities")

I get

4 9 3 2 2 2 2 2 2 2 2 2

[superprismatic]

Tough Question!!!

I think i have a solution:

Number: 462926426622

The main problem is that the probability of each number is based on the probability of previous numbers, you'd have to write an A-Star type algorithm to determine with absolute certainty which is the best possible solution.

That being said if we assume the first number based on it's highest probability, and then the second based on assuming the first number is right, third assuming the second is right, we can come up with a solution:

Good one! Tough Question!!

EDIT: I just realize that the probabilities in the above table were not normalized. A better heading for the table would be "Product of Digit/RND Number probabilities")

You have a pretty good answer even though it

is not the highest possible. Your answer has probability

of 5.1×10^-19. That's a little more than half of the

probability of the best answer. The target probability

is the product of the individual probabilities (according

to the given distribution) of the digits in the 12-digit

number times the product of the probabilities of the

sum of each pair from the RNG used to produce key.

[superprismatic]

I get

4 9 3 2 2 2 2 2 2 2 2 2

Your answer requires the key to be 450164553745.

So, the sum of the pairs of digits (from 0, 1, 2, or 3)

coming out of the RNG must be 415158108471 (remember,

according to the OP the sum of pairs is accumulated),

which is impossible because the two 8s and the 7

could not be the sum of two digits from the RNG.

[Guest]

You have a pretty good answer even though it

is not the highest possible. Your answer has probability

of 5.1×10-19. That's a little more than half of the

probability of the best answer. The target probability

is the product of the individual probabilities (according

to the given distribution) of the digits in the 12-digit

number times the product of the probabilities of the

sum of each pair from the RNG used to produce key.

Hmmm... Back to the drawing board.

[Guest]

Number: 694249639932 Probability: 8.50991E-19

[superprismatic]

Number: 694249639932 Probability: 8.50991E-19

You have a better answer and I do agree with your probability calculation to within 5 significant digits. But, it still isn't the best possible.

[Guest]

Can you give a hint in the form of the probability of the best answer?

[superprismatic]

Can you give a hint in the form of the probability of the best answer?

OK, your last probability was very close to 75% of that of the best answer. It's funny,

but your first answer was very close to 50%. I guess your stepping by half the remaining

distance each time!

[Guest]

OK, your last probability was very close to 75% of that of the best answer. It's funny,

but your first answer was very close to 50%. I guess your stepping by half the remaining

distance each time!

I'm stumped without generating a brute force method algorithm or a A-STAR algorithm. Were you able to come up with your solution using logic?

[superprismatic]

I'm stumped without generating a brute force method algorithm or a A-STAR algorithm. Were you able to come up with your solution using logic?

No, and I never thought of using an A* algorithm -- I think

that would be far too complicated for this type of problem.

I just wrote a simple dynamic program which chains small

links from time T to time T+1 together. For every pair

of possible plain pairs (p,q), I find the best path (in

terms of probability) going from p at time 1 to q at time

T. This is easy to extend inductively to time T+1. So,

I have exactly 100 paths at every time T>1. When I get

to time T=12, I find the best of the 100 I have (in terms

of probability). That's it! This kind of use is what

dynamic programming was at its inception, about 60 years

ago. Since then, dynamic programming has come to include

more complicated scenerios. My program is quite small

and runs in a few milliseconds. I hope you or someone

out there tries this and finds the highest probability

12-digit number.

[Guest]

584138638931

584178638931

584938638931

584978638931

edit: for editing

Edited July 9, 2010 by PVRoot

[superprismatic]

584138638931

584178638931

584938638931

584978638931

edit: for editing

Two of these (584178638931 and 584978638931) are

are impossible because the cipher (843386775967)

has an 86 in the 5th & 6th positions, making the

key at these positions to be 18. The difference

in these positions is 7 (8-1) which cannot be obtained

by adding two numbers between 0 and 3 from the RNG.

The other two are possible but have very small

probabilities.

[Guest]

Two of these (584178638931 and 584978638931) are

are impossible because the cipher (843386775967)

has an 86 in the 5th & 6th positions, making the

key at these positions to be 18. The difference

in these positions is 7 (8-1) which cannot be obtained

by adding two numbers between 0 and 3 from the RNG.

The other two are possible but have very small

probabilities.

edit: for editing

				This is yours				

     sum   plus     mod           Plain   Key +  mod

RNG  of     to      ten    Key    Digit   Plain  ten   Cipher

     RNG previous  equals                 Digit equals

3,0   3	    3	     3	    3	    9	   12	  2	 2

1,3   4	    7	     7	    7	    9	   16	  6	 6

2,2   4	   11	     1	    1	    3	    4	  4	 4

3,1   4	   15	     5	    5	    6	   11	  1	 1

1,2   3	   18	     8	    8	    6	   14	  4	 4

1,2   3	   21	     1	    1	    2	    3	  3	 3

0,3   3	   24	     4	    4	    9	   13	  3	 3

3,0   3	   27	     7	    7	    6	   13	  3	 3

1,1   2	   29	     9	    9	    9	   18	  8	 8

2,1   3	   32	     2	    2	    2	    4	  4	 4

3,1   4	   36	     6	    6	    3	    9	  9	 9

1,2   3	   39	     9	    9	    6	   15	  5	 5

Is this the method used to go from Key to Plain Digit to Cipher?

Edited July 9, 2010 by PVRoot

[Guest]

				This is yours				

     sum   plus     mod           Plain   Key +  mod

RNG  of     to      ten    Key    Digit   Plain  ten   Cipher

     RNG previous  equals                 Digit equals

3,0   3	    3	     3	    3	    9	   12	  2	 2

1,3   4	    7	     7	    7	    9	   16	  6	 6

2,2   4	   11	     1	    1	    3	    4	  4	 4

3,1   4	   15	     5	    5	    6	   11	  1	 1

1,2   3	   18	     8	    8	    6	   14	  4	 4

1,2   3	   21	     1	    1	    2	    3	  3	 3

0,3   3	   24	     4	    4	    9	   13	  3	 3

3,0   3	   27	     7	    7	    6	   13	  3	 3

1,1   2	   29	     9	    9	    9	   18	  8	 8

2,1   3	   32	     2	    2	    2	    4	  4	 4

3,1   4	   36	     6	    6	    3	    9	  9	 9

1,2   3	   39	     9	    9	    6	   15	  5	 5

Is this the method used to go from Key to Plain Digit to Cipher?

edit: for editing

I see where I messed up on mine and I just want to make sure I'm figureing how to go from key to plain digit to cipher correctly?

[superprismatic]

I see where I messed up on mine and I just want to make sure I'm figureing how to go from key to plain digit to cipher correctly?

I was just trying to point out that to go from a key value to the next one, you can't add more than 6.

So, your key was like this: ....18...... , and in order to go from 1 to 8 requires adding 7. I hope

it's clear now.