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

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

• I guess no primes are ever played, is that right? Because they cannot share a factor (other than 1, which is out of play) with any other number? – Brian Tung Jun 3 '15 at 17:55
• @Brian_Tung yes that seems to be the case – TrostAft Jun 3 '15 at 17:55
• Got it. @BrianTung primes can come as they can be factors and share a digit. – Macavity Jun 3 '15 at 17:56
• Well, no I think I was wrong. If A plays 94, then B can play 47, and wins. – Brian Tung Jun 3 '15 at 17:57
• @BrianTung 47 does not share a factor with 94 right? the game rules forbids 1 being the shared factor. – TrostAft Jun 3 '15 at 17:59

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.

• Your answer is great, really helpful when playing the game. Still looking for an absolute rule of some kind (if it exists / solvable) – TrostAft Jun 4 '15 at 14:23

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.

• Alternative rule change: If B has no valid first choice, A simply has to pick a different starting number. – Joffan Jun 4 '15 at 17:24