a2dalek's blog

a problem about game theory
By a2dalek, history, 4 years ago, In English

I can't solve this problem: There are N stones (N<=1e18) and two players. They play alterably. At the k-th turn, player must take at least 1 stone but can take no more than k stones (player at the first turn can take no more than 1, player at the second turn can take no more than 2,..). Who takes the last stone is the winner. Give N, who will win the game, player 1 or player 2 ? Please help me. Tks.

  • Vote: I like it
  • -15
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i think the winner is affected by minimum x satisfied (x-1) + x >= k that is odd or not

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think player 2 wins if n%(k+1) == 0, else player 1 wins.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry because my blog was unclear. I updated.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by a2dalek (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

I don't know proof but solution look like this series. If a(n) = 1, then first player win, otherwise second player win.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Inspired by Sakhiya07's result, I give a proof.

Note that whatever in 2k - 1-th turn, first player take, the second player could make the sum of 2k - 1-th turn and 2k-th turn to be $$$2 k$$$ or $$$2 k + 1$$$. so we may write $$$n$$$ as:

$$$ n = 2 + 4 + \cdots + 2 k - 2 + m $$$

if $$$m = 2k, 2k + 1$$$, then since at 2k - 1-th turn, the first play take at most $$$2 k - 1$$$ stones, the second player will win.

Now, if $$$2k \leq m \leq 2k + k$$$, we may write $$$n$$$ as:

$$$ n = 3 + 5 + \cdots + 2l + 1 + 2l + 2 + \cdots + 2k - 2 + 2k $$$

Similar, we know the second player will win.

Thus, if $$$k^2 + k \leq n \leq k^2 + 2k$$$, the second player will win.

Similar, whatever in 2k - 2-th turn, second player take, the second player could make the sum of 2k- 2-th turn and 2k - 1-th turn to be $$$2 k - 1$$$ or $$$2 k$$$, we can write $$$n$$$ as:

$$$ n = 1 + 3 + \cdots + (2k - 1) + m $$$

easy to easy if $$$2k + 1 \leq m \leq 2k + 1 + k$$$, the first player will win.

Thus, if $$$k ^ 2 \leq n < k^2 + k$$$, the first player will win.

Code is easy:

bool f(long long n) {
	long long k = std::sqrt(n + 0.1);
	return n < (k + 1) * k;
}
→ Reply