Home » Subject » Graph Theory » Graph Algorithms

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 $ 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.
add new comment

Not an open problem in the strict sense

On October 4th, 2009 porton says:

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

reply

Comment viewing options

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