اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدQueens in exile: non-attacking queens on infinite chess boards
85
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Number the cells of a (possibly infinite) chessboard in some way with the numbers 0, 1, 2, ... Consider the cells in order, placing a queen in a cell if and only if it would not attack any earlier queen. The problem is to determine the positions of the queens. We study the problem for a doubly-infinite chessboard of size Z x Z numbered along a square spiral, and an infinite single-quadrant chessboard (of size N x N) numbered along antidiagonals. We give a fairly complete solution in the first case, based on the Tribonacci word. There are connections with combinatorial games.
قيم البحث
اقرأ أيضاً
The famous $n$-queens problem asks how many ways there are to place $n$ queens on an $n times n$ chessboard so that no two queens can attack one another. The toroidal $n$-queens problem asks the same question where the board is considered on the surf
ace of the torus and was asked by P{o}lya in 1918. Let $Q(n)$ denote the number of $n$-queens configurations on the classical board and $T(n)$ the number of toroidal $n$-queens configurations. P{o}lya showed that $T(n)>0$ if and only if $n equiv 1,5 mod 6$ and much more recently, in 2017, Luria showed that $T(n)leq ((1+o(1))ne^{-3})^n$ and conjectured equality when $n equiv 1,5 mod 6$. Our main result is a proof of this conjecture, thus answering P{o}lyas question asymptotically. Furthermore, we also show that $Q(n)geq((1+o(1))ne^{-3})^n$ for all $n$ sufficiently large, which was independently proved by Luria and Simkin. Combined with our main result and an upper bound of Luria, this completely settles a conjecture of Rivin, Vardi and Zimmmerman from 1994 regarding both $Q(n)$ and $T(n)$. Our proof combines a random greedy algorithm to count almost configurations with a complex absorbing strategy that uses ideas from the recently developed methods of randomised algebraic construction and iterative absorption.
By now, the Maker-Breaker connectivity game on a complete graph $K_n$ or on a random graph $Gsim G_{n,p}$ is well studied. Recently, London and Pluhar suggested a variant in which Maker always needs to choose her edges in such a way that her graph st
ays connected. By their results it follows that for this connected version of the game, the threshold bias on $K_n$ and the threshold probability on $Gsim G_{n,p}$ for winning the game drastically differ from the corresponding values for the usual Maker-Breaker version, assuming Makers bias to be $1$. However, they observed that the threshold biases of bo
We investigate the transfinite game values arising in infinite chess, providing both upper and lower bounds on the supremum of these values---the omega one of chess---with two senses depending on whether one considers only finite positions or also po
sitions with infinitely many pieces. For lower bounds, we present specific infinite positions with transfinite game values of omega, omega^2, omega^2 times k, and omega^3. By embedding trees into chess, we show that there is a computable infinite chess position that is a win for white if the players are required to play according to a deterministic computable strategy, but which is a draw without that restriction. Finally, we prove that every countable ordinal arises as the game value of a position in infinite three-dimensional chess, and consequently the omega one of infinite three-dimensional chess is as large as it can be, namely, true omega one.
We present a position in infinite chess exhibiting an ordinal game value of $omega^4$, thereby improving on the previously largest-known values of $omega^3$ and $omega^3cdot 4$.
The study of the structure of infinite words having bounded abelian complexity was initiated by G. Richomme, K. Saari, and L. Q. Zamboni. In this note we define bounded additive complexity for infinite words over a finite subset of Z^m. We provide an
alternative proof of one of the results of Richomme, Saari, and Zamboni.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
