Learning of winning strategies for terminal games with linear-size memory

We prove that if one or more players in a locally finite positional game have winning strategies, then they can find it by themselves, not losing more than a bounded number of plays and not using more than a linear-size memory, independently of the strategies applied by the other players. We design two algorithms for learning how to win. One of them can also be modified to determine a strategy that achieves a draw, provided that no winning strategy exists for the player in question but with properly chosen moves a draw can be ensured from the starting position. If a drawing- or winning strategy exists, then it is learnt after no more than a linear number of plays lost (linear in the number of edges of the game graph). Z. Tuza’s research has been supported in part by the grant OTKA T-049613.     

Computational complexity of winning strategies in two-person polynomial games

One considers two-person games, with players called I and II below. In order, they choose natural numbers, for example, for length 4, I chooses x₁, II chooses x₂. I chooses x₃, II chooses x₄. Then I wins if P(x₁,x₂,x₃,x₄)=0.Here P is a polynomial with integer coefficients. An old theorem of von Neumann and Zermelo shows that such a game is determined, i.e., there exists a winning strategy for one player or the other but not necessarily a computable winning strategy or one computable in polynomial time. It will be shown that there exists a game of polynomial type of length 4 for which there do not exist winning strategies for either player which are computable in polynomial time.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 192, pp. 69–73, 1991.     

h-analogue of Fibonacci numbers

