Proof Wanted
Difference between en1 and en2, changed 2 character(s)
> There are four towers who is named A,B,C,D respectively.↵
>↵
> Initially there are n disks
,. All disks are different in size.↵
>↵
> The disks are initially stacked on tower A increasing in size from the top to the bottom.↵
>↵
> You can't put disk A onto disk B if the size of disk A is bigger than the size of disk B.↵
>↵
> The goal is to transfer all of the disks from tower A to tower D with smallest amount of options.↵
↵
Above all is the description of the problem.↵
↵
The solution uses $f(n)$ to represent the minimum times to transfer n disks increasing in size from the top to the bottom from tower A to tower D. And it uses $d(n)$ to represent the minimum times to transfer n disks increasing in size from the top to the bottom from tower A to tower C without the help of tower D (It means you can't stack disks on tower D).↵
↵
Then the solution claims that $f(n) = min(2 \times f(i) + d(n - i)) (1 \le i < n)$, but I don't know why. Please give me a proof,thanks!↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English 040902fyn 2021-10-19 02:59:02 2 Tiny change: 're n disks, All disks' -> 're n disks. All disks'
en1 English 040902fyn 2021-10-18 06:01:13 987 Initial revision (published)