TRGAME - Editorial

PROBLEM LINK:
Practice

Author: Jatin Yadav
Tester: tncks0121

DIFFICULTY:
Medium

PREREQUISITES:
Basic game theory, Mathematics

PROBLEM:

There’s a tree and two players Alice and Bob. They play a game on this tree taking turns alternatively starting with Alice. In their turn, a player removes a leaf from the tree. Alice wants vertex x to be the last one remaining while Bob doesn’t want x to be the last vertex remaining.

For each choice of x, find who wins if both play optimally.

QUICK EXPLANATION:

Alice wins if and only if n is even and the size of the largest tree obtained on removing x is \leq \frac{n}{2}.

Explanation:

If n is odd, Bob must win irrespective of the tree structure. This is because when there are two nodes left in the tree, it must be Bob’s turn and he can remove vertex x if it hasn’t been removed already. So, he can force x to not be the last vertex remaining and win the game.

Consider n even now. Root the tree at x. Let S_1, S_2, \ldots, S_k be the subtrees of the children of x in decreasing order of size. Let m = |S_1| be the maximum size among these subtrees.

Claim : Alice wins if and only if 2m \leq n.

Proof:

One side of the proof is trivial. If 2 m > n, Bob can keep removing from a subtree other than S_1. Doing this, he ensures that there comes a point in the game when all subtrees other than S_1 are emptied and x has only one child left, and hence is a leaf. At this point, Bob can remove x to win the game.

Lets prove the other side using induction on n.

If n = 2, the only possibility is m = 1 and 2 m \leq n. Here, Alice wins the game by removing the vertex other than x

Else, let m' be the maximum subtree size on the next turn of Alice. Clearly, m' \leq m. There are two cases (note that 2m \neq n - 1 as n is even):

  • If 2 m \leq n - 2, then 2 m' \leq 2m \leq n - 2. So, the condition is also satisfied in the next turn and by induction, Alice wins.

  • If 2m = n, S_1 must be the only subtree with size m, as the sum of remaining subtrees is n - 1 - m = m - 1. Removing a leaf from S_1 will make sure that m' \leq m - 1 and 2m' \leq n - 2. Again, the condition is satisfied in the next turn, and by induction, Alice wins.

AUTHOR’S and TESTER’S codes:

The author’s code can be found here
The tester’s code can be found here

2 Likes