The Generalized Bergman Game
| Autor: | Baily, Benjamin, Dell, Justine, Durmić, Irfan, Fleischmann, Henry, Jackson, Faye, Mijares, Isaac, Miller, Steven J., Pesikoff, Ethan, Reifenberg, Luke, Reina, Alicia Smith, Yang, Yingzi |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Every positive integer may be written uniquely as a base-$\beta$ decomposition--that is a legal sum of powers of $\beta$--where $\beta$ is the dominating root of a non-increasing positive linear recurrence sequence. Guided by earlier work on a two-player game which produces the Zeckendorf Decomposition of an integer (see [Bai+19]), we define a broad class of two-player games played on an infinite tuple of non-negative integers which decompose a positive integer into its base-$\beta$ expansion. We call this game the Generalized Bergman Game. We prove that the longest possible Generalized Bergman game on an initial state $S$ with $n$ summands terminates in $\Theta(n^2)$ time, and we also prove that the shortest possible Generalized Bergman game on an initial state terminates between $\Omega(n)$ and $O(n^2)$ time. We also show a linear bound on the maximum length of the tuple used throughout the game. Comment: 34 pages, 6 figures, to be submitted in Fibonacci Quartlerly |
| Databáze: | arXiv |
| Externí odkaz: |
|