# A gold-grabbing game

 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 and for every vertex a non-negative integer which we think of as the amount of gold at .

2-Player game Players alternate turns. On each turn, a player chooses a leaf vertex of the tree, takes the gold at this vertex, and then deletes . 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 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.

### Not an open problem in the strict sense

There exists an obvious algorithm which just enumerates all variants.

The problem seems to mean to find a more efficient algorithm. This is not a strict formulation because it is not strictly defined what is "more efficient".

I suggest to rip this problem, such as to put it into Second tier problems.

--
Victor Porton - http://www.mathematics21.org

## Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.