Home » Subject » Graph Theory » Graph Algorithms
Importance: Medium ✭✭
Author(s): Rosenfeld, Moshe
Subject: Graph Theory
» Graph Algorithms
Keywords: game
tree
Recomm. for undergrads: no
Posted by: mdevos
on: October 2nd, 2009

Setup Fix a tree $ T $ and for every vertex $ v \in V(T) $ a non-negative integer $ g(v) $ which we think of as the amount of gold at $ v $.

2-Player game Players alternate turns. On each turn, a player chooses a leaf vertex $ v $ of the tree, takes the gold at this vertex, and then deletes $ v $. The game ends when the tree is empty, and the winner is the player who has accumulated the most gold.

Problem   Find optimal strategies for the players.

In the special case when $ T $ is a path of even length, the first player can ensure that she chooses either all of the even vertices, or all of the odd vertices. Thus, player 1 should never finish with less than player 2, and whenever the total gold on the odd vertices and the total gold on the even vertices are not equal, there is a winning strategy for player 1.

Bibliography



* indicates original appearance(s) of problem.
1 comment

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options