4
$\begingroup$

Given $2n$ people in a room where each pair is either friends or strangers, two players take turns picking a person such that the person chosen is a friend of the person previously picked. The player who cannot make a move loses. Determine a winning strategy for one of the players.

What I think,

Let A and B be the first and second player respectively.

Each vertex of Graph G represents the person and two vertices are connected if they are friends.

A wins if the graph has two connected edges, three connected edges in a triangle.

B wins if the graph has one edge, three connected edges in a line.

$\endgroup$
7
  • 1
    $\begingroup$ Are there any limitations to which friend they can pick (like not picking someone who has been picked before, or not use the same friendship more than once), or could they end up going in a loop indefinitely? Would the game just continue in that case, or be considered a draw? $\endgroup$
    – Arthur
    Sep 20 '17 at 7:29
  • $\begingroup$ somewhat related to ramsey theorem, i think $\endgroup$
    – vidyarthi
    Sep 20 '17 at 7:29
  • $\begingroup$ @ Arthur. I think, not picking someone who has been picked before. $\endgroup$
    – Dan
    Sep 20 '17 at 7:35
  • $\begingroup$ Do they start at an arbitrary person, or do $A$ or $B$ get to define a starting point (and in that case who)? $\endgroup$
    – Arthur
    Sep 20 '17 at 8:35
  • $\begingroup$ It is still unclear whether the player A (or B) gets to choose the starting vertex or it is fixed in advance. $\endgroup$
    – Adayah
    Sep 20 '17 at 10:00
4
$\begingroup$

Hint: if there is a perfect matching of the graph, B wins. Otherwise A wins.


Edit: in response to an extended discussion below, aiming to settle the precise statement of the problem, I will try to provide a more robust solution.

Case 1: Player A gets to choose the starting vertex, then B chooses an adjacent vertex and the game continues.

  • Suppose there is a perfect matching. Then no matter which vertex A chooses, B can go along an edge to a matched vertex and continue this way, so he will always be able to make a move.

  • Now suppose there is no perfect matching. Then A can find any maximum matching, then pick an unmatched vertex and use the strategy of B above, i.e. to always pick the vertex matched with the vertex chosen by B. This way A will win, for if B could at one time pick an unmatched vertex, the path traversed throughout the game would form an augmenting path, but such a path never exists in a maximum matching.

Case 2: The starting vertex $u \in G$ is arbitrarily fixed and A plays first by choosing a friend of $u$.

  • Suppose there is a maximum matching omitting $u$. Then the winning strategy for B is analogous to the one in the case 1.

  • Suppose on the contrary that every maximum matching involves $u$. Then A can pick any maximum matching and play as before, i.e. always choose a vertex matched to the one chosen by B. It is always possible: if B could once choose an unmatched vertex $v$, the traversed path would be an alternating path beginning in $u$ and ending in $v$. By shifting the edges along that path we produce a maximum matching omitting $u$, which was assumed to be impossible. So A wins.

Case 3: We are at a fixed vertex $u \in G$ at some point in a game in progress. Since the already used vertices are no longer of use to us, we can remove them from $G$, thereby reducing the case to the previous one.

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. It seemed to me that your discussion had reached a satisfactory conclusion, so I relocated the exchange. You can still revisit those comments in the linked chatroom. If you dearly want something left visible here, please explain what, and flag again or @-ping me. $\endgroup$ Sep 24 '17 at 6:23

Your Answer

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

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