34
$\begingroup$

Rules

Alice and Bob take turns claiming territories on a map with a finite number of territories. After their first turn, a player may only claim a territory if it borders one they already own. If a player has no moves available, they lose their turn. Once neither player can move, a player wins if they own more territories.

Examples

On the map below, play might proceed as follows:

  1. Alice claims B,
  2. Bob claims C,
  3. Alice claims A,
  4. Bob claims D,

resulting in a 2-2 draw. Map with 4 territories where A borders B, B borders C, and C borders D.

On this map, here's how the game might go:

  1. Alice claims B,
  2. Bob claims C,
  3. Alice claims D,
  4. Bob loses his turn,
  5. Alice claims A,

and Alice wins 3-1. Map with 4 territories where A borders B, B borders C, and C borders D, and D borders B.

Question

It's possible for Bob to win on both of the maps shown, but only if Alice makes a mistake; if she plays correctly, she wins or draws as demonstrated.

Is there a map where Bob can guarantee a win?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Is the number of regions finite? $\endgroup$
    – DL33
    Commented Nov 1 at 21:52
  • $\begingroup$ @DL33. I would think so, otherwise the game will never end, so there’s no winning $\endgroup$
    – Pranay
    Commented Nov 1 at 21:56
  • 1
    $\begingroup$ @Pranay not necessarily, they could agree to have 1 minute of thinking time and cut it in half every round, this way they could cover a countable inifinity of regions in 4 minutes. The reason I'm asking is that I have a solution for this case $\endgroup$
    – DL33
    Commented Nov 1 at 21:59
  • 3
    $\begingroup$ @DL33 Good question! Yes, the map is finite. Playing on an infinite map is an interesting idea, perhaps while posing a different question. $\endgroup$
    – noedne
    Commented Nov 1 at 22:27

1 Answer 1

Reset to default
40
$\begingroup$

Yes, e.g.

enter image description here
If Alice chooses green, Bob can choose the opposing red and get 2 green. If Alice chooses red, Bob can choose an adjacent green and get 2 green. Bob can thus score 9 points.

Improve this answer
$\endgroup$
6
  • 5
    $\begingroup$ For completeness: If Alice chooses yellow, Bob chooses the nearest green and gets 12 points. $\endgroup$
    – Tim C
    Commented Nov 1 at 23:19
  • $\begingroup$ Nice answer! Do you know if there's a map without "holes" where Bob can win? In your map, the region bounded by the red and green regions is a "hole" in the map. $\endgroup$
    – Pranay
    Commented Nov 1 at 23:24
  • 3
    $\begingroup$ @Pranay make the red and green regions triangles, then they can touch in the center with their vertices (judging from examples in the question, regions only touching with a vertex are not considered connected) $\endgroup$
    – DL33
    Commented Nov 1 at 23:43
  • $\begingroup$ @DL33. Ah yes, makes sense, thanks! $\endgroup$
    – Pranay
    Commented Nov 1 at 23:47
  • 5
    $\begingroup$ Actually, only one yellow is required at each end. Then the map can be drawn as a size-3 triangle divided into unit triangles. $\endgroup$
    – Florian F
    Commented Nov 2 at 10:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.