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.

A Topswops example with numbers. The algorithm ends after 7 iterations.

Formulation

edit

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   to  . A shuffled pile of cards is written as  .

Topswops

edit

For topswops the following algorithm is applied:

  1. Consider the first card from the pile (which is  )
  2. Take the first   cards from the pile
  3. Swap these cards and place them back on the pile
  4. Repeat step 1, 2 and 3 until the top card is  

The final configuration of the row always starts with  . The topswops problem is occasionally named differently, with naming including deterministic pancake problem, topswops, topswaps, reverse card shuffle and fannkuch.[1][2][3]

The problem formulated by Conway is the following:

Which initial configuration leads to the maximum number of 'swops' before the algorithm terminates?

In literature there are some attempts to find lower and upper bounds for the number of iterations  .

Theorem:   is bounded by  .

Proof by Herbert S. Wilf:[2] Consider a permutation   to   of the row   to  . As an example, we consider  . 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  .

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  , leaves the Wilf number unchanged. The remaining numbers at 'the correct position' will in general not be at 'the correct position' anymore. Nevertheless, the  's number is at the correct position. And since the sum of the first   Wilf numbers is always smaller than the Wilf number of  , the total Wilf number always increases (with at least 1 per iteration of the algorithm).  

The maximal Wilf number is found when each number is at the correct position. So the maximal Wilf number is  . By refining the proof, the given upper bound can be proven to be a real upper bound for the number of iterations.  

 
Topswops: the relation between   and   in a semi-logarithmic graph. The upper bound is loose, whereas the lower bound is quite tight.
 
Topswops: the expected relation between   and   in a double logarithmic graph. The data points in the graph are only some permutated rows, and are lower bounds of the real value. The upper bound is again very loose, whereas the lower bound is relatively tight.

Theorem:   is bounded by the  th Fibonacci number.

Proof by Murray S. Klamkin:[4] Suppose that during the algorithm, the first number   takes on in total   distinct values.

Claim:  .

Proof: We prove the claim by mathematical induction. For  , the algorithm directly terminates, hence,  . Thus   and since   the claim is proven.

We now take some  . All   values that   takes on, are ordered and can be written as:  . Suppose that the largest value of these values, which is  , occurs for the first time at position   during iteration   of the algorithm. Denote  . During the  'th iteration, we know   and  . The remaining iterations will always retain  . Hence   can now take on at most   values. Using induction for  , it follows that   and also that  .  

Suppose we would exchange   and   in iteration   Then   and the algorithm terminates;  . During the algorithm, we are sure that both   and   have never been at position  , unless  .

Suppose  . Then   since   takes on at most   distinct values. So it follows that  .

Suppose  . Then   since   takes on at most   distinct values. Using the claim, it follows that  . This proves the theorem.  

Besides these results, Morales and Sudborough have recently proven that the lower bound for   is a quadratic function in  .[1] The optimal values are, however, still unknown. There have been several attempts to find the optimal values, for example by A. Pepperdine.[5] For rows with 19 or fewer numbers, the exact solution is known. Larger rows only have lower bounds, which is shown on the right.

row length 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
maximal number of iterations 0 1 2 4 7 10 16 22 30 38 51 65 80 101 113 139 159 191 221

It is yet unknown whether this problem is NP-hard.

Topdrops

edit

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  ). Take the first   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:

  • 2 1 3 4
  • 3 4 1 2
  • 2 1 4 3
  • 4 3 1 2
  • 2 1 3 4

whereafter the original row is found again.

Botswops

edit

In this variant, the bottom card of the pile is taken (and again named  ). Then the first   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.[2]

Botdrops

edit

The final variant is botdrops where the bottom card of the pile is taken (again  ). In this variant, the bottom   cards are swapped.

References

edit
  1. ^ a b Morales, Linda; Sudborough, Hal (2010). "A quadratic lower bound for Topswops" (PDF). Theoretical Computer Science. 411 (44–46): 3965–3970. doi:10.1016/j.tcs.2010.08.011.
  2. ^ a b c Gardner, Martin (1987). "6". Time Travel and Other Mathematical Bewilderments. New York: W. H. Freeman & Co. pp. 76–82. ISBN 978-0716719250.
  3. ^ Knuth, Donald E. (2002). The Art of computer programming: Volume 4, Fascicle 2A: Generating all n-tuples. Addison-Wesley. pp. 74, 119–120. ISBN 978-0201853933.
  4. ^ Klamkin, Murray S. (1990). Problems in Applied Mathematics: Selections from SIAM review. SIAM. pp. 74, 115–117. ISBN 978-0898712599.
  5. ^ Pepperdine, Andy (1989). "73.23 Topswops". The Mathematical Association. 73 (464): 131–133. doi:10.2307/3619674. JSTOR 3619674. A renewed version of the article can be found on https://www.pepsplace.org.uk/Trivia/Topswops/Topswops.pdf. {{cite journal}}: External link in |quote= (help)
edit