Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Sprague-Grundy function for some selective compound games
108
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We analyze the Sprague-Grundy functions for a class of almost disjoint selective compound games played on Nim heaps. Surprisingly, we find that these functions behave chaotically for smaller Sprague-Grundy values of each component game yet predictably when any one heap is sufficiently large.
rate research
Read More
For a collection of papers in memory of Elwyn Berlekamp (1940-2019), John Conway (1937-2020), and Richard Guy (1916-2020). The Sprague-Grundy theory for finite games without cycles was extended to general finite games by Cedric Smith and by Aviezri Fraenkel and coauthors. We observe that the same framework used to classify finite games also covers the case of locally finite games (that is, games where any position has only finitely many options). In particular, any locally finite game is equivalent to some finite game. We then study cases where the directed graph of a game is chosen randomly, and is given by the tree of a Galton-Watson branching process. Natural families of offspring distributions display a surprisingly wide range of behaviour. The setting shows a nice interplay between ideas from combinatorial game theory and ideas from probability.
The concept of nimbers--a.k.a. Grundy-values or nim-values--is fundamental to combinatorial game theory. Nimbers provide a complete characterization of strategic interactions among impartial games in their disjunctive sums as well as the winnability. In this paper, we initiate a study of nimber-preserving reductions among impartial games. These reductions enhance the winnability-preserving reductions in traditional computational characterizations of combinatorial games. We prove that Generalized Geography is complete for the natural class, $cal{I}^P$ , of polynomially-short impartial rulesets under nimber-preserving reductions, a property we refer to as Sprague-Grundy-complete. In contrast, we also show that not every PSPACE-complete ruleset in $cal{I}^P$ is Sprague-Grundy-complete for $cal{I}^P$ . By considering every impartial game as an encoding of its nimber, our technical result establishes the following striking cryptography-inspired homomorphic theorem: Despite the PSPACE-completeness of nimber computation for $cal{I}^P$ , there exists a polynomial-time algorithm to construct, for any pair of games $G_1$, $G_2$ of $cal{I}^P$ , a prime game (i.e. a game that cannot be written as a sum) $H$ of $cal{I}^P$ , satisfying: nimber($H$) = nimber($G_1$) $oplus$ nimber($G_2$).
Let $S$ be a set of positive integers, and let $D$ be a set of integers larger than $1$. The game $i$-Mark$(S,D)$ is an impartial combinatorial game introduced by Sopena (2016), which is played with a single pile of tokens. In each turn, a player can subtract $s in S$ from the pile, or divide the size of the pile by $d in D$, if the pile size is divisible by $d$. Sopena partially analyzed the games with $S=[1, t-1]$ and $D={d}$ for $d otequiv 1 pmod t$, but left the case $d equiv 1 pmod t$ open. We solve this problem by calculating the Sprague-Grundy function of $i$-Mark$([1,t-1],{d})$ for $d equiv 1 pmod t$, for all $t,d geq 2$. We also calculate the Sprague-Grundy function of $i$-Mark$({2},{2k + 1})$ for all $k$, and show that it exhibits similar behavior. Finally, following Sopenas suggestion to look at games with $|D|>1$, we derive some partial results for the game $i$-Mark$({1}, {2, 3})$, whose Sprague-Grundy function seems to behave erratically and does not show any clean pattern. We prove that each value $0,1,2$ occurs infinitely often in its SG sequence, with a maximum gap length between consecutive appearances.
The edit distance function of a hereditary property $mathscr{H}$ is the asymptotically largest edit distance between a graph of density $pin[0,1]$ and $mathscr{H}$. Denote by $P_n$ and $C_n$ the path graph of order $n$ and the cycle graph of order $n$, respectively. Let $C_{2n}^*$ be the cycle graph $C_{2n}$ with a diagonal, and $widetilde{C_n}$ be the graph with vertex set ${v_0, v_1, ldots, v_{n-1}}$ and $E(widetilde{C_n})=E(C_n)cup {v_0v_2}$. Marchant and Thomason determined the edit distance function of $C_6^{*}$. Peck studied the edit distance function of $C_n$, while Berikkyzy et al. studied the edit distance of powers of cycles. In this paper, by using the methods of Peck and Martin, we determine the edit distance function of $C_8^{*}$, $widetilde{C_n}$ and $P_n$, respectively.
In order to provide a unified combinatorial interpretation of congruences modulo $5$ for 2-colored partition functions, Garvan introduced a bicrank statistic in terms of weighted vector partitions. In this paper, we obtain some inequalities between the bicrank counts $M^{*}(r,m,n)$ for $m=2$, $3$ and $4$ via their asymptotic formulas and some $q$-series techniques. These inequalities are parallel to Andrews and Lewis results on the rank and crank counts for ordinary partitions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
