Help with deriving an absolute strategy (very fun if anything)

Question

My friend and I are trying to figure out a solution or even a best path to figuring out a certain win strategy to this game.

This game that my friend made, calling it the number game for short, is where a person picks a number on the interval [2,100] and then the other person must search for a number which shares both a factor and a digit with the originally picked number. For example, if you start with the number 15, the number the next person chooses must have a factor of one of the following [3,5,15] and share the digit 1 or 5. Additional rules include that one is never considered a factor (as that would make everything easy) and that you may not start on a number which is prime. Whenever a number is picked, it may not be used again therefore the game is over when a player is unable to choose a different number and that player loses.

We are wondering how would determine a set of bounds such that whatever number was picked to go first, you could follow to guarantee victory or if certain numbers guarantee certain loss. What we have started to do is to program a eclipse script in order to run and derive all of the paths of the game with the interval [2,20] as all of the greater intervals have total paths equalling something in the $10^{40}$ power. [2,20] we estimate to have some 7300 paths which is doable by computer. We would be happy to upload preliminary code if anyone is interested, but so far we are still in the process of writing it.

Does anyone have any idea's on how one would go about creating an absolute strategy or even to get a program to print out all of the iterations of path without requiring a supercomputer? Has anyone heard of this game before? Are there any solutions to problems like this that exist on the net (I have not found any) that may help us come to a conclusion?

If you are interested, we have a link to sample game code created with eclipse. Have fun!

Thank you for your help and time

Answer 1

Playing in the $[2,100]$ space:

First player (A) can be immediately beaten if choosing $51,74,92,93,94,95$ - the second player (B) can choose $17,37,23,31,47,19$ respectively, with no other links. So those choices for A are "death" numbers that need to be avoided during open play.

A can set a trap by choosing $70$ - if B chooses $7$ or $77$, A must choose the other and wins. Alternatively, as a first move, A can choose $77$ and if B chooses $70$, A can choose $7$ and win.

There are actually only $14$ numbers that are disconnected from any other: $11,29,41,43,53,59,61,67,71,73,79,83,89,97$ - obviously all the primes over $50$ but only $4$ of the primes under $50$.

$42$ is the best-connected number (along with $84$). I knew it was important.

Answer 2

Playing in the $[2,20]$ game, this is a win (with perfect play) for the second player.

There is a slight flaw in the game rules in that A can choose $9$ first turn, which is isolated. However I suggest that the rules change so that A loses if B has no valid first choice. This then prohibits $3,7,9,11,13,17,19$ as starters.

$14, 15, 16, 18$ are death numbers in open play, leading to a subsequent choice of $4,5,6,8$. The other numbers in play are $2,10,12,20$ - A can choose one of these or lead in with one of the low numbers and B continues through a (now-harmless) death number. B needs to be careful not to exhaust $12,20$ early or A can win since $2$ and $10$ are not connected. Then the game ends at $2$ or through one of the death numbers.