Each subsequent choice must be adjacent to the most recent choice of the other player.Thus, together they follow a path. The last player able to move wins. Who has a winning strategy that always works no matter how the other player plays? Intuitively, I believe Alice will win because she's limiting Bob to the vertex that she ends off with. I don't know if that's the idea. Any help would be great.

  • $\begingroup$ Are you not allowed to repeat a choice? $\endgroup$ – lulu Mar 28 '16 at 23:09
  • $\begingroup$ Clearly there is no general strategy that works for all graphs, because on a cycle all choices (essentially) are determined. If the cycle has odd length Alice wins, even length Bob wins. $\endgroup$ – David Mar 28 '16 at 23:10
  • $\begingroup$ A path doesn't contain a repeated edge. $\endgroup$ – nyorkr23 Mar 28 '16 at 23:11
  • $\begingroup$ David, that was what I was thinking. $\endgroup$ – nyorkr23 Mar 28 '16 at 23:11

Your Answer

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

Browse other questions tagged or ask your own question.