Game of 2/9 (Interview at Facebook)

Question

I was asked this question: similar question at google. Similar question was asked during Facebook interview.

Determine winner of 2/9 number game

Two players play the following game: they pick a random number N (less than 2 billion) then, starting from 1, take turns multiplying the number from the previous turn with either 2 or 9 (their choice). Whoever reaches N first wins.

The candidate should write a function that given N decides who wins (first or second player?)

Will a basic random choice of 2/9 for multiplication work or they'd want us to add intelligence in making moves. For ex: start with multiplication with 2 and multiply with 9 only when you see the other person will not be able to reach N quicker than you?

What is the best way to approach these type of questions?

Answer 1

The best approach to this type of questions.

First you need to have the basic understanding of the theory of games. Really basic. That is you are conscious of the fact, that for a given number N there is either a winning strategy for player who starts or a winning strategy for his oponent. So you must assume that they both know the strategy and play the best moves they can.

Then you start to become familiar with the game. You practice on a low level. You quickly notice that for 2-9 the starter is winning, while for 10-18 he must lose. So your function is ready for a case of N<=18.

Then you start thinking of a general winning strategy. Knowing the strategy would give you the algorithm. After 5 minutes (the sooner the better) you understand that you won't fit in time to find the winning strategy, as it is not obvious in that case. So you decide to give the computer some basic principles and let it solve the puzzle for you. You know you'll use the recursion.

You try to find the rule for recursion. You may want to start from the end or from the beginning. I'll describe the approach from the end.

The goal of the game is to push your opponent to the zone, where he must give you the victory. And not get pushed to that zone yourself. From N/9 to N there is a zone for winning. If one is pushed to play from between N/9/2 and N/9, he must lose. (Because both his moves push his opponent to the winning zone.) So you write your function:

wins(n) {
  // returns 1, if starting player is able to reach
  // the range [n, 2*n) with his move
  if (n<=18) {
    if (n<=9)
      return 1;
    else
      return 0;
  } else {
    // I must push him to the zone between N/9/2 and N/9
    return wins(n/18);
  }

If you reached that point, you passed. There are details left, like whether to use float or int, whether to round up or down using int. But in general you showed the right way of thinking and you're ready to face the interviewer :)

EDIT: Actually there is a mistake in the code above. "Winning" is not the same as "being able to reach the range (n,2n)". Maybe 2 functions are necessary here: wins(n) and reaches_slightly_above(n). The latter would be called in a recursive way, and the values returned below 18 should be different, resemble the ones in the solution of Peter de Rivaz. However the solution below and the general approach should be ok.

The alternative approach, going from bottom to up, would be to use the function:

wins(a,n) {
  if (9*a >= n)
    // I win easily
    return 1;
  else
    // if one of my moves pushes the opponent to the zone
    // where he's not able to win, then I win!
    return !wins(2*a, n) || !wins(9*a, n);
}

If they ask for n, you return the value of win(1,n). The complexity of this algorithm is not obvious, but I believe it's logarithmic.

Answer 2

Two-player, deterministic games such as this are studied by combinatorial game theory. This frivolous game theory has no relation with the more useful game theory of Neumann and Nash popular in economics. The seminal work is a delightful book called Winning Ways by Conway, Berlekamp & Guy.

Think. For any game, either:

1. There is a strategy whereby the second player always wins, however the first player plays.
2. There is a strategy whereby the first player always wins, however the second player plays. 

Your game is a special case, an impartial game, where the state of the game looks the same to both players. The best example is a simple matchstick game called Nim. It happens that all impartial games are equivalent to Nim (this is the Sprague Grundy theorem), so all impartial games can be solved completely.

---

Let's solve your game. The possible states of the game are the positive integers. We'll classify each state as either winning for the second player (we'll label such games zero '0' games), or winning for the first player (we'll label such games star '*' games).

The integers greater than or equal to N are all zero games, because at this point the game is over. Whoever's move it is has already lost.

States where the player whose turn it is can move to the zero positions above are star games. Thus the integers n, N/9 <= n < N are all star games - the winning move is to multiply by 9.

States where the player whose turn it is has no choice but to move to star position are zero positions again. So integers n, N/9/2 <= n < N/9 are zero positions. Our player has lost.

And so on. Using the similar arguments we eventually classify all integers down to one.

---

For N=1000 say,

• Integers 1000 and above are zero games
• Integers 112 to 999 are star games (to win, multiply by 9)
• Integers 56 to 111 are zero games (the player can't win)
• Integers 7 to 55 are star games (multiply by 9 or 2 accordingly so to move to one of the zero games 56 to 111)
• Integers 4 to 6 are zero games (the player can't win)
• Integers 2 to 3 are star games (multiply by 2)
• The integer 1 is a zero game (the player can't win)

---

Generalising we reach Peter's conclusion https://stackoverflow.com/a/13367642/284795

Answer 3

Yes, you are supposed to think of an optimal-play from both players and decide who will win.

Here, a simple recursive thinking could lead you to a solution.

If a player is with number n and n*9 >= N then the current player will win the game.
else, He will pass on either 2*n or 9*n, to the 2nd-Player. Now, 1st-Player will lose the game only if both options provided by him(2*n and 9*n) to the 2nd-Player lead to a winning number for 2nd-Player, otherwise he will have a chance of picking a winning number again.

Hence, we could write a recursive approach as following:
since, all numbers in game are going to be of form: 2^i * 9^j we could write:

 F(i, j) = true; if (2^i * 9^j * 9) >= N
           !(F(i+1, j) && F(i, j+1)); otherwise

solution would be in F(0, 0), whether the 1st-Player wins or not.