Let a stack of pancakes with different sizes be given. A spatula is a tool to flip over pancakes. If you put the spatula under the -th pancake from the top, all top to the -th pancakes are flipped over and placed in the reverse order (Fig.1). Let us rearrange the stack using a spatula so that the smallest pancake appears on the top of the stack, monotonically increasing the size, and the largest at the bottom, which we call "ordered-state". We assume that both sides of each pancake are identical and we know which pancake is the -th biggest in advance. From now, we use this pancake-number to identify the pancake. A "stack-state" is denoted by the sequence of pancake-numbers from the top to the bottom. For example, using our notation, state transitions in Fig. 1 are described as in Fig. 2. Answer the following questions.
(1) For , draw a state transition graph, whose vertices are "stack-states" and arcs are transitions by a spatula. Fig. 3 shows one example of the state transition graph for .
(2) For , give an example of "stack-state" which requires the maximum number of flips to reach "ordered-state", and the corresponding number of flips.
(3) For , give an example of "stack-state" which requires the maximum number of flips to reach "ordered-state", and the corresponding number of flips.
(4) For general , describe an algorithm for rearrangement to reach "ordered-state" and give its time complexity.
