کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648936 1632446 2007 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the misere version of game Euclid and miserable games
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On the misere version of game Euclid and miserable games
چکیده انگلیسی

Recently, Gabriel Nivasch got the following remarkable formula for the Sprague–Grundy function of game Euclid: g+(x,y)=⌊|x/y-y/x|⌋g+(x,y)=⌊|x/y-y/x|⌋ for all integers x,y⩾1x,y⩾1. We consider the corresponding misere game and show that its Sprague–Grundy function g-(x,y)g-(x,y) is equal to g+(x,y)g+(x,y) for all positions (x,y)(x,y), except for the case when (x,y)(x,y) or (y,x)(y,x) equals (kFi,kFi+1)(kFi,kFi+1), where FiFi is the ith Fibonacci number and k is a positive integer. It is easy to see that these exceptional Fibonacci   positions are exactly those in which all further moves in the game are forced (unique) and hence, the results of the normal and misere versions are opposite; in other words, for these positions g+g+ and g-g- take values 0 and 1 so that g-=1-g+=(-1)i+1+g+g-=1-g+=(-1)i+1+g+.Let us note that the good old game of Nim has similar property: if there is at most one bean in each pile then all further moves are forced. Hence, in these forced   positions the results of the normal and misere versions are opposite, while for all other positions they are the same, as it was proved by Charles Bouton in 1901. Respectively, in the forced positions g+g+ and g-g- take values 0 and 1 so that g-=1-g+=(-1)i+1+g+g-=1-g+=(-1)i+1+g+, where i   is the number of non-empty piles, while in all other positions g+≡g-g+≡g-.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issues 9–10, 6 May 2007, Pages 1199–1204
نویسندگان
,