Search

Given integers n , k , ℓ such that 0 < k < n , 1 < ℓ and an integer vector x = (x 1 , ... , x n) , denote by m = m (x) the number of entries of x that are multiple of ℓ. Choose n − k entries of x as follows: if m (x) ≥ n − k , take n − k smallest entries of x that are multiple of ℓ ; if n − k > m (x) , take all m such entries, if any, and add n − k − m largest entries of x. In one step, the chosen n − k entries (bears) keep their values, while the remaining k (bulls) are reduced by 1. Repeat such steps getting the sequence S = S (n , k , ℓ , x 0) = (x 0 → x 1 → ... → x j → ...). We prove that it is "quasi-periodic". More precisely, there exists a number N = N (n , k , ℓ , x 0) such that for all j ≥ N we have m (x j) ≥ n − k and r a n g e (x j) ≤ ℓ , where r a n g e (x) = max (x i ∣ i ∈ [ n ]) − min (x i ∣ i ∈ [ n ]) with [ n ] = { 1 , ... , n }. Furthermore, after N steps, the system "moves like a screw". Assuming that x 1 ≤ ⋯ ≤ x n , introduce the cyclical order on [ n ] considering 1 and n as neighbors. Then, bears and bulls partition [ n ] into two intervals that are shifted by k with every ℓ steps. Then, after every p = ℓ n / G C D (n , k) = ℓ L C M (n , k) / k steps all entries of x are reduced by the same value δ = p k / n , that is, x i j − x i j + p = δ for all i ∈ [ n ] and j ≥ N. We prove that N (n , k , ℓ , x 0) ≤ (ℓ + r a n g e (x 0)) ⌈ n / k ⌉ and give an algorithm computing N in time polynomial in n , k , ℓ , and log (1 + r a n g e (x 0)). Furthermore, x j , for any j ≥ 0 , can be computed in time polynomial in n , k , ℓ , log (1 + r a n g e (x 0)) , and log (1 + j). In case k = n − 1 and ℓ = 2 such screw dynamical system are applicable to impartial games; see Gurvich, Martynov, Maximchuk, and Vyalyi, "On Remoteness Functions of Exact Slow k -NIM with k + 1 Piles", https://arxiv.org/abs/2304.06498 (2023). [ABSTRACT FROM AUTHOR]

Accordingly to Duchet (1987), the first paper of convexity on general graphs, in english, is the 1981 paper "Convexity in graphs". One of its authors, Frank Harary, introduced in 1984 the first graph convexity games, focused on the geodesic convexity, which were investigated in a sequence of five papers that ended in 2003. In this paper, we continue this research line, extend these games to other graph convexities, and obtain winning strategies and complexity results. Among them, we obtain winning strategies for general convex geometries and winning strategies for trees from the Sprague-Grundy theory on impartial games. We also obtain the first PSPACE-hardness results on convexity games, by proving that the normal play and the misère play of the impartial hull game on the geodesic convexity is PSPACE-complete even in graphs with diameter two. [ABSTRACT FROM AUTHOR]

If a combinatorial game involves more than two players, the problem of coalitions arises. To avoid the problem, Shuo-Yen Robert Li analyzed three-player nim with the podium rule, that is, if a player cannot be last, he should try to be last but one. With that simplification, he proved that a disjunctive sum of nim piles is a P -position if and only if the sum modulo 3 of the binary representations of the piles is equal to zero. In this paper, we extend the result in order to understand the complete characterization of the outcome classes, the possible reductions of the game forms, the equivalence classes under the equality of games and related canonical forms. [ABSTRACT FROM AUTHOR]

In Chomp on graphs, two players alternatingly pick an edge or a vertex from a graph. The player that cannot move any more loses. The questions one wants to answer for a given graph are: Which player has a winning strategy? Can an explicit strategy be devised? We answer these questions (and determine the Nim-value) for the class of generalized Kneser graphs and for several families of Johnson graphs. We also generalize some of these results to the clique complexes of these graphs. Furthermore, we determine which player has a winning strategy for some classes of threshold graphs. [ABSTRACT FROM AUTHOR]

Timber is a two player game played on a directed graph, with a domino on each arc. The direction of an arc indicates the direction its domino can be toppled. Once a domino is toppled, it creates a chain reaction toppling all dominoes along that direction, and the player who topples the last domino wins. A P -position is an orientation of the edges of the graph where the second player can always force a win. A connected graph with a cycle has no P -position, thus Timber is a game studied in trees. We prove that a tree has a P -position if and only if the number of edges is even, which generalizes the existing characterization for paths and improves the performance of the existing algorithm to decide if an oriented tree with an odd number of arcs is a P -position. We contribute to the open problem of determining the number of P -positions of a tree. We compute the number of P -positions of three caterpillar infinite subclasses. Finally, we present a lower bound to the number of P -positions of an arbitrary caterpillar. [ABSTRACT FROM AUTHOR]

