Gra w zjadanie drzew

Dwoje graczy gra w grę na ukorzenionym drzewie z rzeczywistymi wagami na każdym wierzchołku. Gracze na przemian zabierają po jednym liściu z drzewa, gromadząc ich wagi. Korzeń musi być wzięty ostatni. Każdy gracz chce zmaksymalizować sumę zgromadzonych przez siebie wag. Wartość takiej gry jest zdefiniowana jako różnica sumy wag zebranych przez pierwszego gracza i sumy wag zebranych przez drugiego gracza. Opisujemy algorytm stworzony przez Bartosza Walczaka, który przypuszczalnie oblicza wartość tej gry, i przeprowadzamy wyczerpujące poszukiwanie kontrprzykładu. Dowodzimy, że jeśli kontrprzykład istnieje, to jest to drzewo zawierające co najmniej 16 wierzchołków.

Two players are playing a game on a rooted tree with real weights on vertices. The players take turns grabbing leaves of the tree, one by one, and collecting their weights. The root has to be taken last. Each player wants to maximize the sum of the weights they collected. The value of this game is defined as the sum of the weights collected by the player who starts minus the sum of the weights collected by the other player. We describe an algorithm developed by Bartosz Walczak, which is conjectured to compute the value of this game, and we perform an exhaustive search for a counterexample. We prove that, if a counterexample exists, it has to be a tree on at least 16 vertices.