[PDF] Fibonacci-like sequences for variants of the tower of Hanoi and

View - Download Fibonacci-like sequences for variants of the tower of Hanoi and

Previous PDF

Next PDF

FIBONACCI-LIKE SEQUENCES FOR VARIANTS OF THE TOWER OF

HANOI, AND CORRESPONDING GRAPHS AND GRAY CODES

BENO ^IT RITTAUD Abstract.We modify the rules of the classical Tower of Hanoi puzzle in a quite natural way to get the Fibonacci sequence involved in the optimal algorithm of resolution, and show some nice properties of such a variant. In particular, we deduce from thisTower of Hanoi-Fibonacci a Gray-like code on the set of binary words without the factor 11, which has some properties intersting for itself and from which an iterative algorithm for the Tower of Hanoi-Fibonacci is obtained. Such an algorithm involves the Fibonacci substitution. Eventually, we brie y extend the study to some natural generalizations.

The Tower of Hanoi is a puzzle invented by

Edouard Lucas [7, 8] in which a set ofndisks

of dierent radius from 1 tonare put on a pegAin decreasing order, thus materializing a triangular tower. Two other pegs,BandC, are empty. The aim of the game is to move all the disks on the pegC(or, in a roughly equivalent version, on eitherBandC), following the two rules: (1) the disks are moved one at a time, taking a disk on the top of a peg and putting it on the top of another peg, and (2) a disk cannot be put over a smaller disk. This is what we will call theclassicalTower of Hanoi puzzle. A set-theoretic description of it is the following. We write eitherdkorkfor the disk of radiusk, and k=f1;:::;kgfor the set of theksmallest disks (with k=?fork <1). Any state of the puzzle corresponds to an ordered 3-partition of n, written as (A;B;C) and referred as astateof the puzzle (also referred asregular statein the litterature, when it is necessary to emphasize on the fact that disks on each peg has to be set up with decreasing size, an assumption that is weakened in some studies). A move from such a state to another one, say (A0;B0;C0), is allowed if, and only if, the two ordered partitions are equal up to somed2nsuch that d2 fmin(A);min(B);min(C)g \ fmin(A0);min(B0);min(C0)g. A lot of variants of the puzzle has been proposed since Lucas' orginal one. We report the reader to the highly valuable book [5] for a general synthesis on the subject. Lucas already understood that the Tower of Hanoi was deeply linked to numeration systems.

Indeed, he wrote in 1893 [9, p. 58] that