In an ordinal sum of two combinatorial games G and H , denoted by G : H , a player may move in either G (base) or H (subordinate), with the additional constraint that any move on G completely annihilates the component H . It is well-known that the ordinal sum does not depend on the form of its subordinate, but depends on the form of its base. In this work, we analyze G ( G : H ) where G and H are impartial forms, observing that the G -values are related to the concept of minimum excluded value of order k . As a case study, we introduce the ruleset oak , a generalization of green hackenbush . By defining the operation gin sum , it is possible to determine the literal forms of the bases in polynomial time. [ABSTRACT FROM AUTHOR]

Playing impartial games under the normal and misère conventions may differ a lot. However, there are also many “exceptions” for which the normal and misère Sprague–Grundyfunctions are very similar. The first such example, the game of Nim , was considered by Bouton as early as in 1901. In 1976 Conway introduced a large class of such games that he called tame games. Here we introduce a proper subclass, pet games, and a proper superclass, domestic games. For each of these three classes we provide efficiently verifiable characterizations. These games are closely related to another important subclass of the tame games introduced in 2007 by the first author and called miserable games. We show that tame, pet, and domestic games turn into miserable games by “slight modifications” of the definitions. We also show that the sum of miserable games is miserable and find several other classes that respect summation. The developed techniques allow us to prove that very many well-known impartial games fall into classes mentioned above. Such examples include all subtraction games, which are pet; game Euclid , which is miserable (and, hence, tame), as well as many versions of the Wythoff game and Nim , which may be miserable, pet, or domestic. [ABSTRACT FROM AUTHOR]

In this paper we analyze a recently proposed impartial combinatorial ruleset that is played on a permutation of the set n. We call this ruleset STIRLING SHAVE. A procedure utilizing the ordinal sum operation is given to determine the nim value of a given normal play position. Additionally, we enumerate the number of permutations of n which are P-positions. The formula given involves the Stirling numbers of the first-kind. We also give a complete analysis of the Misère version of STIRLING SHAVE using Conway’s genus theory. An interesting by-product of this analysis is insight into how the ordinal sum operation behaves in Misère Play. [ABSTRACT FROM AUTHOR]

Two players alternate moves in the following impartial combinatorial game: Given a finitely generated abelian group A, a move consists of picking some 0≠a∈A. The game then continues with the quotient group A/⟨a⟩. We prove that under the normal play rule, the second player has a winning strategy if and only if A is a square, i.e. A≅B×B for some abelian group B. Under the misère play rule, only minor modifications concerning elementary abelian groups are necessary to describe the winning situations. We also compute the nimbers, i.e. Sprague-Grundy values of 2-generated abelian groups. An analogous game can be played with arbitrary algebraic structures. We study some examples of non-abelian groups and commutative rings such as R[X], where R is a principal ideal domain. [ABSTRACT FROM AUTHOR]

Moore’s generalization of the game of Nim is played as follows. Let n and k be two integers such that 1 ≤ k < n . Given n piles of tokens, two players move alternately, removing tokens from at least one and at most k of the piles. The player who makes the last move wins. The game was solved by Moore in 1910; an explicit formula for its Sprague–Grundy function was given by Jenkyns and Mayberry in 1980, but only for the case n = k + 1 . We introduce another generalization of Nim , called Exact k - Nim , in which exactly k piles are reduced by each move. We give an explicit formula for the Sprague–Grundy function of Exact k - Nim for the case 2 k ≥ n . If n = 2 k , our formula is surprisingly similar to Jenkyns and Mayberry’s one. [ABSTRACT FROM AUTHOR]

In this paper LIM, a recently proposed impartial combinatorial ruleset, is analyzed. A formula to describe the $$\mathcal G $$ -values of LIM positions is given, by way of analyzing an equivalent combinatorial ruleset LIM', closely related to the classical nim. Also, an enumeration of $$\mathcal P $$ -positions of LIM with $$n$$ stones, and its relation to the Ulam-Warburton cellular automaton, is presented. [ABSTRACT FROM AUTHOR]

Abstract: Given non-negative integers and , we consider the following game . Given two piles that consist of and matches, and two players having alternate turns; a single move consists of a player choosing matches from one pile and from the other such that The player who takes the last match is the winner in the normal version of the game and the loser in its misère version. It is easy to verify that the cases , and correspond to the two-pile, Wythoff and Fraenkel NIM, respectively. The concept of the minimum excludant, , is known to be instrumental in solving the last two games. We generalize this concept by introducing a function (such that ) to solve the normal and misère versions of the game . [Copyright &y& Elsevier]

