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