Increasing the number of pegs and slightly modifying the rule of the game would easily provide representations of all numeration systems. [En augmentant le nombre de tiges et en modiant legerement les regles du jeu, on obtiendrait facilement des representations de tous les systemes de numeration.] The optimal algorithm to solve the puzzle withndisks requires 2n1 moves (hence passes through 2 nstates), and the total number of admissible states is 3n. (There exists a \worst" algorithm that solves the puzzle passing through all these 3 nstate exactly once). Hence, it is not a surprise that there are natural links between the Tower of hanoi and binary and ternary numeration systems. At Lucas' time, only integral numeration systems were known. Since the \worst" solution (i.e. the solution that pass through all possible states) requires 3 n1 moves, it is sensible to ask for more pegs to represent other numeration systems. But now that non-integer numeration systems are known, we can give to Lucas' sentence a new meaning,

1arXiv:2206.03047v1 [cs.DM] 7 Jun 2022

keeping the three initial pegs and modifying the rules of the game, to get a Tower of Hanoi version of some nonconventional ways to write integers. A rst possibility consists in restricting the moves allowed between pegs. For example, we can forbid any direct move fromAtoCand fromCtoA. It is well-known that this constraint leads to the \worst" algorithm mentioned beforehand, that visits every possible state of the puzzle among the 3 nones. Each of the possible variants of this kind is linked to some numeration system (as well as to some Gray code) dened by a linear recurring sequence (see [11]). The initial question that gave rise to the present article was the converse: nd natural alternative rules for the Tower of Hanoi such that the minimal number of moves required to solve the puzzle withndisks corresponds to a sequence xeda priori. One of these sequences for which an answer can be found is the Fibonacci sequence, and we will shw that the answer described here extends to some other linear recurring sequences as well. Apart from the sequence of minimal moves, other links between the Tower of Hanoi and the Fibonacci sequence can be made. In particular, it is shown in [4] that, for the classical puzzle withndisks, the number ofkey states(i.e. for which the minimal number of moves to reach (?;?;n) is exactly twice the minimal number of moves to reach (n;?;?)) is equal to F n1. The same article mentions the following other result, due to Merryeld and published in [2]: for anyn, the set of distinctsAk(resp.Bk,Ck) attained during the optimal algorithm of resolution of the standard puzzle is of cardinalityFn+2(resp.Fn+1,Fn+2). The present paper is organized as follows. In Section 1, we recall the relevant properties of the classical Tower of Hanoi we wish to generalize. Section 2 is devoted to the main variant we are interested in. In this variant is denedFibonacci moves. We prove that the variant dened by these kind of moves, theTower of Hanoi-Fibonacci, is optimally solved in a number of moves essentially given by the Fibonacci sequence (Section 2.2). Then, we provide a link with the classical Zeckendorf-Fibonacci numeration system (Section 2.2) and deduce from it an iterative algorithm for the Tower of Hanoi-Fibonacci. We then study a Gray- like code associated to this numeration system (Section 2.3), then investigate the general properties of the graph associated to the puzzle (Section 2.4). Eventually, in Section 3 are brie y investigated some generalizations and questions, in two directions. The rst one is when the denition of Fibonacci moves is modied so as to get an optimal algorithm that requires a number of moves given by a linear recurring sequence of the formmn=mnp+mnq+ 1. The second one considers complementary restrictions on moves between pegs, that gives rise to a Tribonacci-like sequence.

1.The classical Tower of Hanoi

In the following, a subsetfdk1;:::;dkigof nwithk1<< kiis simply writtenk1ki. It is known since Lucas that the Tower of Hanoi has a solution for anyn>0, and that there is a unique solution with minimal numbermnof moves. Such a solution can be described recursively by the following decomposition, valid for anyn>1, from which we easily deduce thatmn= 2mn1+ 1, hencemn= 2n1 (sincem0= 0) . n;?;?)m n1!(n;n1;?)1!(?;n1;n)m n1!(?;?;n): Since the number of states during the optimal resolution of the puzzle is 1 +mn= 2n, it is natural to consider the binary expansion of length exactlynto code the successive states from

0 to 2

n1. It is easily proved by induction that the indexk(between 1 ton) of the leftmost changing digit from the binary expansion ofito the binary expansion ofi+ 1 corresponds to 2 FIBONACCI-LIKE SEQUENCES FOR VARIANTS OF THE TOWER OF HANOI Figure 1.The graphH3of the classical Tower of Hanoi with 3 disks. the disk which is moved when going from the stateito the statei+ 1. As a consequence, we have that, for any 16k6n, the number of times the diskdkis moved is 2nk. Also, consider the alternative codage of the states of the puzzle withndisks by elements of f0;1gngiven by the following rules: the initial state (n;?;?) is labelled 0n, and when we go from partition (A;B;C) to (A0;B0;C0) by moving the diskd=dk, the label of the state (A0;B0;C0) is dened as the label of (A;B;C) in which thek-th digit has been switched (that is: this digit becomes a 0 if it was a 1 and a 1 if it was a 0). Then, an induction shows that the sequence of codages of the successive states thus obtained coincides with there ected binary Gray code, that is: the listGnof all binary words with exactlynletters dened recursively byG0=f0gandGn= 0Gn1+ 1G n1(where, for a sequenceL=fx1;:::;xkgof words and da letter,dL=fdx1;:::;dxngand, withL0=fy1;:::;y`g, the notationL+L0stands for fx1;:::;xk;y1;:::y`g). The fundamental property of such a listGnis that any two consecutive elements of the list dier by exactly one digit. For a given state, when only the partition is known but not the order of its elements, we write the partition asXtYtZ. An expression likeXtYtZ!RtStTmeans a move (or a sequence of moves) in which the position of the elementR(resp.S,T) of the nal partition is the same as the position of the elementX(resp.Y,Z) in the initial partition. It was observed in [6] that the graphHn= (Vn;En) of the classical Tower of Hanoi has a fractal structure similar to the Sierpinski triangle,Hnbeing made of three copies ofHn1for any n>1, any two of these copies being linked by a single edge corresponding to a move of the formntn1t?!?tn1tn(see Figure 1). Eventually, the optimal solution of the puzzle can be described by the following algorithm: moved1(always in the wayA!B!C!Aifnis odd, and in the wayA!C!B!A ifnis even), then, while there is a diskdk6=d1that can be moved, move that disk then then move againd1. 3 Figure 2.The 3-Fibonacci move from (35;24;6) to (5;14;236).

