Source author record

Aviezri S. Fraenkel

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.NT

Catalog footprint

Research overview

6works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Searching for Disjoint Covering Systems with Precisely One Repeated Modulus

A set of arithmetical sequences $a_1\, (\bmod{ \,\, m_1}) \quad, \quad a_2 \, (\bmod{\,\, m_2}) \quad, \quad \dots \quad , \quad a_k \, (\bmod{\,\,m_k}) \quad \quad ,$ with $m_1 \leq m_2 \leq \dots \leq m_k \quad \quad ,$ is called a {\it disjoint covering system} (alias {\it exact covering system}) if every positive integer belongs to {\bf exactly} one of the sequences. Mirski, Newman, Davenport and Rado famously proved that the moduli can't all be distinct. In fact the two largest moduli must be equal, i.e. $m_{k-1}=m_k$ This raises the natural question:"How close can you get to getting distinct moduli?", in other words, can you find all such systems where all the moduli are distinct except the largest, that is repeated $r$ times, for any, specific given $r$ ? It turns out (conjecturally, but almost certainly) that excluding the trivial case where the smallest modulus is 2, for any number of repeats $r$ , there are only finitely many such systems. Marc Berger, Alexander Felzenbaum and Aviezri Fraenkel found them all for $r$ up to $9$ , and Mekmamu Zeleke and Jamie Simpson extended the list for systems up to $12$ repeats. In the present article we continue the list up to $r=32$ . All our systems are correct, but we did not bother to formally prove completeness, but we know for sure that the lists are complete if the largest modulus is $\leq 600$ , and we are pretty sure that they are complete.

preprint2014arXiv

When are translations of P-positions of Wythoff's game P-positions?

We study the problem whether there exist variants of {\sc Wythoff}'s game whose $¶$ -positions, except for a finite number, are obtained from those of {\sc Wythoff}'s game by adding a constant $k$ to each $¶$ -position. We solve this question by introducing a class $\{\W_k\}_{k \geq 0}$ of variants of {\sc Wythoff}'s game in which, for any fixed $k \geq 0$ , the $¶$ -positions of $\W_k$ form the set $\{(i,i) | 0 \leq i < k\}\cup \{(\lfloor ϕn \rfloor + k, \lfloor ϕ^2 n \rfloor + k) | n\ge 0\}$ , where $ϕ$ is the golden ratio. We then analyze a class $\{\T_k\}_{k \geq 0}$ of variants of {\sc Wythoff}'s game whose members share the same $¶$ -positions set $\{(0,0)\}\cup \{(\lfloor ϕn \rfloor + 1, \lfloor ϕ^2 n \rfloor + 1) | n \geq 0 \}$ . We establish several results for the Sprague-Grundy function of these two families. On the way we exhibit a family of games with different rule sets that share the same set of $¶$ -positions.

preprint2010arXiv

Invariant and dual subtraction games resolving the Duchê-Rigo conjecture

We prove a recent conjecture of Duchêne and Rigo, stating that every complementary pair of homogeneous Beatty sequences represents the solution to an \emph{invariant} impartial game. Here invariance means that each available move in a game can be played anywhere inside the game-board. In fact, we establish such a result for a wider class of pairs of complementary sequences, and in the process generalize the notion of a \emph{subtraction game}. Given a pair of complementary sequences $(a_n)$ and $(b_n)$ of positive integers, we define a game $G$ by setting $\{\{a_n, b_n\}\}$ as invariant moves. We then introduce the invariant game $G^\star$ , whose moves are all non-zero $P$ -positions of $G$ . Provided the set of non-zero $P$ -positions of $G^\star$ equals $\{\{a_n,b_n\}\}$ , this \emph{is} the desired invariant game. We give sufficient conditions on the initial pair of sequences for this 'duality' to hold.

preprint1998arXiv

Multivision: an intractable impartial game with a linear winning strategy

Something is definitely wrong. If the game has a linear winning strategy, then it is tractable. What's going on? Well, we describe a two-person game which has a definite winner, that is, a player who can force a win in a finite number of moves, and we determine the winner in linear time. Moreover, the winner's winning moves can be computed in linear time, yet the game is highly intractable. In particular, at each step, except the very last ones, a player can make the length of play arbitrarily long. Unfortunately, the space for this summary is too small to contain a proof that these properties are not contradictory.

preprint1995arXiv

Error-correcting codes derived from combinatorial games

The ``losing positions" of certain combinatorial games constitute linear error detecting and correcting codes. We show that a large class of games that can be cast in the form of *annihilation games*, provides a potentially polynomial method for computing codes (*anncodes*). We also give a short proof of the basic properties of the previously known *lexicodes*, which are defined by means of an exponential algorithm, and are related to game theory. The set of lexicodes is seen to constitute a subset of the set of anncodes. In the final section we indicate, by means of an example, how the method of producing lexicodes can be applied optimally to find anncodes. Some extensions are indicated.

preprint1995arXiv

Scenic trails ascending from sea-level Nim to alpine chess

Aim: Present a systematic development of part of the theory of combinatorial games from the ground up. Approach: Computational complexity. Combinatorial games are completely determined; the questions of interest are efficiencies of strategies. Methodology: Divide and conquer. Ascend from Nim to chess in small strides at a gradient that's not too steep. Presentation: Informal; examples of games sampled from various strategic viewing points along scenic mountain trails, which illustrate the theory.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.