<p>Let some finite array of integers is given initially.</p>

<p>There is a number k which is initially '0'.</p>

<p>In a move, a player will select a number from the array arr[i] and change k to gcd(k,arr[i]).</p>

<p>Also, the number chosen from the array(i.e a[i]) will be removed from that array.</p>

<p>CONSTRAINTS</p>

<p>A player who makes k=1 at any step loses.
A player who cannot move also loses.
2 players are playing the game optimally.</p>

<p>When will the player who moves first wins the game?</p>

CC BY-SA 3.0
2014-05-06T12:56:41.607Z
this seems related to the Sylver Coinage game: http://en.wikipedia.org/wiki/Sylver_coinage
greg
CC BY-SA 3.0
2014-05-06T16:57:30.230Z
@mobiusdumpling I have seen that game before,But how can we reduce it to this one.
user2573642
CC BY-SA 3.0
2014-05-06T21:15:29.300Z
This seems to be identical to the problem http://www.codechef.com/MAY14/problems/SEAGM, which is a problem on a currently ongoing contest. It's probably best to at least wait until the contest is over before answering.
jschnei
<ds.algorithms><pr.probability><gt.game-theory><combinatorial-game-theory>
What is the optimal strategy for this 2 player game?
user2573642
# What is the optimal strategy for this 2 player game?

(Asked by: username_0 on 2014-05-06)

Let some finite array of integers is given initially.

There is a number k which is initially '0'.

In a move, a player will select a number from the array arr[i] and change k to gcd(k,arr[i]).

Also, the number chosen from the array(i.e a[i]) will be removed from that array.

CONSTRAINTS

A player who makes k=1 at any step loses.
A player who cannot move also loses.
2 players are playing the game optimally.

When will the player who moves first wins the game?

**Tags:** ds.algorithms, pr.probability, gt.game-theory, combinatorial-game-theory
> **Comments:**
> **username_1**: this seems related to the Sylver Coinage game: http://en.wikipedia.org/wiki/Sylver_coinage  
> **username_0**: @mobiusdumpling I have seen that game before,But how can we reduce it to this one.  
> **username_2**: This seems to be identical to the problem http://www.codechef.com/MAY14/problems/SEAGM, which is a problem on a currently ongoing contest. It's probably best to at least wait until the contest is over before answering.  

---

## 0 answers