Combinatorial game theory is the study of two player perfect information games. While work has been done in the past on expanding this field to include n-player games we present a unique method which guarantees a single winner. Specifically our goal is to derive a function which, given an n-player game, is able to determine the winning player (assuming all n players play optimally). Once this is accomplished we use this function in analyzing a certain family of three player subtraction games along with a complete analysis of three player, three row Chomp. Furthermore we make use of our new function in producing alternative proofs to various well known two player Chomp games. Finally the paper presents a possible method of analyzing a two player game where one of the players plays a completely random game. As it turns out this slight twist to the rules of combinatorial game theory produces rather interesting results and is certainly worth the time to study further. [ABSTRACT FROM AUTHOR]

Triangular Nim, one variant of the game Nim, is a common two-player game in Taiwan and China. In the past, Hsu [9] strongly solved seven layer Triangular Nim while some of the authors recently strongly solved eight layer Triangular Nim. The latter required 8 gigabytes in memory and 8,472 seconds. Using a retrograde method, this paper strongly solves nine layer Triangular Nim. In our first version, the program requires four terabytes in memory and takes about 129.21 days aggregately. In our second version, improved by removing some rotated and mirrored positions, the program reduces the memory by a factor of 5.72 and the computation time by a factor of 4.62. Our experiment result also shows that the loss rate is only 5.0%. This is also used to help improve the performance. [ABSTRACT FROM AUTHOR]

Abstract: We consider the Impartial Solitaire Clobber which is a one-player combinatorial game on graphs. The problem of determining the minimum number of remaining stones after a sequence of moves was proved to be NP-hard for graphs in general and, in particular, for grid graphs. This problem was studied for paths, cycles and trees, and it was proved that, for any arrangement of stones, this number can be computed in polinomial time. We study a more complex question related to determining the color and the location of the remaining stones. A graph G is strongly 1-reducible if: for any vertex v of G, for any arrangement of stones on G such that is non-monochromatic, and for any color c, there exists a succession of moves that yields a single stone of color c on v. We investigate this problem for powers of paths and for powers of cycles and we prove that if , then (resp. ) is strongly 1-reducible; if , then , is not strongly 1-reducible. [Copyright &y& Elsevier]

Abstract: Impartial Solitaire Clobber (ISC) is a variant of the two-player game Clobber introduced by Albert et al. in 2002. It is a one-player game with the following rules: given a graph , for each vertex , we assign a black or a white stone. A move consists in picking up a stone and clobbering another one of the opposite color located on an adjacent vertex. The clobbered stone is removed from the graph and it is replaced by the picked one. The goal is to find a succession of moves that minimizes the number of the remaining stones. In this paper, we study the ISC when G is a power of a path, and we prove that any non-monochromatic configuration of stones can be reduced to a single stone for a r-power of a path, and some circulant graphs. [Copyright &y& Elsevier]

Abstract: In this paper we study 3-Euclid, a modification of the game Euclid to three dimensions. In 3-Euclid, a position is a triplet of positive integers, written as . A legal move is to replace the current position with one in which any integer has been reduced by an integral multiple of some other integer. The only restriction on this subtraction is that the result must stay positive. We solve the game for some special cases and prove two theorems which give some properties of 3-Euclid''s Sprague–Grundy function. They provide a structural description of all positions of Sprague–Grundy value g with two numbers fixed. We state a theorem which establishes a periodicity in the P positions (i.e., those of Sprague–Grundy value ), and extend some results to the misère version. [Copyright &y& Elsevier]

Abstract: Recently, Gabriel Nivasch got the following remarkable formula for the Sprague–Grundy function of game Euclid: for all integers . We consider the corresponding misere game and show that its Sprague–Grundy function is equal to for all positions , except for the case when or equals , where is the ith Fibonacci number and k is a positive integer. It is easy to see that these exceptional Fibonacci positions are exactly those in which all further moves in the game are forced (unique) and hence, the results of the normal and misere versions are opposite; in other words, for these positions and take values 0 and 1 so that . Let us note that the good old game of Nim has similar property: if there is at most one bean in each pile then all further moves are forced. Hence, in these forced positions the results of the normal and misere versions are opposite, while for all other positions they are the same, as it was proved by Charles Bouton in 1901. Respectively, in the forced positions and take values 0 and 1 so that , where i is the number of non-empty piles, while in all other positions . [Copyright &y& Elsevier]