Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

2 players A and B play a game. At the start of the game, $n$ positive integers (not necessarily distinct) are written on a notebook. First, player A chooses a number from the notebook and declares it the "current number". After that, they play alternately starting with B. At each turn, they do the following: if the current number is $x$, then the player erases $x$ from the notebook (if multiplicity > 1, leaves the rest unerased), chooses some other number $y$ from the notebook, and declares it the "current number". $y$ can be chosen provided either

1) $x|y$ and $y/x$ is prime, or 2) $y|x$ and $x/y$ is prime.

The first player who is unable to make a move loses. When does A have a winning strategy?

share|improve this question
1  
It might be more instructive to think of this as a game on a directed graph, where each number is a node and there is a directed edge $(m,n)$ if $n=pm$ for some prime $p$. This graph is acyclic and any two directed paths between two nodes $x,y$ will have the same length. Not sure if all such graphs are represented by these conditions, or if there are other conditions needed. –  Thomas Andrews Aug 7 '12 at 20:17
    
This is basically a nim game. So, classical algorithms using the mex can be used to determine who has the winning strategy. –  Xoff Aug 7 '12 at 20:21
    
@ThomasAndrews Seems like the graph is undirected. Certainly not all graphs can be embedded (there are no odd cycles), but it could be viewed as an arbitrary subset of the direct sum of countably many $\mathbb N$'s (under a suitable graph product). –  Erick Wong Aug 7 '12 at 20:27
    
It is a problem about undirected paths in a directed graph, @ErickWong. Basically, the question about a general (undirected) graph might be enough to solve the problem, but I wanted to find out what properties the conditions place on the graph. (For example, the undirected graph is definitely bipartite.) –  Thomas Andrews Aug 7 '12 at 20:29
    
@ThomasAndrews I see what you are getting at. There are definitely other conditions needed: for instance, if $x,y$ are at distance $2$ then there can be at most two directed paths from $x$ to $y$. –  Erick Wong Aug 8 '12 at 7:56
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.