益智游戏“汉诺塔”中的矩阵运算

汉诺塔(Tower of Hanoi)问题源于印度一个古老传说,据此做成了益智游戏,蕴含大量的数学思想与方法.本文采用矩阵描述汉诺塔状态和圆盘移动过程,将圆盘从一个位置移动到另一个位置转化为矩阵的加法,进而构造由若干可能状态矩阵组成的图的邻接矩阵,计算其幂矩阵,由此很方便地求得完成汉诺塔游戏的所有可能的圆盘移动方案,求解过程简单,含义清晰,易于理解和实现.     

Hanoi塔问题的一个公式解

Hanoi塔问题自提出以来已有一百多年的历史.其间,这一问题吸引了许多的研究者.正如H.A.Simon所指出的,Hanoi塔问题对于认知科学就象大肠杆菌对现代基因学那样,是一个无价的研究标本.事实上,它已成为组合数学,人工智能,计算机科学以及规划等中的递归问题的典型例子,并由此产生了各种各样成熟的算法.回顾这些结果,我们提出一个基本问题能否对Hanoi塔问题给出一个公式解?本文就此给出了一个肯定的回答.在我们的研究中,图论将是一个有力的工具     

On the Frame–Stewart algorithm for the multi-peg Tower of Hanoi problem

It is proved that seven different approaches to the multi-peg Tower of Hanoi problem are all equivalent. Among them the classical approaches of Stewart and Frame from 1941 can be found.     

Two-player stochastic games I: A reduction

This paper is the first step in the proof of existence of equilibrium payoffs for two-player stochastic games with finite state and action sets. It reduces the existence problem to the class of so-called positive absorbing recursive games. The existence problem for this class is solved in a subsequent paper.     

Using the Tower of Hanoi puzzle to infuse your mathematics classroom with computer science concepts

This article suggests that logic puzzles, such as the well-known Tower of Hanoi puzzle, can be used to introduce computer science concepts to mathematics students of all ages. Mathematics teachers introduce their students to computer science concepts that are enacted spontaneously and subconsciously throughout the solution to the Tower of Hanoi puzzle. These concepts include, but are not limited to, conditionals, iteration, and recursion. Lessons, such as the one proposed in this article, are easily implementable in mathematics classrooms and extracurricular programmes as they are good candidates for ‘drop in’ lessons that do not need to fit into any particular place in the typical curriculum sequence. As an example for readers, the author describes how she used the puzzle in her own Number Sense and Logic course during the federally funded Upward Bound Math/Science summer programme for college-intending low-income high school students. The article explains each computer science term with real-life and mathematical examples, applies each term to the Tower of Hanoi puzzle solution, and describes how students connected the terms to their own solutions of the puzzle. It is timely and important to expose mathematics students to computer science concepts. Given the rate at which technology is currently advancing, and our increased dependence on technology in our daily lives, it has become more important than ever for children to be exposed to computer science. Yet, despite the importance of exposing today's children to computer science, many children are not given adequate opportunity to learn computer science in schools. In the United States, for example, most students finish high school without ever taking a computing course. Mathematics lessons, such as the one described in this article, can help to make computer science more accessible to students who may have otherwise had little opportunity to be introduced to these increasingly important concepts.     

Graphs S(n, k) and a Variant of the Tower of Hanoi Problem

For any n 1 and any k 1, a graph S(n, k) is introduced. Vertices of S(n, k) are n-tuples over {1, 2,. . . k} and two n-tuples are adjacent if they are in a certain relation. These graphs are graphs of a particular variant of the Tower of Hanoi problem. Namely, the graphs S(n, 3) are isomorphic to the graphs of the Tower of Hanoi problem. It is proved that there are at most two shortest paths between any two vertices of S(n, k). Together with a formula for the distance, this result is used to compute the distance between two vertices in O(n) time. It is also shown that for k 3, the graphs S(n, k) are Hamiltonian.     

Two-player bargaining problems with unilateral pre-donation

This paper characterizes conditions for two-player bargaining problems and bargaining rules under which unilateral pre-donation always yields Pareto utility gains. The paper also computes the optimal pre-donation of each player under the class of proportional bargaining rules.     

Two-player simultaneous location game: Preferential rights and overbidding

