tailieunhanh - Báo cáo toán học: "Periodicity and Other Structure in a Colorful Family of Nim-like Arrays"

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: Periodicity and Other Structure in a Colorful Family of Nim-like Arrays. | Periodicity and Other Structure in a Colorful Family of Nim-like Arrays Lowell Abrams Department of Mathematics The George Washington University Washington DC 20052 . labrams@ Dena S. Cowen-Morton Department of Mathematics Xavier University Cincinnati OH 45207-4441 . morton@ Submitted May 21 2009 Accepted Jul 13 2010 Published Jul 20 2010 Mathematics Subject Classification 68R15 91A46 Abstract We study aspects of the combinatorial and graphical structure shared by a certain family of recursively generated arrays related to the operation of Nim-addition. In particular these arrays display periodic behavior along rows and diagonals. We explain how various features of computer-generated graphics depicting these arrays are reflections of the theorems we prove. Keywords Nim Sprague-Grundy periodicity sequential compound 1 Introduction The game of Nim is a two-person combinatorial game consisting of one or more piles of stones in which the players alternate turns removing any number of stones they wish from a single pile of stones the winner is the player who takes the last stone. The direct sum G1 G2 of two combinatorial games G1 G2 is the game in which a Partially supported by The Johns Hopkins University s Acheson J. Duncan Fund for the Advancement of Research in Statistics THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R103 1 player on their turn has the option of making a move in exactly one of the games G1 or G2 which are not yet exhausted in Nim this simply means having several independent piles of stones . Again the winner is the last player to make a move. The importance of Nim was established by the Sprague-Grundy Theorem 14 24 also developed in 7 chapter 11 which essentially asserts that Nim is universal among finite impartial two-player combinatorial games in which the winner is the player to move last. Briefly that is to say that every such game G is vis-a-vis direct sum equivalent to a single-pile Nim game we write G for the size