Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.03088 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918153819258880 |
|---|---|
| author | Inoue, Hiyu Kimura, Shun-ichi Manabe, Hikaru Suetsugu, Koki Yamashita, Takahiro Yoshiwatari, Kanae |
| author_facet | Inoue, Hiyu Kimura, Shun-ichi Manabe, Hikaru Suetsugu, Koki Yamashita, Takahiro Yoshiwatari, Kanae |
| contents | {\sc Yama Nim} is a variant of two piles {\sc Nim}. In this ruleset, the player chosses one of the piles and removes at least two tokens from the pile. In the same move, the player adds one token to the other pile. We show the winning strategies and SG-values of this ruleset.
In addition, we introduce a generalization of {\sc Yama Nim}, named {\sc Digraph Yama Nim}. In this ruleset, a digraph is given and there are some tokens on each vertex of the digraph. Each player, in their turn, chooses one vertex and removes at least its out-degree plus one tokens from the vertex. Furthermore, one token is added to each vertex to which a directed edge from the chosen vertex is connected. We show that the winner determination problem of {\sc Digraph Yama Nim} is PSPACE-complete even when the input graph is bipartite and directed acyclic. Despite this, there are some cases that can be solved easily and we show them. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_03088 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Digraph Yama Nim Inoue, Hiyu Kimura, Shun-ichi Manabe, Hikaru Suetsugu, Koki Yamashita, Takahiro Yoshiwatari, Kanae Combinatorics {\sc Yama Nim} is a variant of two piles {\sc Nim}. In this ruleset, the player chosses one of the piles and removes at least two tokens from the pile. In the same move, the player adds one token to the other pile. We show the winning strategies and SG-values of this ruleset. In addition, we introduce a generalization of {\sc Yama Nim}, named {\sc Digraph Yama Nim}. In this ruleset, a digraph is given and there are some tokens on each vertex of the digraph. Each player, in their turn, chooses one vertex and removes at least its out-degree plus one tokens from the vertex. Furthermore, one token is added to each vertex to which a directed edge from the chosen vertex is connected. We show that the winner determination problem of {\sc Digraph Yama Nim} is PSPACE-complete even when the input graph is bipartite and directed acyclic. Despite this, there are some cases that can be solved easily and we show them. |
| title | Digraph Yama Nim |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2510.03088 |