{"id":347,"date":"2014-11-09T21:00:44","date_gmt":"2014-11-10T05:00:44","guid":{"rendered":"http:\/\/mostlymental.com\/?p=347"},"modified":"2014-11-24T19:36:16","modified_gmt":"2014-11-25T03:36:16","slug":"towers-of-hanoi","status":"publish","type":"post","link":"http:\/\/mostlymental.com\/?p=347","title":{"rendered":"Towers of Hanoi"},"content":{"rendered":"

Hello everyone!<\/p>\n

I'm back, and I've got lots of exciting math to share, so let's get to it!\u00a0 This week, I'd like to talk about a classic puzzle called the Towers of Hanoi.\u00a0 To start, we have a board with three pegs, as shown below, one of which has a stack of disks on it.\u00a0 We want to move all the disks from the starting peg to either of the other pegs.\"hanoi_basic\"<\/a>However, we have two constraints: we can only move one disk at a time, from one peg to another, and we can never place a disk on top of a smaller disk.\u00a0 So in the example below, we can move the middle disk onto the larger disk on the left, but not the smaller disk on the right.\"hanoi_move\"<\/a><\/p>\n

 <\/p>\n

So how do we solve it?\u00a0 The key insight here is that a disk can only move when all the smaller disks are stacked on another peg.\u00a0 So in the example below, we can only move the red disk to the third peg once we've moved the yellow, green, and blue disks to the second.\u00a0 So the problem of moving all four disks can be broken down into moving the top three to another peg, moving the largest disk, then moving the top three back on top of the largest. \"hanoi_recurse\"<\/a>This brings up an important concept.\u00a0 We've taken the problem with \"\"<\/span>