Competitive location problems can be characterized by the fact that the decisions made by others will affect our own payoffs. In this paper, we address a discrete competitive location game in which two decision-makers have to decide simultaneously where to locate their services without knowing the decisions of one another. This problem arises in a franchising environment in which the decision-makers are the franchisees and the franchiser defines the potential sites for locating services and the rules of the game. At most one service can be located at each site, and one of the franchisees has preferential rights over the other. This means that if both franchisees are interested in opening the service in the same site, only the one that has preferential rights will open it. We consider that both franchisees have budget constraints, but the franchisee without preferential rights is allowed to show interest in more sites than the ones she can afford. We are interested in studying the influence of the existence of preferential rights and overbidding on the outcomes for both franchisees and franchiser. A model is presented and an algorithmic approach is developed for the calculation of Nash equilibria. Several computational experiments are defined and their results are analysed, showing that preferential rights give its holder a relative advantage over the other competitor. The possibility of overbidding seems to be advantageous for the franchiser, as well as the inclusion of some level of asymmetry between the two decision-makers.     

The Towers of Hanoi

This article presents an investigation carried out with a groupof able mathematics students who were studying at a level 1year in advance of their peers. The purpose was to investigatethe extension of usual three peg Towers of Hanoi to four pegsand attempt to find a rule that could be used to predict theminimum number of moves required to complete the puzzle.     

Two-player stochastic games II: The case of recursive games

This paper contains the second step in the proof of existence of equilibrium payoffs for two-player stochastic games. It deals with the case of positive absorbing recursive games     

A Mathematical Visit to Hanoi

This article, written in September 1978, is appearing after several unexpected publication delays. In the meantime a sequence of events in Southeast Asia — the Chinese invasion, the exodus of refugees, the war in Cambodia — is inevitably having an impact on Vietnam’s pace of economic recovery from the War and level of technological development. In any case, this article obviously cannot address the political and economic issues that have come into focus in the past year.     

Parallelism for multipeg towers of Hanoi

This paper studies parallelism for the multipeg Towers of Hanoi problem, an interesting generalization of the traditional one, by allowing concurrent moves of discs in a single step. Three versions of parallelism are investigated based on two factors: the order of moves of discs and the resource utilization of pegs. Solutions obtained include the minimum numbers of steps and algorithms for moving discs in the minimum numbers of steps. A common technique is presented for deriving the nonrecursive computation of minimum numbers of steps, which discloses a methodology for the study of parallelism in the multipeg Towers.     

On the planarity of Hanoi graphs

Hanoi graphs are the state graphs for Tower of Hanoi problems with three or more pegs. We prove hamiltonicity and present a complete analysis of planarity of these graphs.     

梵塔问题的两个定理

本文首次证明了梵塔问题的两个定理,建立了一种梵塔问题新算法．     

带上下界的双参与人双向委托代理模型及优化算法研究

考虑现实中双参与人同时具有委托人和代理人双重身份情形下,双参与人间的互为委托代理关系,设计虚拟委托人期望效用函数表达式,建立带上下界的双参与人双边约束双向委托代理模型,利用不动点定理确定参数的上下界,并运用不等式组的旋转算法并结合序列二次规划算法进行求解.通过算例分析表明,为达到联盟总效用最大化,需通过确定联盟成员各自合适的保留效用值,以平衡联盟成员的投资和回报,真正实现对联盟成员的激励.     

An analysis of the generalized Towers of Hanoi problem

A state-space graph for representing the states and their transitions ofn discs on three pegs is formulated. It is then transformed to a shortest-path tree for representing the shortest paths in transferringn discs in any configurations to a specified peg. The shortest-path tree clearly characterizes the generalized Towers of Hanoi problem; and its use leads to a very simple analysis of the generalized problem. The best-case, the worst-case and the average-case complexities are analyzed.     

Asymptotic aspects of Schreier graphs and Hanoi Towers groups

We present relations between growth, growth of diameters and the rate of vanishing of the spectral gap in Schreier graphs of automaton groups. In particular, we introduce a series of examples, called Hanoi Towers groups since they model the well known Hanoi Towers Problem, that illustrate some of the possible types of behavior. To cite this article: R. Grigorchuk, Z. ?unik´, C. R. Acad. Sci. Paris, Ser. I 342 (2006).     

The complexity of the generalised cyclic Towers of Hanoi problem

This paper analyzes the generalised cyclic Towers of Hanoi problem. A directed state-space graph is used for representing states of discs and disc movements. Such a graph is then transformed to a shortest-path tree for making explicit all shortest paths for moving all discs in all possible states to a goal state. The best-case, the worst-case, and the average-case complexities are then given based on such a shortest-path tree.