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í toán học quốc tế đề tài: Playing Nim on a simplicial complex. | Playing Nim on a simplicial complex Richard Ehrenborg Department of Mathematics White Hall Cornell University Ithaca NY 14853-7901 USA jrge@ Einar Steingrimsson Matematiska institutionen Chalmers Tekniska Hogskola Goteborgs universitet S-412 96 Goteborg Sweden einar@ Received December 12 1995 Accepted March 6 1996 Abstract We introduce a generalization of the classical game of Nim by placing the piles on the vertices of a simplicial complex and allowing a move to affect the piles on any set of vertices that forms a face of the complex. Under certain conditions on the complex we present a winning strategy. These conditions are satisfied for instance when the simplicial complex consists of the independent sets of a binary matroid. Moreover we study four operations on a simplicial complex under which games on the complex behave nicely. We also consider particular complexes that correspond to natural generalizations of classical Nim. Mathematics Subject Classification 90D05 90D43 90D44 90D46. Partially supported by a grant from the Icelandic Council of Science THE ELECTRONIC .JOURNAL OF COMBINATORICS 3 1996 R9 2 1 Introduction One of the classical games - perhaps the classical game - in mathematics is the game of Nim. It is a two player game played as follows. A set of piles of chips is given. The players take turns removing chips. In a move a player removes any positive number of chips from one pile. The winner is the player who takes the last chip. An elegant winning strategy for this game was hrst described by Bouton 2 . By virtue of the simplicity of this strategy Nim has since served as a yardstick for all impartial two-player games see 1 3 in the sense that any position in such a game is equivalent to a position in Nim. In this paper we generalize the game of Nim to a hnite simplicial complex A. Note that in accordance with the following dehnition a simplicial complex is taken to be hnite throughout the paper. Definition A .
