| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2017-10-27 14:00 「一山崩しのゲームと数論問題」の修正版 塚村善弘（元ソニー）・五十嵐善英・○藤田顕光・浦部裕太・山崎浩一（群馬大）  COMP2017-22 |
|
| 抄録 | （和） | ここで議論されるゲーム MSP(m) では、一山の石から2人のプレイヤーが交互に1以上$m$以下の石を取り除いていく。各プレイヤーは、直前に取られた石の数と同じ個数の石を取り除くことが禁じられている。最後に石を取りきったプレイヤーは勝ちとし、石が残っているのに禁じ規則により石が取れない場合は、相手のプレイヤーの勝ちとする。以前の報告[Games with a Single Pile of Stones and Number Theoretic Problems, COMP2016-17 pp.17-24]で、先手、後手の何れが勝ちであるかを判定できるように、初期に置かれた石の数を定式化した。その報告の中に誤りがあったので、本報告でそれらの誤りを修正し、新しい結果も加えた。MSP(m) のタイプを $1, 2, ..., k, k + 1, ...$に分類し、各タイプについて、後手が必勝になる石の数のほとんどは、同じ形の規則的な周期性を示すが、そのような規則性から外れる周期性もありうることを示す。各正整数$k$について、タイプ番号が$k$であり、後手必勝になる初期の石の個数が同じ形の規則的な周期性を示すような$m$は無限個あることも示す。 |
| （英） | 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. | |
| キーワード | （和） | 一山崩し / アルゴリズム / ゲーム / 数論 / 禁じ手 / 戦略 / / |
| （英） | a pile of stones / algorithms / games / number theory / prohibition / strategies / / | |
| 文献情報 | 信学技報, vol. 117, no. 269, COMP2017-22, pp. 13-20, 2017年10月. | |
| 資料番号 | COMP2017-22 | |
| 発行日 | 2017-10-20 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2017-22 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2017-10-27 - 2017-10-27 |
| 開催地（和） | 成蹊大学 |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2017-10-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | 「一山崩しのゲームと数論問題」の修正版 |
| サブタイトル（和） | |
| タイトル（英） | A Revised Version of "Games with a Single Pile of Stones and Number Theoretic Problems" |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 一山崩し / a pile of stones |
| キーワード(2)（和/英） | アルゴリズム / algorithms |
| キーワード(3)（和/英） | ゲーム / games |
| キーワード(4)（和/英） | 数論 / number theory |
| キーワード(5)（和/英） | 禁じ手 / prohibition |
| キーワード(6)（和/英） | 戦略 / strategies |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 塚村 善弘 / Yoshihiro Tsukamura / ツカムラ ヨシヒロ |
| 第1著者 所属（和/英） | 元ソニー (略称： 元ソニー) former Sony Corporation (略称： former Sony) |
| 第2著者 氏名（和/英/ヨミ） | 五十嵐 善英 / Yoshihide Igarashi / イガラシ ヨシヒデ |
| 第2著者 所属（和/英） | 群馬大学 (略称： 群馬大) Gunma University (略称： Gunma Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 藤田 顕光 / Takaaki Fujita / フジタ タカアキ |
| 第3著者 所属（和/英） | 群馬大学 (略称： 群馬大) Gunma University (略称： Gunma Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 浦部 裕太 / Yuta Urabe / ウラベ ユウタ |
| 第4著者 所属（和/英） | 群馬大学 (略称： 群馬大) Gunma University (略称： Gunma Univ.) |
| 第5著者 氏名（和/英/ヨミ） | 山崎 浩一 / Koichi Yamazaki / ヤマザキ コウイチ |
| 第5著者 所属（和/英） | 群馬大学 (略称： 群馬大) Gunma University (略称： Gunma Univ.) |
| 講演者 | 第3著者 |
| 発表日時 | 2017-10-27 14:00:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2017-22 |
| 巻番号（vol） | vol.117 |
| 号番号（no） | no.269 |
| ページ範囲 | pp.13-20 |
| ページ数 | 8 |
| 発行日 | 2017-10-20 (COMP) |
[研究会発表申込システムのトップページに戻る]