The Tower of Hanai puzzel is to move the entire stack of disks from peg A to peg C with the help of peg B. Initially, peg A has n disks, with a smaller disk placed on top of a larger disk, peg B and peg C are empty. Moving a disk is subject to the following rules:

Only one disk may be moved at a time.

Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty peg.

No disk may be placed on top of a disk that is smaller than it

Let T(n) denote the smallest number of moves for moving the entire n disks from one peg to another. Then T(n) cannot be solved in polynomial time because T(n) = 2ⁿ - 1.

a)True

b)False