oalib
Search Results: 1 - 10 of 100 matches for " "
All listed articles are free for downloading (OA Articles)
Page 1 /100
Display every page Item
The Tower of Hanoi and finite automata  [PDF]
Jean-Paul Allouche,Jeff Shallit
Mathematics , 2009,
Abstract: Some of the algorithms for solving the Tower of Hanoi puzzle can be applied "with eyes closed" or "without memory". Here we survey the solution for the classical Tower of Hanoi that uses finite automata, as well as some variations on the original puzzle. In passing, we obtain a new result on morphisms generating the classical and the lazy Tower of Hanoi, and a new result on automatic sequences.
The Magnetic Tower of Hanoi  [PDF]
Uri Levy
Computer Science , 2010,
Abstract: In this work I study a modified Tower of Hanoi puzzle, which I term Magnetic Tower of Hanoi (MToH). The original Tower of Hanoi puzzle, invented by the French mathematician Edouard Lucas in 1883, spans "base 2". That is - the number of moves of disk number k is 2^(k-1), and the total number of moves required to solve the puzzle with N disks is 2^N - 1. In the MToH puzzle, each disk has two distinct-color sides, and disks must be flipped and placed so that no sides of the same color meet. I show here that the MToH puzzle spans "base 3" - the number of moves required to solve an N+1 disk puzzle is essentially three times larger than he number of moves required to solve an N disk puzzle. The MToH comes in 3 flavors which differ in the rules for placing a disk on a free post and therefore differ in the possible evolutions of the Tower states towards a puzzle solution. I analyze here algorithms for minimizing the number of steps required to solve the MToH puzzle in its different versions. Thus, while the colorful Magnetic Tower of Hanoi puzzle is rather challenging, its inherent freedom nurtures mathematics with remarkable elegance.
The group of symmetries of the Tower of Hanoi graph  [PDF]
So Eun Park
Mathematics , 2008,
Abstract: I prove that the group of symmetries of the Tower of Hanoi graph with k pegs and n disks, denoted H_n^k, is isomorphic to the group of permutations of k elements, S_k, for all k greater than or equal to 3 and positive n.
On the Footsteps to Generalized Tower of Hanoi Strategy  [PDF]
Bijoy Rahman Arif
Computer Science , 2011,
Abstract: In this paper, our aim is to prove that our recursive algorithm to solve the "Reve's puzzle" (four- peg Tower of Hanoi) is the optimal solution according to minimum number of moves. Here we used Frame's five step algorithm to solve the "Reve's puzzle", and proved its optimality analyzing all possible strategies to solve the problem. Minimum number of moves is important because no one ever proved that the "presumed optimal" solution, the Frame-Stewart algorithm, always gives the minimum number of moves. The basis of our proof is Bifurcation Theorem. In fact, we can solve generalized "Tower of Hanoi" puzzle for any pegs (three or more pegs) using Bifurcation Theorem. But our scope is limited to the "Reve's puzzle" in this literature, but lately, we would discuss how we can reach our final destination, the Generalized Tower of Hanoi Strategy. Another important point is that we have used only induction method to prove all the results throughout this literature. Moreover, some simple theorems and lemmas are derived through logical perspective or consequence of induction method. Lastly, we will try to answer about uniqueness of solution of this famous puzzle.
Solving the Tower of Hanoi with Random Moves  [PDF]
Max A. Alekseyev,Toby Berger
Computer Science , 2013,
Abstract: We prove the exact formulae for the expected number of moves to solve several variants of the Tower of Hanoi puzzle with 3 pegs and n disks, when each move is chosen uniformly randomly from the set of all valid moves. We further present an alternative proof for one of the formulae that couples a theorem about expected commute times of random walks on graphs with the delta-to-wye transformation used in the analysis of three-phase AC systems for electrical power distribution.
Two-Player Tower of Hanoi  [PDF]
Jonathan Chappelon,Urban Larsson,Akihiro Matsuura
Computer Science , 2015,
Abstract: The Tower of Hanoi game is a classical puzzle in recreational mathematics, which also has a strong record in pure mathematics. In a borderland between these two areas we find the characterization of the minimal number of moves, which is $2^n-1$, to transfer a tower of $n$ disks. But there are also other variations to the game, involving for example move edges weighted by real numbers. This gives rise to a similar type of problem, but where the final score seeks to be optimized. We study extensions of the one-player setting to two players, invoking classical winning conditions in combinatorial game theory such as the player who moves last wins, or the highest score wins. Here we solve both these winning conditions on three heaps.
Upper estimates of complexity of algorithms for multi-peg Tower of Hanoi problem  [cached]
Sergey Novikov
Annales Universitatis Paedagogicae Cracoviensis. Studia Mathematica , 2007,
Abstract: There are proved upper explicit estimates of complexity of lgorithms: for multi-peg Tower of Hanoi problem with the limited number of disks, for Reve's puzzle and for $5$-peg Tower of Hanoi problem with the free number of disks.
Shortest paths in the Tower of Hanoi graph and finite automata  [PDF]
Dan Romik
Mathematics , 2003,
Abstract: We present efficient algorithms for constructing a shortest path between two states in the Tower of Hanoi graph, and for computing the length of the shortest path. The key element is a finite-state machine which decides, after examining on the average only 63/38 of the largest discs, whether the largest disc will be moved once or twice. This solves a problem raised by Andreas Hinz, and results in a better understanding of how the shortest path is determined. Our algorithm for computing the length of the shortest path is typically about twice as fast as the existing algorithm. We also use our results to give a new derivation of the average distance 466/885 between two random points on the Sierpinski gasket of unit side.
The Tower of Hanoi problem on Path_h graphs  [PDF]
Daniel Berend,Amir Sapir,Shay Solomon
Computer Science , 2011,
Abstract: The generalized Tower of Hanoi problem with h \ge 4 pegs is known to require a sub-exponentially fast growing number of moves in order to transfer a pile of n disks from one peg to another. In this paper we study the Path_h variant, where the pegs are placed along a line, and disks can be moved from a peg to its nearest neighbor(s) only. Whereas in the simple variant there are h(h-1)/2 possible bi-directional interconnections among pegs, here there are only h-1 of them. Despite the significant reduction in the number of interconnections, the number of moves needed to transfer a pile of n disks between any two pegs also grows sub-exponentially as a function of n. We study these graphs, identify sets of mutually recursive tasks, and obtain a relatively tight upper bound for the number of moves, depending on h, n and the source and destination pegs.
The Tower of Hanoi for Evaluating Dysexecutive Syndrome in Patients with Parkinson’s: Standardization Values  [PDF]
Marcos Serrano-Due?as, Belén Calero, Maite Serrano
Advances in Parkinson's Disease (APD) , 2017, DOI: 10.4236/apd.2017.63008
Abstract:
Objective: The Tower of Hanoi measures executive functions using non-verbal content and requires perception of position in space. The main objective of this study is to standardize the use of the TOH as a measurement tool in Parkinson’s disease. Patients and Methods: Of the Control Group subjects, 192 (59.6%) were women, 223 subjects (69.25%) were able to perform the TOH with 3 discs. In the Parkinson’s Group, there were 57 women (39.3%), and 66 subjects (45.5%) did not get past that level. Results: If we take the TOH (with 3 or 4 discs) as a tool for discriminating between those who have dysexecutive syndrome and those who do not, we find that the Parkinson’s Group presents dysexecutive syndrome significantly more frequently than the Control Group (p ≤ 0.0064). Conclusion: We can conclude that dysexecutive syndrome is frequent in Parkinson’s patients and it is more prevalent than in the general population.
Page 1 /100
Display every page Item


Home
Copyright © 2008-2017 Open Access Library. All rights reserved.