Answer to Problem of the Month for 10/2014

Arka Roychowdhury sent me an interesting game that he made up. In one of the variations of the game, you are given a tower with discs on it. You may flip the discs on the tower in the following ways: you may flip the top disc, the top 2 discs, ... or all the discs. All the discs start out blue. Whenever a disc touches the bottom, it turns to red. The object of the game is to turn all the discs to red.

Here is an example with three discs:

Initial Position Flipping all 3 discs Flipping top 2 discs Flipping all 3 discs

What is the least number of flips needed to turn all the discs to red on a a tower containing 20 discs?

You can check out Arka's game for the iphone by clicking here

Solution to the Problem:
The answer is 37 flips.

Here is a chart showing the number of flips needed to turn all the discs to red:

Discs Flips

2 1

3 3

4 5

5 7

6 9

7 11

8 13

9 15

10 17

11 19

12 21

13 23

14 25

15 27

16 29

17 31

18 33

19 35

20 37

James Alarie sent in a nice explanation:
For N pancakes, the minimum number of flips will be 2N-3 and there will be (N-2)! ways of doing it. For the N=20 given in the problem, you will need 220-3=37 moves and there will be 18!=6,402,373,705,728,000 ways of doing it. The easiest way will be to flip 20, 19, 20, 19, 20, 19, 20, 19, 20, 19, 20, 19, 20, 19, 20, 19, 20, 19, 20, 19, 20, 19, 20, 19, 20, 19, 20, 19, 20, 19, 20, 19, 20, 19, 20, 19, 20.
Chad Fore also sent in the 2n-3 formula for the number of flips where n is the number of disks.

Correctly solved by:

1. James Alarie	Flint, Michigan
2. Brooks Garris	Lake View High School, Dillon, South Carolina
3. Rick Bessey	John Paul II Catholic High, Tallahassee, Florida
4. Chad Fore	Gate City, Virginia