2.The Tower of Hanoi-Fibonacci

2.1.Denition and optimal algorithm.

Denition 2.1.LetXandYbe two dierent pegs such that, for somek2n, we have X=k~XandY= k1~Y. WriteZfor the third peg. We dene ak-Fibonacci moveas a move that consists in putting simultaneously bothk1andkontoZ, i.e.: k ~Xtk1~YtZ!~Xtk2~Yt(k1)kZ: AFibonacci moveis ak-Fibonacci move for somek. TheTower of Hanoi-Fibonacciis the Tower of Hanoi puzzle in which only Fibonacci moves are allowed. (Note that this denition will be slightly modied in Section 2.4.) Note that the 1-Fibonacci move is the one in which only one disk is moved (the diskd1). Hence, this move is the only one common to the Tower of Hanoi-Fibonacci and the classical

Tower of Hanoi.

Theorem 2.2.The Tower of Hanoi-Fibonacci withndisks admits a solution for anyn>0. There is only one optimal algorithm for it, that needs exactlyFn+21Fibonacci moves (hence passes throughFn+2dierent states). As an example, here is the optimal solution in the casen= 5.

5;?;?)!(2345;?;1)!(345;12;?)!(45;1;23)!

Proof.The proof is very similar to the classical case. First, the casesn= 0 andn= 1 both admit trivial solutions, withm0= 0 =F21 andm1= 1 =F31, wheremnstands for the minimal number of moves to solve the puzzle withndisks. Now, putn>2 and assume that the puzzle withn1 andn2 disks are both solvable, withmn2=Fn1 andmn1=Fn+11. Consider the puzzle withndisks. To be moved, the disk of radiusnneeds to be alone on its peg, and needs the tower n1to be on another peg. To mimimize the number of moves, we can askdnto be moved only once, hence any solution of the puzzle needs to reach the state (n;n1;?). We thus get a recursive description of the optimal solution of the puzzle withn disks: n;?;?)m n1!(n;n1;?)1!(?;n2;(n1)n)m n2!(?;?;n): Hence, we have thatmn=mn1+ 1 +mn2, so, by the induction hypothesis,mn= (Fn+11) + 1 + (Fn1) =Fn+21, as required. 4 FIBONACCI-LIKE SEQUENCES FOR VARIANTS OF THE TOWER OF HANOI

2.2.Link with the Zeckendorf-Fibonacci numeration system.The classical link be-

tween binary numeration system and the standard Tower of Hanoi extends to theZeckendorf (orZeckendorf-Fibonacci)numeration systemand the Tower of Hanoi-Fibonacci. This link will provide us an iterative algorithm for the optimal solution of the latter puzzle. Recall that, as proved in [12], for any xedn>2 and any integer 0< k < Fn+1there exists a unique nite sequence (ui)26i6n2 f0;1gn1such thatuiui+1= 0 for anyiandk=X

26i6nu

