Tower of Hanoi (alternative version)

“I can’t do it,” sighs the Ninja Monkey.

“Now what?” I ask

“It’s the legend of the Flowers of Hanoi,” replies Monkey. “Something I learnt from the Bad Idea Bears.”

“I know you often mention the Flowers of Hanoi during Spider Solitaire lessons,” says Bad Idea Bear #1. “We asked our friends about it, and eventually figured out the rules.”

This cannot be good. Yes, the Bad Idea Bears have inquisitive minds, an essential quality for anyone who does a Ph. D., but it’s a pity their math fundamentals are 83,72,73,84.

In front of the Monkey are a pile of five flowers, surrounded by a large square. Each flower lies atop another flower of slightly smaller size. There are two more squares of the same size, but do not contain any flowers.”

“The Bad Idea Bears say I should be able to shift all the flowers to one of the other squares in 30 moves, but the best I can do is 31.”

“Shouldn’t be too hard,” I say. “After all, thanks to an extremely fast metabolism you are able to complete 200 games of Spider Solitaire in three minutes if you pretend it’s played at the one-suit level. But this puzzle only involves five flowers instead of 104. How hard can it be?”

“But there’s a catch. You can only move one flower at a time – and no flower can be on top of a smaller flower.”

“Of course if this were Spider Solitaire then you can do it in one move, since all flowers are the same colour.”

“Yes that is true,” chuckles Ninja Monkey. “The game does have similarities with Flowers of Hanoi. I find I often need to make many moves just to expose one more card. But perhaps my Random Move algorithms aren’t all they’re cracked up to be.”

“Don’t be too hard on yourself. You’ve already achieved a lot with Four Suit Spider Solitaire. Everybody treats you with respect, and we won $3000 dollars from the Eagle last …”

“For 70,85,67,75,78 sake,” says the Eagle. “You don’t need to bring that up every third day of the month.”

“Why do the Bad Idea Bears think it’s possible in 30 moves?” I ask.

“I was wondering about that as well,” says the Bad Idea Bear #1. “But we finally figured out the pattern. We started by considering what happens with fewer than 5 flowers.”

BIB #1 draws a large circle in the dirt. He chooses two random points A and B on the circle and draws a line connecting the points. The two resulting regions in the circle are labelled 0 and 1.

“With only one flower, it takes one move to shift all flowers from one square to another,” says BIB #2

I nod in agreement. So far no ground-breaking discoveries yet.

BIB #2 draws a new circle in the dirt but with three vertices A,B,C and lines connecting all pairs of points. Now there are four regions numbered 0,1,2,3.

“With two flowers, we need three moves to shift all flowers to a different square.”

Again I nod in agreement.

The Bad Idea Bears draw three more similar diagrams but with four, five, and six vertices and lines connecting all pairs of vertices.

“Continuing in this manner,” says BIB #1, “we find seven moves are required to shift three flowers, fifteen moves for four flowers and thirty moves for five flowers. In every case Ninja Monkey has found a solution with the correct number of moves – except the last one.”

I examine the BIB’s artwork carefully. They have indeed correctly counted 30 regions in the last diagram. And they can draw diagrams faster than the Wise Snail, I’ll give them that.

“At first we thought it should be 29 regions in the last diagram,” says BIB #2 “but we eventually figured out that no three lines should intersect at a single point. Unfortunately Ninja Monkey has never been able to do it in 30 moves. He can do 7 moves with three flowers and 15 moves with four flowers but the best he can do is 31 moves with five flowers.”

I look in the Monkey’s direction – unfortunately he seems to have knocked himself out, and it doesn’t take long to work out why.

Oh well. At least I was brought up right by Mom and Dad. For one thing, I never scratch my 66,85,77 and/or pick my nose in public.

THE END