TAILIEUCHUNG - Báo cáo toán học: "Aperiodic Subtraction Games"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Aperiodic Subtraction Games. | Aperiodic Subtraction Games Aviezri S. Fraenkel Department of Computer Science and Applied Mathematics Weizmann Institute of Science Rehovot 76100 Israel Submitted Apr 30 2011 Accepted Aug 1 2011 Published Aug 26 2011 Mathematics Subject Classification 91A46 91A05 11B75 68Q25 To Doron Zeilberger at 60 Ekhad and Maple .and a threefold cord is not quickly broken Ecclesiastes 4 12 . Abstract Periodicity is a fundamental property of many combinatorial games. It is sought vigorously yet remains elusive in important cases such as for some octal games notably Grundy s game. Periodicity is important because it provides poly-time winning strategies for many games. In particular subtraction games impartial and partizan have been proved to be periodic. Our main purpose here is to exhibit constructively a class of subtraction games which is demonstratively aperiodic and yet is shown to have linear-time winning strategies. Keywords Combinatorial games Complementary sequences Numeration systems Complexity Aperiodicity 1 Prologue Throughout we deal with two-player impartial games where the two players move alternately. We are mainly concerned with normal play but we consider misere play in Section 4. Normal play means that the player first unable to move loses and the opponent wins. In misere play the outcome is reversed the player making the last move loses and the opponent wins. In the theory of impartial combinatorial games the notion of periodicity or its extension is central. Thus octal games have a poly-time winning strategy if the Sprague-Grundy function - to be discussed in Section 3 - is periodic 2 . The question whether certain octal games are periodic is still open. The most famous among them is Grundy s game given a pile of tokens divide it into two unequal parts. The player first unable to play because fraenkel@ http fraenkel THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2 2011 P19 1 all piles have size 2 loses and the .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học