[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

136.0. "Mutants of Hanoi" by TURTLE::GILBERT () Thu Aug 23 1984 17:53

These variants of the classic Towers of Hanoi problem appear in issue 3
of ABACUS.  Programs to solve them, and analyses of the programs were
requested.  A recurrence that yields the minimum number of moves, and a
proof of minimality should suffice here.

1.  Self-Solving
	Color the disks alternately Red and White.  If two isochromatic disks
	are never stacked atop each other, the problem almost solves itself.
	This is just a curio; no solution is requested.

2.  Crippled
	Disks can only be moved one peg to the left or right (per move).  Move
	the stack from the leftmost peg to the rightmost peg.

3.  Centipede
	Consider four disks and four pegs; five disks and five pegs.
	(the more general case of d disks and s pegs was considered in a
	previous note).

4.  Patriot
	Color the disks alternately Red, White and Blue.  Isochromatic disks
	may not be stacked atop one another.  This is the most difficult of
	the proposed mutants.

5.  Crowd (aka the Tower of Calcutta)
	There are three initial stacks of disks, identical except for color
	(Red, White and Blue).  A disk can be placed atop another of greater OR
	equal size.  "Rotate" the three stacks of disks.

6.  Clock
	The three pegs are placed in a circle.  Disks may only be moved one peg
	clockwise.  Move the entire stack two pegs clockwise.
T.RTitleUserPersonal
Name
DateLines
136.1TURTLE::GILBERTThu Aug 23 1984 18:3445
6.  Clock
	Let c1(d) be the cost of moving a stack of d disks one peg clockwise.
	Let c2(d) be the cost of moving a stack of d disks two pegs clockwise.

	Then c1(0) = c2(0) = 0, c1(1) = 1, c2(1) = 2, and
	c1(d) = c2(d-1) + 1 + c2(d-1)
	c2(d) = c2(d-1) + 1 + c1(d-1) + 1 + c2(d-1)

	Or,
	c2(d) = 2 c2(d-1) + 2 c2(d-2) + 3

	Letting f(d) = c2(d) + 1, then f(0) = 1, f(1) = 3, and
	f(d) = 2 f(d-1) + 2 f(d-2)

			d      d
	Then, f(d) = w x  + y z , where

	x = 1 + sqrt(3)
	z = 1 - sqrt(3)
	w = (3 + 2 sqrt(3))/6
	y = (3 - 2 sqrt(3))/6
			       2
	(x and z are roots of x  - 2 x - 2 = 0, w and y are chosen to fit the
	initial conditions).

	Thus,

		3 + 2 sqrt(3)		   d   3 - 2 sqrt(3)		  d
	c2(d) = ------------- (1 + sqrt(3))  + ------------- (1 - sqrt(3))  - 1
		     6				    6

					   d				  d
	c1(d) = (3 + sqrt(3)) (1 + sqrt(3))  + (3 - sqrt(3)) (1 - sqrt(3))  - 1

	Or (much prettier),

		sqrt(3) [	       d+1		  d+1 ]
	c1(d) = ------- [ (1 + sqrt(3))    + (1 - sqrt(3))    ] - 1
		   6	[				      ]

		sqrt(3) [	       d+2		  d+2 ]
	c2(d) = ------- [ (1 + sqrt(3))    + (1 - sqrt(3))    ] - 1
		  12	[				      ]

					- Gilbert
136.2TURTLE::GILBERTMon Aug 27 1984 07:5984
4.  Patriot

	The following set of 11 recurrence relations yields a solution for
	the patriot mutant.  P(n) is the number of moves required to move
	n disks from one peg to another, and p(1)=q(1)=...=z(1)=1.
	For large n, p(n) seems to grow as: k * x^n, where x is a root of
	2x^2 + x = 13 (for the thirteen original colonies, of course!).

	The derivation of these equations is not particularly difficult,
	except that the notation gets pretty gruesome.

	Note that there are 4 relations which may be solved independently
	of the other 7 (namely, s,w,v and z, marked with an "*").  Also,
	no two of the 11 functions happen to be identical.

		p(i) =	2*q(i-1) + 1
		q(i) =	q(i-1) + r(i-1) + 1
		r(i) =	s(i-1) + t(i-1) + u(i-1) + 2
	*	s(i) =	v(i-1) + w(i-1) + 1
		t(i) =	s(i-1) + x(i-1) + 1
		u(i) =	v(i-1) + y(i-1) + 1
	*	v(i) =	2*s(i-1) + z(i-1) + 2
	*	w(i) =	2*v(i-1) + 1
		x(i) =	r(i-1) + u(i-1) + 1
		y(i) =	2*r(i-1) + 1
	*	z(i) =	2*s(i-1) + 1

	A small table of p(n) follows.
					- Gilbert


	Table of p(n), for n < 50

	 n	    p(n)
	 - ------------------
	 1                  1
	 2                  3
	 3                  7
	 4                 19
	 5                 43
	 6                 99
	 7                235
	 8                535
	 9               1239
	10               2879
	11               6619
	12              15323
	13              35451
	14              81823
	15             189263
	16             437543
	17            1011059
	18            2337731
	19            5403987
	20           12491223
	21           28877687
	22           66755519
	23          154315883
	24          356738411
	25          824668747
	26         1906384015
	27         4407016991
	28        10187707927
	29        23550975203
	30        54442996563
	31       125856166851
	32       290942533447
	33       672573989511
	34      1554793681263
	35      3594227304667
	36      8308800562043
	37     19207511250747
	38     44402137601023
	39    102644731732399
	40    237284539657159
	41    548532326102867
	42   1268046007224291
	43   2931350797033395
	44   6776424099061175
	45  15665106892563351
	46  36213136933143071
	47  83714161449950539
	48 193522611430039179
	49 447367571779515947
136.3HARE::STANMon Sep 03 1984 21:476
The reference is

Joe Celko, Mutants of Hanoi (Problems and Puzzles). ABACUS. Vol 1 No. 3 (1984)
		pp. 54-57.

The Problems and Puzzles editor is Richard V. Andreee, University of Oklahoma.
136.4SULTAN::MEIERMon Sep 03 1984 22:46133
	For the people that haven't seen the execution of
	the solution of the Tower's of Hanoi?

	Here's a simple graphical program that could
	show the use the results of the method of solution

	I wrote the program in C for the Recursiveness.


	Required DCL:

		$ CC HANOI
		$ LINK HANOI,SYS$LIBRARY:CRTLIB.OLD
		$ HANOI == "$SYS$DISK:[]HANOI.EXE"
		$ Hanoi 3
/*
 * Hanoi.
 */
#include stdio.h

int	top[3]	= { 22, 22, 22 };
int	atoi(), fprintf(), printf();

main(argc, argv)
char *argv[];
{
	register int n;

	if (argc == 0) {
		argc = 2;
		argv[0] = "hanoi";
		argv[1] = "5";
	}
	if (argc < 2) {
		fprintf(stderr, "Arg. count!\n");
		exit(1);
	}
	n = atoi(argv[1]);
	if ( n < 0 || n > 13 ) {
		fprintf(stderr, "Bad number of rings!\n");
		exit(1);
	}
	setup(n);
	hanoi(n, 0, 2, 1);
}

hanoi(n, a, b, c)
{
	if (n == 0)
		return;
	hanoi(n-1, a, c, b);
	movering(n, a, b);
	hanoi(n-1, c, b, a);
}

setup(n)
{
	register i;

	printf("\033[2J");
	for ( i = 11; i < 23; ++i ) {
		cput(15, i, '|');
		cput(40, i, '|');
		cput(65, i, '|');
	}
	curse(5, 23);
	for ( i = 5; i < 76; ++i )
		putchar('-');
	for ( i = n; i > 0; --i )
		draw(i, 15, top[0]--, 'x');
}

curse(x, y)
{
	printf("\033[%d;%dH", y+1, x+1);
}

cput(x, y, c)
{
	curse(x, y);
	putchar(c);
}

draw(ring, centre, y, ch)
{
	register int i;

	curse(centre-ring, y);
	for ( i = 0; i < ring; ++i  )
		putchar(ch);
	curse(centre+1, y);
	for ( i = 0; i < ring; ++i )
		putchar(ch);
}

movering(ring, from, to)
{
	int fromc, toc;
	int fromy, toy;

	fromc = 15 + from*25;
	toc = 15 + to*25;
	fromy = ++top[from];
	toy = top[to]--;
	while (fromy != 10) {
		draw(ring, fromc, fromy, ' ');
		draw(ring, fromc, --fromy, 'x');
	}
	if (fromc < toc) 
		while (fromc != toc) {
			cput(fromc-ring, fromy, ' ');
			cput(fromc, fromy, 'x');
			cput(fromc+1, fromy, ' ');
			cput(fromc+ring+1, fromy, 'x');
			++fromc;
		}
	else if (fromc > toc)
		while (fromc != toc) {
			cput(fromc+ring, fromy, ' ');
			cput(fromc, fromy, 'x');
			--fromc;
		}
	while (fromy != toy) {
		draw(ring, fromc, fromy, ' ');
		draw(ring, fromc, ++fromy, 'x');
	}
}
	
	Have fun with it.....


		Al Meier

136.5TURTLE::GILBERTSun Sep 30 1984 04:173
There's also a Towers of Hanoi, done in "one DCL procedure", in
HARE::SYS$GAMES:HANOI.COM.  Warning - It talks VT52 escape sequences,
so set your terminal appropriately beforehand.
136.6TURTLE::GILBERTWed Oct 17 1984 17:3743
For the patriot mutant, moving a stack of n disks requires p(n) moves,

		    n	     n	      n	       n	n
	p(n) = a0 r0  + a1 r1  + a2 r2  + a3 r3  + a4 r4  +

		    n	     n	      n	       n
	     + a5 r5  + a6 r6  + a7 r7  + a8 r8  + a9,

				  4	 2
Where r0 through r3 are roots of r  - 2 r  - 6 r - 4 = 0,

	r0 =	 2.31170698134063,
	r1 =	-0.81444031337008,
	r2 =	-0.74863333398527 + 1.25064102146243 * i,
	r3 =	-0.74863333398527 - 1.25064102146243 * i,

				5      2
And r4 through r8 are roots of r  - 3 r  - 2 = 0,

	r4 =	 1.56303765441336,
	r5 =	 0.06210288664806 + 0.79369475055732 * i,
	r6 =	 0.06210288664806 - 0.79369475055732 * i,
	r7 =	-0.84362171385475 + 1.14330501709387 * i,
	r8 =	-0.84362171385475 - 1.14330501709387 * i,

And the coefficients a0 through a9 are

	a0 =	 0.65759432442712,
	a1 =	 0.04589563937290,
	a2 =	 0.06245317948915 - 0.05876363440754 * i,
	a3 =	 0.06245317948915 + 0.05876363440754 * i,

	a4 =	 0.04412890243680,
	a5 =	 0.05973351224700 - 0.05356885709716 * i,
	a6 =	 0.05973351224700 + 0.05356885709716 * i,
	a7 =	-0.13235976121822 + 0.08472845082312 * i,
	a8 =	-0.13235976121822 - 0.08472845082312 * i,

	a9 =	-0.72727272727272.

Unfortunately, I see no obvious structure of a0 through a8.

					- Gilbert