We introduce the \(h\) -analogue of Fibonacci numbers for non-commutative \(h\) -plane. For \(h h'= 1\) and \(h = 0\) , these are just the usual Fibonacci numbers as it should be. We show that the Laplace integral transforms for both the Fibonacci and Chebyshev polynomials are the \(h\) -Fibonacci numbers. We also derive a collection of identities for these numbers.     

广义Fibonacci数的一些恒等式

利用非数学归纳法,以及广义Fibonacci数的性质,得到了广义Fibonacci数的一些求和公式.     

Fibonacci数与Legendre多项式

讨论了 Fibonacci数与 Legendre多项式之间的关系 ,得到了一些有趣的恒等式 .     

Incomplete Fibonacci and Lucas numbers

A particular use of well-known combinatorial expressions for Fibonacci and Lucas numbers gives rise to two interesting classes of integers (namely, the numbersF _n(k) andL _n(k)) governed by the integral parametersn andk. After establishing the main properties of these numbers and their interrelationship, we study some congruence properties ofL _n(k), one of which leads to a supposedly new characterisation of prime numbers. A glimpse of possible generalisations and further avenues of research is also caught.     

Unique winning policies for linear differential pursuit games

We study optimal control problems which are the duals, in a specified sense, to a certain class of linear differential games. Directly verifiable conditions, in terms of the data of the game, for uniqueness of solutions of the dual problem and thus for uniqueness of winning policies for the differential game, are derived. As a byproduct, in the particular context of two-dimensional problems, a strong result concerning normality is obtained. As a second byproduct, several geometrical and topological properties of thestar difference are derived. This set operation is of paramount importance for the study of rich classes of differential and difference games extending far beyond that treated here.Notation co(P) convex hull of a setPR ⁿ - ext(P) set of extreme points ofP - [x ₁,x ₂] line segment joining the pointsx ₁,x ₂ R ⁿ - S(P, c) Supporting closed halfspace ofP with exterior normalc - H(P, c) supporting hyperplane ofP with exterior normalc - F(P, c) face of the polytopeP with exterior normalc - span(P) linear span ofP - lin(P) linear closure ofP = smallest linear manifold containingP - relbd(P) relative boundary ofP - int(P) interior ofP with respect to the topology ofR ⁿ - ri(P) relative interior ofP with respect to lin(P) - a, b inner product (inR ⁿ) ofa andb - U/W {x:x U R ⁿ andx W R ⁿ} - cl(P) closure ofP This work was done during the year 1972, when the author was a student of Prof. O. Hajek at Case Western Reserve University, Cleveland, Ohio. The author wishes to thank Dr. Hajek for his many comments, suggestions, and critique.     

On beta expansions for Pisot numbers

Given a number , the beta-transformation is defined for by (mod 1). The number is said to be a beta-number if the orbit is finite, hence eventually periodic. In this case is the root of a monic polynomial with integer coefficients called the characteristic polynomial of . If is the minimal polynomial of , then for some polynomial . It is the factor which concerns us here in case is a Pisot number. It is known that all Pisot numbers are beta-numbers, and it has often been asked whether must be cyclotomic in this case, particularly if . We answer this question in the negative by an examination of the regular Pisot numbers associated with the smallest 8 limit points of the Pisot numbers, by an exhaustive enumeration of the irregular Pisot numbers in (an infinite set), by a search up to degree in , to degree in , and to degree in . We find the smallest counterexample, the counterexample of smallest degree, examples where is nonreciprocal, and examples where is reciprocal but noncyclotomic. We produce infinite sequences of these two types which converge to from above, and infinite sequences of with nonreciprocal which converge to from below and to the th smallest limit point of the Pisot numbers from both sides. We conjecture that these are the only limit points of such numbers in . The Pisot numbers for which is cyclotomic are related to an interesting closed set of numbers introduced by Flatto, Lagarias and Poonen in connection with the zeta function of . Our examples show that the set of Pisot numbers is not a subset of .

     

Graphs, partitions and Fibonacci numbers

The Fibonacci number of a graph is the number of independent vertex subsets. In this paper, we investigate trees with large Fibonacci number. In particular, we show that all trees with n edges and Fibonacci number >2^n-1+5 have diameter ?4 and determine the order of these trees with respect to their Fibonacci numbers. Furthermore, it is shown that the average Fibonacci number of a star-like tree (i.e. diameter ?4) is asymptotically for constants A,B as n→∞. This is proved by using a natural correspondence between partitions of integers and star-like trees.     

Complexity of winning strategies

Rabin has given an example of a game with recursive rules but no recursive winning strategy. We show that such a game always has a hyperarithmetical winning strategy, but arbitrarily high levels of the hyperarithmetical hierarchy may be needed. We also exhibit a recursively enumerable game which has no hyperarithmetical winning strategy.     

Formula for Fibonacci sequence with arbitrary initial numbers

In this paper the formula for Fibonacci sequences with arbitrary initial numbers has been established by using damped oscillation equation. The formula has an exponential and an oscillatory part, it does not separate the indexes of odd and even members of the series and it is applicable on the continual domain. With elementary conditions the formula is reduced to Lucas series, and the square of Lucas series has a catalytic role in the relation of hyperbolic and trigonometric cosine. A complex function is given and the length of Fibonacci spiral is calculated. Natural phenomena support the validity of the proposed concept.     

Common factors of shifted Fibonacci numbers

For any positive integer n let F_n be the n-th Fibonacci number. Given positive integers a and b, we study the size of the greatest common divisor of F_n + a and F_m + b for varying positive integers m and n.     

Unique expansions of real numbers

It was discovered some years ago that there exist non-integer real numbers q>1 for which only one sequence (ci) of integers ci∈[0,q) satisfies the equality . The set of such “univoque numbers” has a rich topological structure, and its study revealed a number of unexpected connections with measure theory, fractals, ergodic theory and Diophantine approximation.In this paper we consider for each fixed q>1 the set Uq of real numbers x having a unique representation of the form with integers ci belonging to [0,q). We carry out a detailed topological study of these sets. For instance, we characterize their closures, and we determine those bases q for which Uq is closed or even a Cantor set. We also study the set consisting of all sequences (ci) of integers ci∈[0,q) such that . We determine the numbers r>1 for which the map (defined on (1,∞)) is constant in a neighborhood of r and the numbers q>1 for which is a subshift or a subshift of finite type.     

Fibonacci numbers, Lucas numbers and integrals of certain Gaussian processes

We study the distributions of integrals of Gaussian processes arising as limiting distributions of test statistics proposed for treating a goodness of fit or symmetry problem. We show that the cumulants of the distributions can be expressed in terms of Fibonacci numbers and Lucas numbers.

     

Fibonacci numbers and real quadratic p-rational fields

Periodica Mathematica Hungarica - We characterize p-rational real quadratic fields in terms of generalized Fibonacci numbers. We then use this characterization to give numerical evidence to a...     

Quantitative irrationality for sums of reciprocals of Fibonacci and Lucas numbers

Irrationality measures are given for the values of the series , where and W_n is a rational valued Fibonacci or Lucas form, satisfying a second order linear recurrence. In particular, we prove irrationality of all the numbers