Open Problem Garden - A gold-grabbing game - Comments

Not an open problem in the strict sense (re: A gold-grabbing game)

porton — Sun, 04 Oct 2009 01:38:53 +0200

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

A gold-grabbing game

mdevos — Fri, 02 Oct 2009 15:57:29 +0200

Author(s): Rosenfeld

Subject: Graph Theory » Graph Algorithms

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.