wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Average Hanoi
        
(Message started by: Eigenray on Dec 16^th, 2008, 1:38pm)

Title: Average Hanoi
Post by Eigenray on Dec 16^th, 2008, 1:38pm

Suppose the n disks are randomly distributed among the 3 pegs in a standard Tower of Hanoi puzzle, with each of the 3ⁿ legal positions equally likely.

1) What is the expected number of moves required to get all the disks onto the same peg? (The choice of final peg depends on the initial configuration.)

2) In the limit, how many standard deviations above the mean is the worst case?

3a) Show that there exists a real number x such that for all n, the median number of moves required is http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gif 2ⁿ x http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif.

3b) Show that x is irrational.

3c) Does every finite binary string appear somewhere in the binary expansion of x?

Title: Re: Average Hanoi
Post by Grimbal on Dec 17^th, 2008, 2:46am

If the final peg is given (i.e. you cannot choose) I find:
[hide]2/3*(2^n-1)[/hide]

Title: Re: Average Hanoi
Post by Eigenray on Dec 17^th, 2008, 10:45am

Correct. Interesting that it is exactly [hide]two-thirds of the worst case[/hide].

There is a simple relationship between the two cases, when you can pick the final peg and when you can't.

Title: Re: Average Hanoi
Post by rmsgrey on Dec 17^th, 2008, 11:27am

Assuming Grimbal's result for the fixed destination to be correct, I get the following for the case where you can choose: [hideb]2/3 * (2^n-1-1) for n>0 or 0 when n=0[/hideb]

Reasoning:
[hideb]The optimum choice of destination is obviously the peg where the largest disk starts. Once you choose that peg, you then have n-1 disks to pile on a specified peg with each of the 3^n-1 possible arrangements equally likely - in other words, the exact problem for n-1 disks[/hideb]

edit: miscopied Grimbal's formula...

Title: Re: Average Hanoi
Post by Eigenray on Dec 17^th, 2008, 12:02pm

on 12/17/08 at 11:27:19, rmsgrey wrote:

[hide]The optimum choice of destination is obviously the peg where the largest disk starts.[/hide]

This is true but I wouldn't say it's obvious...

A slightly harder followup: in the limit, how many standard deviations above the mean is the worst case?

And harder still: What is the median number of moves?

Title: Re: Average Hanoi
Post by Grimbal on Dec 17^th, 2008, 1:57pm

on 12/17/08 at 12:02:32, Eigenray wrote:

This is true but I wouldn't say it's obvious...

Obviously, to move the largest disk, you must have all other disks on one peg. And in that situation, moving the large disk is a logical non-operation.

Title: Re: Average Hanoi
Post by Eigenray on Dec 17^th, 2008, 3:32pm

Well, when you put it like that, yes, it is obvious. (But what isn't true in general is that to get from one configuration to another, you should move the largest disk at most once.)

Regarding the median, show that there exists a real number x such that for all n, the median number of moves with n disks is http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gif 2ⁿ x http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif. How explicitly can you describe x?

Title: Re: Average Hanoi
Post by Grimbal on Dec 18^th, 2008, 1:24am

on 12/17/08 at 15:32:51, Eigenray wrote:

But what isn't true in general is that to get from one configuration to another, you should move the largest disk at most once.

Hm... that's true. From that point of view, it was worth clearing it up.

Isn't that the job of mathematicians to break down non-obvious claims into obvious steps?

Title: Re: Average Hanoi
Post by rmsgrey on Dec 18^th, 2008, 11:48am

on 12/17/08 at 15:32:51, Eigenray wrote:

Well, when you put it like that, yes, it is obvious. (But what isn't true in general is that to get from one configuration to another, you should move the largest disk at most once.)

True.

The state-transition-graph of n-disk Towers of Hanoi can be drawn fairly naturally in a layout strongly reminiscent of Sierpinski's Gasket - with 1 disk, it's simply a triangle. For n+1 disks, it's three copies of the n-disk version, each with the largest disk on a different peg, connected at the corners by moves of the largest disk. With that graph in mind, it's obvious that the closest corner is always the one in the same third of the graph.

Title: Re: Average Hanoi
Post by Eigenray on Dec 22^nd, 2008, 4:40am

More generally, for any 0 < t < 1, we can consider M(t,n), the http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gif 3ⁿ t http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif - th smallest distance out of the 3ⁿ configurations. Then M(t,n)/2ⁿ converges to a real number F(t). In fact, we have
M(t,n) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gif 2ⁿ F(t) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gif.
What is the recursive formula for F(t)?

Attached is a graph of F(t) - t. Look [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1178638567#8]familiar[/link]? What's the connection?

Title: Re: Average Hanoi
Post by Grimbal on Dec 22^nd, 2008, 7:08am

Ask Sierpinski.