Heap games, numeration systems and sequences (Q1293425): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(5 intermediate revisions by 5 users not shown) | |||
Property / describes a project that uses | |||
Property / describes a project that uses: OEIS / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: math/9809074 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3944542 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Nonhomogeneous spectra of numbers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A linear algorithm for nonhomogeneous spectra of numbers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4099541 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5823285 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: How to Beat Your Wythoff Games' Opponent on Three Fronts / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Systems of Numeration / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A note on periodicity in some octal games / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Spectra of Numbers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3239652 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the complexity of some two-person perfect-information games / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5524370 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5665234 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2963616802 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 10:46, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Heap games, numeration systems and sequences |
scientific article |
Statements
Heap games, numeration systems and sequences (English)
0 references
20 August 2000
0 references
This is a well-commented analysis of the following heap game (i.e., Nim-like game), depending on a pair of positive integers \((s,t)\): There are two heaps with (finitely many) tokens. Two players alternately remove tokens, either an arbitrary number from one of the heaps, or \(k\) tokens from one and \(l\) from the other heap, provided \( 0 < k \leq l < sk+t \). The player taking the last token wins. A strategy is described by a sequence \((A_n,B_n)\) of winning positions (i.e., the sizes of the heaps to be left for the opponent). While in the previously studied cases -- that are \((1,1)\) (Wythoff's game) and \((1,t)\) -- there are two (real) numbers \(\alpha\) and \(\beta\) such that the (winning) strategy has a (spectral) expression by \( A_n = \lfloor n\alpha \rfloor \) and \( B_n = \lfloor n\beta \rfloor \), this approach is shown to be impossible in the general case. Nevertheless the strategy is of polynomial (even linear) complexity (in the size of the input data, i.e., the \(\log \) of the heap size). It can be characterized using the expansion of integers with respect to an (increasing) recursive sequence of base (nodal) numbers: The \(A_n\) are those integers whose expansion ends on an even number of 0's, while \(B_n\) is the left shift (by one digit) of \(A_n\). In addition, an alternative characterization of the pairs \((A_n,B_n)\) is given.
0 references
heap games
0 references
tree games
0 references
succinct games
0 references
Nim Wythoff's game
0 references
number systems
0 references