Presentation | 2016-09-06 Games with a Single Pile of Stones and Number Theoretic Problems Yoshihiro Tsukamura, Yoshihide Igarashi, Yuta Urabe, Koichi Yamazaki, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | The game discussed in this paper is played alternately by two players, removing at least one and at most m stones from the single pile of stones at each turn. Each player is prohibited from taking the same number of stones as the number of stones taken by the opponent at the immediately previous turn. A player who makes the pile empty wins the game. Furthermore, when a player cannot take any number of stones from the non-empty pile due to the prohibition rule, the opponent becomes the winner. This game is denoted by MSP(m). We formulate the initial numbers of stones at the pile such that one player of MSP(m) is promised to become the winner. According to the formula we categorize MSP(m)’s into types 1,2,3,··· ,k,k + 1,···. We give an algorithm for deciding the type number of MSP(m) for any given m. We prove that for any positive integer k, there exists a positive integer m such that the type number of MSP(m) is k. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | a pile of stones / algorithms / games / number theory / prohibition / strategies |
Paper # | COMP2016-17 |
Date of Issue | 2016-08-30 (COMP) |
Conference Information | |
Committee | COMP |
---|---|
Conference Date | 2016/9/6(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | Toyama Prefectural University |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | Hiroo Itoh(Univ. of Electro-Comm.) |
Vice Chair | Yuushi Uno(Osaka Pref. Univ.) |
Secretary | Yuushi Uno(Seikei Univ.) |
Assistant |
Paper Information | |
Registration To | Technical Committee on Theoretical Foundations of Computing |
---|---|
Language | ENG |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Games with a Single Pile of Stones and Number Theoretic Problems |
Sub Title (in English) | |
Keyword(1) | a pile of stones |
Keyword(2) | algorithms |
Keyword(3) | games |
Keyword(4) | number theory |
Keyword(5) | prohibition |
Keyword(6) | strategies |
1st Author's Name | Yoshihiro Tsukamura |
1st Author's Affiliation | Sony Corporation OB(SONY) |
2nd Author's Name | Yoshihide Igarashi |
2nd Author's Affiliation | Gunma University(Gunma Univ.) |
3rd Author's Name | Yuta Urabe |
3rd Author's Affiliation | Gunma University(Gunma Univ.) |
4th Author's Name | Koichi Yamazaki |
4th Author's Affiliation | Gunma University(Gunma Univ.) |
Date | 2016-09-06 |
Paper # | COMP2016-17 |
Volume (vol) | vol.116 |
Number (no) | COMP-211 |
Page | pp.pp.17-24(COMP), |
#Pages | 8 |
Date of Issue | 2016-08-30 (COMP) |