Two players A and B are playing a game. The game is as follows: the player having the turn can multiply the money with a particular number between 2 to 9 and pass the money to other player. For example initially if A is having 1 rupee with him , therefore he can multiply the money by any number from 2 to 9 and pass it to B.Now B can do the same thing and pass it to A.

So you are given a particular number n. The player whose multiplication results in amount >= n gets all of the money.

You are also given the player name who must win this game (suppose x) , you have to tell which player must have initial 1 rupee so that it can be guaranteed that x will win. (It is given that both players play optimally i.e. both player plays the best move for him to win).

EXAMPLE: If n=2 and winner is A.

A must have 1 ruppee initially So here answer is A.

  • $\begingroup$ Who wins the game? The first person to multiply past $n$ and not have to pass it on? $\endgroup$ – Calvin Lin Mar 4 '14 at 16:34
  • $\begingroup$ @CalvinLin going by his example yes. Otherwise B would win. Interesting question though. $\endgroup$ – Guy Mar 4 '14 at 16:54
  • $\begingroup$ @Sabyasachi what about if N=17 and player B is the winner $\endgroup$ – user3001932 Mar 4 '14 at 16:57
  • $\begingroup$ @user3001932 this is a very interesting question. Solving it for the general case if even more interesting.This probably be tagged game-theory as well. $\endgroup$ – Guy Mar 4 '14 at 17:03
  • $\begingroup$ @Sabyasachi so whats ans for above example acc to u? $\endgroup$ – user3001932 Mar 4 '14 at 17:19

An equivalent way of describing the game is that, starting from $1$, the two players simply take turns multiplying the current product by any number between $2$ and $9$. It sounds as if the winner is defined to be the player who first produces a product that is greater than or equal to $n$. Naming the player who is supposed to win and asking whether they should go first or second is, obviously, equivalent to asking whether the game (with target $n$) is a first-player win or a second-player win.

Presumably the OP is restricting the player's choices to the integers from $2$ to $9$. Assuming this, then the game is a first player win when $2\le n\le9$, a second player win when $10\le n\le18$, a first player win again for $19\le n\le162$, a second player win for $163\le n\le324$, a first player win for $325\le n\le2916$, and so forth, where the upper limit sequence $9,18,162,324,2916,\ldots$ is obtained by alternately multiplying by $2$ and $9$.

A way to see this is to reinterpret the game as starting at $n$, with each move consisting of computing the ceiling function

$$\lceil {n\over k} \rceil$$

where $2\le k\le9$, and where the game ends when the value becomes $1$.


(I'm assuming that the person who can multiply past $n$ will win the game.)

Hint: The loser of the game is the first person to receive more than $\frac{n}{2}$.

Hint: The winner of the game is the first person to receive more than $\frac{n}{18} $.

Continue this sequence of winning / losing positions to it's natural conclusion.

If you want player A to win, and you know that the first person to move will win, then person to start will be player A.

  • $\begingroup$ I know the winner , i need to tell who start the game $\endgroup$ – user3001932 Mar 4 '14 at 16:38
  • $\begingroup$ @user3001932 You need to define what "win" the game means. You have never said how to win the game, merely that someone has to win the game. $\endgroup$ – Calvin Lin Mar 4 '14 at 16:38
  • $\begingroup$ I know at start that who ll win the game.Here by winner is that player who gets all the money $\endgroup$ – user3001932 Mar 4 '14 at 16:41
  • $\begingroup$ @user3001932 What does it mean to win the game? If you are the first person to multiply by 5? If you are the first person to leave? YOu need to define the winning condition. $\endgroup$ – Calvin Lin Mar 4 '14 at 16:42
  • $\begingroup$ when multiplcation answer exceeds N then the other player who cant multiply anymore looses the game $\endgroup$ – user3001932 Mar 4 '14 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.