Author |
Topic: Average Hanoi (Read 824 times) |
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
 |
Average Hanoi
« on: Dec 16th, 2008, 1:38pm » |
 Quote  Modify
|
Suppose the n disks are randomly distributed among the 3 pegs in a standard Tower of Hanoi puzzle, with each of the 3n 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  2n x  .
3b) Show that x is irrational.
3c) Does every finite binary string appear somewhere in the binary expansion of x?
|
| « Last Edit: Dec 17th, 2008, 6:41pm by Eigenray » |
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Average Hanoi
« Reply #1 on: Dec 17th, 2008, 2:46am » |
Quote Modify
|
If the final peg is given (i.e. you cannot choose) I find:
2/3*(2^n-1)
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Average Hanoi
« Reply #2 on: Dec 17th, 2008, 10:45am » |
Quote Modify
|
Correct. Interesting that it is exactly two-thirds of the worst case.
There is a simple relationship between the two cases, when you can pick the final peg and when you can't.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Average Hanoi
« Reply #3 on: Dec 17th, 2008, 11:27am » |
Quote Modify
|
Assuming Grimbal's result for the fixed destination to be correct, I get the following for the case where you can choose: | hidden: | | 2/3 * (2n-1-1) for n>0 or 0 when n=0 |
Reasoning:
| hidden: | | 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 3n-1 possible arrangements equally likely - in other words, the exact problem for n-1 disks |
edit: miscopied Grimbal's formula...
|
| « Last Edit: Dec 17th, 2008, 11:31am by rmsgrey » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Average Hanoi
« Reply #4 on: Dec 17th, 2008, 12:02pm » |
Quote Modify
|
on Dec 17th, 2008, 11:27am, rmsgrey wrote:| The optimum choice of destination is obviously the peg where the largest disk starts. |
|
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?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Average Hanoi
« Reply #5 on: Dec 17th, 2008, 1:57pm » |
Quote Modify
|
on Dec 17th, 2008, 12:02pm, 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.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Average Hanoi
« Reply #6 on: Dec 17th, 2008, 3:32pm » |
Quote Modify
|
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 2n x . How explicitly can you describe x?
|
| « Last Edit: Dec 17th, 2008, 4:54pm by Eigenray » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Average Hanoi
« Reply #7 on: Dec 18th, 2008, 1:24am » |
Quote Modify
|
on Dec 17th, 2008, 3:32pm, 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?
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Average Hanoi
« Reply #8 on: Dec 18th, 2008, 11:48am » |
Quote Modify
|
on Dec 17th, 2008, 3:32pm, 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.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
More generally, for any 0 < t < 1, we can consider M(t,n), the 3n t - th smallest distance out of the 3n configurations. Then M(t,n)/2n converges to a real number F(t). In fact, we have
M(t,n) = 2n F(t) .
What is the recursive formula for F(t)?
Attached is a graph of F(t) - t. Look familiar? What's the connection?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Average Hanoi
« Reply #10 on: Dec 22nd, 2008, 7:08am » |
Quote Modify
|
Ask Sierpinski.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print