4
$\begingroup$

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?

  • 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.2012-08-07
  • 0
    This is basically a nim game. So, classical algorithms using the mex can be used to determine who has the winning strategy.2012-08-07
  • 0
    @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).2012-08-07
  • 0
    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.)2012-08-07
  • 0
    @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$.2012-08-08
  • 0
    @ErickWong Except that he allows duplicates, and I was adding a node for each duplicate. Then the condition gets more complicated: Two nodes are defined to be "equivalent" if they have the same set of neighbors. Then the set of length $2$ directed paths can pass through at most two equivalence classes.2012-08-08

0 Answers 0