Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/dubna/2009/notes/dehornoy/MotivationalExercises.pdf Дата изменения: Sun Jul 19 23:34:19 2009 Дата индексирования: Sat Oct 17 10:07:47 2009 Кодировка: Поисковые слова: south pole

Combinatorial Game Theory: Motivation Exercises Pierre Dehornoy
We are dealing with two-players games, with full information, and no luck. Players play alternatively. From any position, each player has several options (not necessarily the same) leading to new positions. He chooses one and only one of them, then the other player plays. We consider only games which always stop. Exercise 1. Given a position of game and a beginning player. One of the two player has always a winning strategy, i.e. whatever his opponent plays, he can always win the game. Rules (partizan Hackenbush). Positions: a finite numbers of bLue and Red edges, each of which is connected to the ground by a path; Moves: Left (resp. Right) cuts exactly one of the bLue (Red) edges. After that, each edge (bLue or Red) which is not any more connected to the ground disappears; Loser: If there is no more edge of its color when he has to play, a player loses. Example. Here is a starting position, and a sequence of moves. After the seventh move, Right has no more Red edge to cut, so he loses.
1 5 7 4 3 6 2

Red cannot play, therefore he loses!

Exercise 2. Who wins in the following situations i) if Left starts? ii) if Right starts?
1


2

Exercise 3. Given a position of Hackenbush, the first player never has a winning strategy, i.e. either Left wins, either Right wins, either the second player wins. Exercise 4. Suppose that H is a starting position in which the second player has a winning strategy. Then for any other starting position G, the winner starting at position G H is the same as the winner of G. Rules (non partizan Hackenbush). Positions: a finite numbers of green edges, each of which is connected to the ground by a path; Moves: At his turn, a player cuts exactly one of the green edges. After that, each remaining edge which is not any more connected to the ground disappears; Loser: If there is no more edge when he has to play, a player loses. Exercise 5. Who wins in the following situations?