3
$\begingroup$

So I have encountered a question that I am struggling to figure out, what exactly would be considered a perfect way to play a game, especially when this game consists of two players. Its part of Python function that I'm suppose to make.

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 can understand the smaller numbers like 17 and 20. If Jacob starts at 1 and can only get 2 to 9, then the other player can just get 18 (2 x 9) which is greater than 17. So if the number is 17, Vicky automatically wins, but its a lot harder to find out the winner when the numbers get bigger. I had an idea that each player would multiple by the smallest number (2) until a window of opportunity appears but that doesn't seem right as the tests don't turn out to be the same. Please help if possible.

$\endgroup$

1 Answer 1

1
$\begingroup$

Hint

Jacob wins if $n\leq9,$ Vicky wins if $10\leq n\leq 18,$ Jacob wins if $19\leq n\leq 162,$ Vicky wins if $163\leq n\leq 324,$ Jacob wins if $325\leq n\leq 2916,$ etc.

$\endgroup$
14
  • $\begingroup$ The end of Vicky's winning domain is increasing by x 2 from the previous one while the end of Jacob's is increasing by * 9 from the previous one. I am still not sure about the winning strategy, does this mean, that Jacob will always multiple by biggest number in 9 and Vicky will always multiple by the lowest as in 2. I get the first 2 winning domains, Jacob can obviously win in one step if its between 2 and 9, and if its between 10 and 18 he will obviously lose because regardless what he picks, the opponent will be able to win on the second turn. $\endgroup$ Jun 14, 2015 at 18:36
  • $\begingroup$ Cont - 18 is because, Jacob knows he cant win and he chooses to go with two so that the biggest number Vicky can achieve is 18 ( 2 x 9). I don't get it at the 19 to 162 part, 162 I would assume is created through (9 x 18) but why exactly is Vicky's winning domain range so small, compared to Jacob, like Vicky's domain end is just 2 x of its beginning. $\endgroup$ Jun 14, 2015 at 18:44
  • $\begingroup$ @DaenerysTargaryen If $19\leq n\leq 81 $ Jacob will choose $\left\lfloor\dfrac {n - 1} {9} \right \rfloor$ first. If $82\leq n\leq 162 $ Jacob will choose $9.$ Whatever number Vicky chooses, Jacob will win. $\endgroup$
    – martin
    Jun 14, 2015 at 20:04
  • $\begingroup$ @DaenerysTargaryen above $162,$ Vicky will choose $\left\lfloor\dfrac {n - 1} {J_1\cdot 9} \right \rfloor$, where $J_1=$ Jason's first choice, etc. $\endgroup$
    – martin
    Jun 14, 2015 at 20:30
  • 1
    $\begingroup$ Im suppose to do the latter which I have accomplished by recursively creating winning domains for True and False and the program works but it doesn't actually simulate the strategy and proof its just if a number is detected in a specific domain it spits out True or False. I will open a new question about the strategy since I'm interested in it personally. $\endgroup$ Jun 15, 2015 at 17:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .