Topswops
Topswops (and the variants Topdrops, Bottomswops and Bottomdrops) are mathematical problems devised and analysed by the British mathematician John Conway in 1973. Contrary to other games and problems introduced by Conway, these problems have not received much attention from the scientific community. Two famous mathematicians who have contributed to the problem are Martin Gardner and Donald Knuth. Formulation. In each variant of the problem, Conway uses a deck of playing cards. Since the numerical values of the deck are only relevant, only one suit is used. This is mathematically equivalent to a row of integers from formula_1 to formula_2 . A shuffled pile of cards is written as formula_3. Topswops. For "topswops" the following algorithm is applied: The final configuration of the row always starts with formula_1. The "topswops" problem is occasionally named differently, with naming including "deterministic pancake problem", "topswops", "topswaps", "reverse card shuffle" and "fannkuch". The problem formulated by Conway is the following: In literature there are some attempts to find lower and upper bounds for the number of iterations formula_8. Theorem: formula_8 is bounded by formula_10. Proof by Herbert S. Wilf: Consider a permutation formula_4 to formula_12 of the row formula_1 to formula_2. As an example, we  consider formula_15. We are specifically interested in numbers which are at 'the correct position'. These are: 2, 5, 9, 10, 12. We define the Wilf number as formula_16. Claim: after each iteration of the algorithm, the Wilf number increases. Proof: We perform one iteration of the algorithm. Every number at 'the correct position' and larger than formula_4, leaves the Wilf number unchanged. The remaining numbers at 'the correct position' will in general not be at 'the correct position' anymore. Nevertheless, the formula_4's number is at the correct position. And since the sum of the first formula_19 Wilf numbers is  always smaller than the Wilf number of formula_4, the total Wilf number always increases (with at least 1 per iteration of the algorithm). formula_21 The maximal Wilf number is found when each number is at the correct position. So the maximal Wilf number is formula_22. By refining the proof, the given upper bound can be proven to be a real upper bound for the number of iterations. formula_21 Theorem: formula_8 is bounded by the formula_25th Fibonacci number. Proof by Murray S. Klamkin: Suppose that during the algorithm, the first number formula_4 takes on in total formula_27 distinct values. Claim: formula_28 . Proof: We prove the claim by mathematical induction. For formula_29, the algorithm directly terminates, hence, formula_30. Thus formula_31 and since formula_32 the claim is proven. We now take some formula_33. All formula_27 values that formula_4 takes on, are ordered and can be written as: formula_36. Suppose that the largest value of these values, which is formula_37, occurs for the first time at position formula_1 during iteration formula_39 of the algorithm. Denote formula_40. During the formula_41'th iteration, we know formula_42 and formula_43. The remaining iterations will always retain formula_43. Hence formula_4 can now take on at most formula_46 values. Using induction  for formula_27, it follows that formula_48 and also that formula_49. formula_21 Suppose we would exchange formula_49 and formula_37 in iteration formula_39 Then formula_31 and the algorithm terminates; formula_55. During the algorithm, we are sure that both formula_37 and formula_57 have never been at position formula_4, unless formula_59. Suppose formula_59. Then formula_61 since formula_4 takes on at most formula_46 distinct values. So it follows that formula_64. Suppose formula_65. Then formula_66 since formula_4 takes on at most formula_68 distinct values. Using the claim, it follows that formula_69. This proves the theorem. formula_21 Besides these results, Morales and Sudborough have recently proven that  the lower bound for formula_8 is a quadratic function in formula_2. The optimal values are, however, still unknown. There have been several attempts to find the optimal values, for example by A. Pepperdine. For rows with 17 or fewer numbers, the exact solution is known. Larger rows only have lower bounds, which is shown on the right. It is yet unknown whether this problem is NP-hard. Topdrops. A similar problem is "topdrops", where the same playing cards are used. In this problem, the first card of the pile is shown (and has value formula_4). Take the first formula_4 cards  of the pile, change the order and place them back on the bottom of the pile (which contrasts "topswops", where the cards are placed at the top). This problem allows for infinite loops. As an example, we consider the row 2,1,3,4. By applying the algorithm, the following sequence is obtained: whereafter the original row is found again. Botswops. In this variant, the bottom card of the pile is taken (and again named formula_4). Then the first formula_4 cards of the pile are swapped. Unless the bottom card is the highest card in the pile, nothing happens. This makes the problem  uninteresting due to the limited behaviour. Botdrops. The final variant is "botdrops" where the bottom card of the pile is taken (again formula_4). In this variant, the bottom formula_4 cards are swapped.