一般化されたヨセフスの問題と Maxニム

• Item type: Symposium(1)
• 公開日: 2024-11-15
• タイトル: 一般化されたヨセフスの問題と Maxニム
• タイトル / 言語: en
• タイトル: Generalized Josephus problem and maximum nim
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: ヨセフスの問題
• キーワード / 主題Scheme: Other
• キーワード / 主題: Max ニム
• キーワード / 主題Scheme: Other
• キーワード / 主題: グランディ数
• キーワード / 主題Scheme: Other
• キーワード / 主題: 組合せゲーム理論
• キーワード / 主題Scheme: Other
• キーワード / 主題: 不偏ゲーム
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 啓明学院高等学校
• 著者所属: 啓明学院高等学校
• 著者所属: 早稲田大学
• 著者所属: 慶應義塾大学
• 著者所属(英): en
• 著者所属(英): Keimei Gakuin Junior and Senior High School
• 著者所属(英): en
• 著者所属(英): Keimei Gakuin Junior and Senior High School
• 著者所属(英): en
• 著者所属(英): Waseda University
• 著者所属(英): en
• 著者所属(英): Faculty of Environment and Information Studies, Keio University
• 著者名: 眞部, 光; 宮寺, 良平; 末續, 鴻輝; 高橋, 祥英
• 著者名(英): Hikaru, Manabe; Ryohei, Miyadera; Koki, Suetsugu; Shoei, Takahashi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ヨセフスの問題は，古くから知られている数学の問題であり，円形に並んだ n 人の人間を，起点からk 人目を順に消していき，最後に生き残るのはどの人間かを求めるものである．また， Max ニムは組合せゲーム理論で扱われるゲームの中で特に不偏ゲームに属するゲームであり，局面として石の山と関数 f（本稿では制約関数と呼ぶ）が与えられ、それぞれの手番でその時点での山の石の総数 x に対して高々 f(x)個まで石を取り合い，着手ができなくなった方が負けとなるゲームである．これまで， f(x) = ⌊x/k ⌋ となる関数によって定義される Max ニムのグランディ数と k 人目を消していくヨセフスの問題の関係が知られていた．本研究ではこの対応関係を一般化し，飛ばす人数が一定でないヨセフスの問題に対しても対応する Max ニムが定義できること，並びに任意の広義単調増加な制約関数で定義される Max ニムに対して，対応するヨセフスの問題の飛ばし人数順が存在することを示し，さらに具体的な構成方法も示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Josephus problem is an old problem in mathematics: there are n persons in a circle, we start from a person and continue to remove every k-th person until only one person survives, then, how we can find the survivor from the initiate position? Also, max nim is a combinatorial game, which is impartial. In this ruleset, a pile of stones is given as a position and also restrict function f is given. The current player can remove at most f(x) stones, where x is the number of stones in the pile. The player who cannot make a move is the loser. So far, a relationship between max nim defined by f(x) = ⌊x/k⌋ and Josephus problem in which every k-th person is removed has already shown. In this study, we generalize this relationship and show that we can define restrict function for max nim corresponds to a Josephus problem in which the number of skipped person is not a constant, and we can define the sequence of skipped persons of the Josephus problem corresponding to the max nim defined by given weakly increasing function. We show a concrete method to obtain such restricted function and sequence of skipped persons.
• 書誌情報: ゲームプログラミングワークショップ2024論文集; 巻 2024, p. 32-39, 発行日 2024-11-15
• 出版者 / 言語: ja
• 出版者: 情報処理学会