| Presentation | 2017-10-27 A Revised Version of "Games with a Single Pile of Stones and Number Theoretic Problems" Yoshihiro Tsukamura, Yoshihide Igarashi, Takaaki Fujita, Yuta Urabe, Koichi Yamazaki, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The game MSP(m) discussed in this paper, is played alternately by two players, removing at least one stone and at most $m$ stones from the single pile at each turn. Each player is prohibited from removing the same number of stones as the number of stones removed by the opponent at the immediately previous turn. A player who makes the pile empty wins the game. Furthermore, when a player cannot remove any number of stones due to the prohibition rule, the opponent becomes the winner. This game is denoted by MSP(m). In our previous report [Games with a Single Pile of Stones and Number Theoretic Problems, COMP2016-17 pp.17-24], we formulated the initial numbers of stones, called unsafe number of stones, at the pile such that the second player of MSP(m) is promised to become the winner. However, we discovered that there were some serious errors in the previous report. In this paper, we remove the errors in the previous one, and add some new results. We categorize MSP(m)s into types $1, 2, 3, ..., k, k + 1, ...$ according to certain properties of $m$'s. Then for each type of MSP(m)'s we investigate the periodicity of unsafe numbers. For vast majority of MSP(m)'s, from the periodicity we can efficiently decide which player is promised to become the winner of the game with a given initial number of stones. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | a pile of stones / algorithms / games / number theory / prohibition / strategies |
| Paper # | COMP2017-22 |
| Date of Issue | 2017-10-20 (COMP) |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2017/10/27(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Hiro Ito(Univ. of Electro-Comm.) |
| Vice Chair | Yushi Uno(Osaka Pref. Univ.) |
| Secretary | Yushi Uno(Seikei Univ.) |
| Assistant | |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Revised Version of "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 | former Sony Corporation(former Sony) |
| 2nd Author's Name | Yoshihide Igarashi |
| 2nd Author's Affiliation | Gunma University(Gunma Univ.) |
| 3rd Author's Name | Takaaki Fujita |
| 3rd Author's Affiliation | Gunma University(Gunma Univ.) |
| 4th Author's Name | Yuta Urabe |
| 4th Author's Affiliation | Gunma University(Gunma Univ.) |
| 5th Author's Name | Koichi Yamazaki |
| 5th Author's Affiliation | Gunma University(Gunma Univ.) |
| Date | 2017-10-27 |
| Paper # | COMP2017-22 |
| Volume (vol) | vol.117 |
| Number (no) | COMP-269 |
| Page | pp.pp.13-20(COMP), |
| #Pages | 8 |
| Date of Issue | 2017-10-20 (COMP) |