# Strategy/Proof behind the Perfect solution of a Multiplication Game

So the below is the question

Question: Jacob and Vicky play the fun game of multiplication by multiplying an integer p by one of the numbers 2 to 9. Jacob always starts with p = 1, does his multiplication, then Vicky multiplies the number, then Jacob and so on. The winner is who first reaches p >= n (when n is a number chosen at the beginning of each game n>1). Assuming that both of them play perfectly (i.e. Jacob and Vicky play to win, and follow the perfect strategy to win ). Write a Python function play_fun_game, that consume a positive integer n and produces True if Vicky wins after playing the game according to the explained rules, otherwise the function produces False.

These are some of examples for this question.

play_fun_game(17) => True

play_fun_game(35) => False

play_fun_game(190) => True

play_fun_game(771) => False

play_fun_game(20) => False

play_fun_game(3480) => True

play_fun_game(1589) => False

play_fun_game(5768) => True

play_fun_game(36) => False

play_fun_game(2222) => False

play_fun_game(3489) => True

I've already learned the winning domains for each player but what I'm really interested in is if any positive integer (n, n>1) was chosen, how would each player try to play to win even though one is definitely going to lose because its not his/hers (winning domain) if both sides play optimally. I guess the question is how you play optimally for any n. Just for example, could someone explain to me how the two players would each play if the number was 771, whats the thinking behind it.

In the absence of a general solution (ie described for all $n\in\mathbb{N}$), I offer a domain-based solution.

Optimal play (as described below) is defined as winning in all cases, if the opponent were to play randomly. Vicky therefore has an optimal play within her winning domain, and Jason has a strategy within his domain. If desired, for study purposes, both strategies can be combined to give entirely predictable outcomes.

The solution below is only valid for for $n\leq 5832.$ The same logic may be applied however, to extend each player's strategy to any desired $n.$

Claim:

The wining domains for Jason & Vicky are as follows:

\begin{align} &\text{Jacob}:&1< n &\leq \ 9&\\ &\text{Vicky}:&9< n &\leq \ 2\cdot 9&\\ &\text{Jacob}:&2\cdot 9< n &\leq \ 2\cdot 9^2&\\ &\text{Vicky}:&2\cdot 9^2< n &\leq \ 2^2\cdot 9^2&\\ &\text{Jacob}:&2^2\cdot 9^2< n &\leq \ 2^2\cdot 9^3&\\ &\dots\text{etc}. \end{align}

This can be simplified to

\begin{align} \text{win}(n)=\text{int}\left(\frac{\log (2\ (n-1))}{\log (2)+\log (9)}\right)+\operatorname{int}\left(\frac{\log (18\ (n-1))}{\log (2)+\log (9)}\right) \begin{cases} \text{Jason iff win}(n)\text{is odd}\\ \text{Vicky iff win}(n)\text{is even}\\ \end{cases} \end{align}

Strategies & tests:

For $n=2$ to $162,$ the fairly obvious unbeatable fixed best plays are as follows:

\begin{array} {|l|l|} \hline \text{n} &\text{win} & \text{play}\\ \hline 2-9 &\text{Jacob}& 9\\ 10-18 &\text{Vicky}& \_,9\\ 19-27 &\text{Jacob}& 2, \_, 9\\ 28-36 &\quad\downarrow& 3, \_, 9\\ 37-46 && 4, \_, 9\\ 46-54 && 5, \_, 9\\ 55-63 && 6, \_, 9\\ 64-73 && 7, \_, 9\\ 73-81 && 8, \_, 9\\ 82-162 && 9, \_, 9\\ \hline \end{array}

where, for simplicity's sake, the final play is always $9.$ However, after $n=162,$ there is no best fixed play. Before continuing then, it may be helpful to define a few to define a few helping functions first:

\begin{align} \lambda(n)= \begin{cases} 2\quad \text{if }x<2&\quad&\quad&\ \ \ \\ 9\quad \text{if }x>9\\ x\quad \text{if otherwise}\\ \end{cases} \\\\ \Lambda\left(\left(x_1,x_2,\dots,x_y\right),n\right)= \begin{cases} 1\quad \text{if }\ (9\cdot x_1\cdot x_2\cdots x_y) \leq n\\ (9\cdot x_1\cdot x_2\cdots x_y) \text{ if otherwise} \end{cases} \end{align}

and $$M= \begin{pmatrix} a_{1,1}&\dots&a_{1,9}\\ \vdots&\ddots&\vdots\\ a_{9,1}&\dots&a_{9,9} \end{pmatrix}$$ where row $a_1=\{\square,\square,\square,\dots\}$, $a_2=\{\square,2,2,2,2,\dots\}$, $a_3=\{\square,3,2,2,2,\dots\},$ up to $a_9=\{\square,9,8,7,6,5,4,3,2\},$ (where $\square$ is a space-filler, since $a_{\_,1}$ will never be chosen). eg $a_{3,5}=4.$ Simplify this to a function then, so $M(x,y)$ corresponds to $a_{x,y}$ for ease of reading.

For $n=163-324,$ Vicky must play $\lambda\left\lfloor\dfrac{n-1}{\Lambda(j_1,n)}\right\rfloor,$ where $j_1$ is Jacob's first choice.

eg For $n=200,$ if $j_1=5,$ $v_1=\lambda\left\lfloor\dfrac{200-1}{\Lambda(5,200)}\right\rfloor=4.$

For $n=325-2916,$ Jacob's choices should be:

\begin{align} j_1= \begin{cases} 2\text{ if }324<n\leq 648\\ 4\text{ if }648<n\leq 1296\\ 8\text{ if }1296<n\leq 2592\\ 9\text{ otherwise}\\ \end{cases} \\\\ j_2=\lambda\left\lfloor\dfrac{n-1}{\Lambda((j_1,v_1),n)}\right\rfloor\quad\quad\ \end{align}

For $n=2916-5832,$ Vicky's first choice must meet a new condition:

So, to answer the question in the OP re what optimal play is for $n=771,$ $j_1=4,$ since $648<n\leq 1296.$ The optimal plays $(j_1,v_1,j_2)$ for varying $v_1$ then, are:
$(4,2,9),(4,3,7),(4,4,5),(4,5,4),(4,6,3),(4,7,3),(4,8,2),(4,9,2)$
Of course, it won't matter what $v_2$ is if $j_3=9.$
Mathematica code for game simulation can be found here, where implementation is game[n]. Verification of the above method can therefore be shown with Accumulate[Length@# & /@ Split[(game@# & /@ Range@5832)[[All, 1, 1]]]].