What are my chances in a Most Excellent Adventure?

Solution 1:

It is remarkable, though maybe not trivial, that for almost every connected set of phone keys, there exists a Eulerian path through the digits (that is you can walk from digit to adjacent digit and reach all digits exactly once). By simply repeating multiple digits, you can thus dial a number (almost) whenever the set of keys is connected.

There are few exception to the rule above:

• If you have $4, 6, 8, 0$ but neither $2, 5, 7, 9$, there is no Eulerian path. You can win only if you have two $8$s.
• If you have $1, 3, 5$ and at least one of $7,8,9$, but none of $2,4,6$, a similar situation occurs. You may need (at least) two $5$s.
• The previous case rotated by 90° or 180° or 270° around the $5$ key.

In summary: If the set of keys is connected, you have almost won. However, for a precise analysis, I am afraid tha a computer based enumeration of all possibilities is the only way to go.

Solution 2:

I'm not sure that this qualifies as a complete answer to the question, but it will certainly provide some useful ideas and information.

I wrote a program to solve this using the following brute force technique.

1. Create a Possibe_Next_Key integer set for each of the digits 0 to 9 E.g. For 1 this is {1,2,4,5} those being the allowable next key presses following a 1
2. Make a Next_Key_Possible boolean array based on the Possibe_Next_Key sets. This is a 2D array of the form [From_Key,To_Key]=true|false E.g. Possible_Next_Key[0][5]=false because there is no direct link from the 0 to the 5 key
3. Iterate through all $10^{6}$ permutations, finding the longest ordered sequence of connected numbers, checking for uniqueness against previous permutations, and so updating a dictionary containing the following:- {UniqueSet, Longest_Key_Sequence, Number_Of Permutations}
4. Finally - total up the Number_Of_Permutations for each Longest_Key_Sequence

And the results I get are as follows:

Ways of getting a maximum key-sequence of 1 key = 0

Ways of getting a maximum key-sequence of 2 keys = 6300

Ways of getting a maximum key-sequence of 3 keys = 76640

Ways of getting a maximum key-sequence of 4 keys = 119340

Ways of getting a maximum key-sequence of 5 keys = 168024

Ways of getting a maximum key-sequence of 6 keys = 629696

Note - their sum is $10^{6}$

So if $P_{n}$ is the probability that the longest phone number that can be dialed with a roll of 6 10-faced dice is n (following the rules of the game) then

$P_{1}$ = 0

$P_{2}$ = 0.0063

$P_{3}$ = 0.07664

$P_{4}$ = 0.11934

$P_{5}$ = 0.168024

$P_{6}$ = 0.629696

Assuming my program is correct, which I believe it to be.