iFi. Such a sequence is theZeckendorf-Fibonacci expansionofk. We will also write [unu2]F for it, andZ((ui)26i6n) for the correspondingk. By convention, we may deneZ(0) as the empty sequence. When we need the length of a Zeckendorf-Fibonacci expansion to be of a certain kind (as in the following theorem), we allow ourselves to append leading 0s to it, hence considering [0unu2]Fas equivalent to [unu2]F. In the following, aZF-sequence(orZF-word) will denote any binary sequence (or binary word) satisfying the property that it does not contains two successive 1 anywhere in its terms. Two ZF-words likeunu2and 0unu2will be regarded as equivalents. Under this equiv- alence relation, the Zeckendorf-Fibonacci expansion ofkis unique. Moreover, this expansion denes a bijection fromNonto the set of (non-empty) ZF-sequences. The Zeckendorf-Fibonacci expansion ofk >0 can be obtained by the application of the following algorithm: r:=k,ui:= 0 for alli>2,n:= max(j>2 :Fj6k) whiler >0: i:= max(j:Fj6r) u i:= 1 r:=rFi return((ui)26i6n). Theorem 2.3.Letn>0be some integer, let0< k < Fn+2, and letk1 = [un+1u2]F andk= [vn+1v2]F. Letjbe the biggest index such thatuj6=vj. Thek-th move of the Tower of Hanoi-Fibonacci withndisks is a(j1)-Fibonacci move. Proof.This is a simple induction making use of the recursive description of the algorithm n;?;?)!(n;n1;?)!(?;n2;(n1)n)!(?;?;n): The property is true forn= 0 andn= 1. Assume it is true forn2 andn1 for some n>2. The moves from (n;?;?) to (n;n1;?) are moves from 1 tomn1=Fn+11, so their Zeckendorf-Fibonacci exansion of lengthnare all of the form [0unu2]F. Hence, by induction hypothesis on the puzzle withn1 disks, the property is true for all these moves. Now, the Fibonacci move (n;n1;?)!(?;n2;(n1)n) is theFn+1-th one, of Zeckendorf-Fibonacci expansion of lengthnequal to [100]F. The biggest moving disk in this move is then-th one, and the biggest indexjas dened in the theorem is equal to n+ 1, so the theorem is also valid for this move. The remainingFnmoves are the ones with Zeckendorf-Fibonacci expansion of lengthnof the form [10un1u2]F, where [un1u0]Fis the Zeckendorf-Fibonacci expansion of length n2 ofkFn+1. Hence, we can apply to it the induction hypothesis made on the puzzle withn2 disks, and we are done. Theorem 2.4.Let0< k6nbe two integers. For the Hanoi-Fibonacci puzzle withndisks, the number ofk-Fibonacci moves in the optimal algorithm is equal toFn+1k. Proof.We procede by induction onnand (decreasing) induction onk. Fork=n, the number we are looking for is equal to 1, which corresponds indeed toFn+1k=F1= 1. Fork=n1, 5 it is easy to check that there is also exactly onek-Fibonacci move, a number equal toFn+1k= F

2. Now, fork < n1, by induction hypothesis, the part (n;?;?)!(n;n1;?) of the

algorithm involves a number ofk-Fibonacci moves equal toF(n1)+1k=Fnk, and the part (?;n2;(n1)n)!(?;?;n) involvesF(n2)+1k=Fnk1moves, hence a total equal toFnk+Fnk1=Fn+1kmoves. Theorem 2.3 provides a complete iterative algorithm for the Tower of Hanoi-Fibonacci, with the only issue that, for 1-Fibonacci moves (i.e. a move of the single diskd1), one has to determine on which peg the diskd1has to move. Here is an answer to this question. Let us say thatd1is moving to the right (resp. to the left) whenever it moves fromAtoB, fromB toCor fromCtoA(resp. fromAtoC, fromBtoAor fromCtoB). Thus, by Theorem

2.4, we can code the sequence of 1-Fibonacci moves for the puzzle withndisks as a word

n2 fl;rgFn, whereldenotes a move to the left andra move to the right. We then have the following result: Theorem 2.5.In the optimal algorithm for the Tower of Hanoi-Fiboonacci: ifn22N, then thek-th letter ofnis ariZ(k)has an even number of1s; ifn =22N, then thek-th letter ofnis ariZ(k)has an odd number of1s. Proof.We proceeds by induction onn>2. Write the decomposition of the optimal solution of the puzzle, with the corresponding number of 1-Fibonacci moves (given by Theorem 2.4 withk= 1). n;?;?)F n11!(n;n1;?)0!(?;n2;(n1)n)F n21!(?;?;n): Assume for examplen22N(the other case would be similar). Consider thek-th letter of ncorresponding to a 1-Fibonacci move among theFn11 rst ones. By the induction hypothesis, the fact thatn1 is odd and the fact that the 1-Fibonacci moves corresponding to ( n;?;?)!(n;n1;?) are the same as the one for (n;?;?)!(n;?;n1) but with exchanging thers and thels, we have that the consideredk-th letter is ariZ(k) hasquotesdbs_dbs47.pdfusesText_47

[PDF] maths dm sur le calcul

[PDF] maths dm sur les fonctions

[PDF] Maths dm sur les racines carrés

[PDF] maths dm trajet

[PDF] MATHS DM URGENT

[PDF] Maths du niveau quatrième

[PDF] maths ecriture scientifique help

[PDF] maths ecs exercices corrigés

[PDF] Maths effectifs

[PDF] Maths égalité de 2 carrés

[PDF] Maths éma tiques

[PDF] Maths en alld, j´arrive pas ? traduire

[PDF] maths en allemand

[PDF] maths en anglais collège

[PDF] maths en anglais vocabulaire