That article appears to be partly wrong and partly misleading. The game is described in a way that makes no sense and so the significance of the new proof is not made clear. I think this is more accurate:
In topswops we start with a shuffled deck of N cards numbered 1..N. In each move we reverse the order of the top K cards where K is the number initially on the top card. (After that reversal, the original top card, K, is now the Kth card down and the formerly Kth card down is now the top card. Any cards in between have reversed order.)
The game terminates when the card number 1 comes to the top. (For reversing the order of a single card has no effect.)
Here is what the article leaves out: If, when 1 comes to the top, the deck is sorted 1..N, you win. Otherwise, you lose. This is a very tedious form of solitaire.
Note that if your shuffle produces an already sorted deck, you win trivially with 0 moves: the deck is already sorted and 1 is on top! If the shuffle produces a reverse sorted deck, N..1, you win trivially after 1 move!
If someone hands you a different shuffle, you might be playing for a very long time, uncertain whether you will win or lose.
For every deck-size N, there is some number of moves - call it ENOUGH(N) - such that if you haven't won in ENOUGH(N) moves, then you will not win with that deck. For example, if the deck has 12 cards, and you've been playing for 64 moves ... why you might as well quit. We know for sure that any shuffle that wins ends after at most 63 moves for a deck of size 12. ENOUGH(12) is 63. [supposedly, I haven't double checked the brute-force proof]
What is the formula for ENOUGH(N)? or at least an approximate formula?
For values of N up to (the article says) size 18, ENOUGH(N) has been computed by brute force.
Knuth gave a formula KNUTHTOPS(N) and proved that ENOUGH(N) <= KNUTHTOPS(N). His proof was interesting because, asymptotically, KNUTHTOPS(N) is lowest upper bound known. You can confidently stop a losing game after KNUTHTOPS(N) moves -- but it is possible you could have stopped earlier if you had a better formula.
These new guys gave a formula, HALnLINDAWOPS(N), and proved that HALnLINDAWOPS(N) <= ENOUGH(N). HALnLINDAWOPS(N) is interesting for being the highest lower bound known. Don't even think about stopping until you've made at least HALnLINDAWOPS(N) moves or you are guaranteed, in some cases, to quit part way through a winning shuffle.
The number at which you can quit safely, no fear of stopping a winning game, is between HALnLINDAWOPS(N) and KNUTHTOPS(N) (inclusive). The main advance is squeezing that range from below with a new proof.
In topswops we start with a shuffled deck of N cards numbered 1..N. In each move we reverse the order of the top K cards where K is the number initially on the top card. (After that reversal, the original top card, K, is now the Kth card down and the formerly Kth card down is now the top card. Any cards in between have reversed order.)
The game terminates when the card number 1 comes to the top. (For reversing the order of a single card has no effect.)
Here is what the article leaves out: If, when 1 comes to the top, the deck is sorted 1..N, you win. Otherwise, you lose. This is a very tedious form of solitaire.
Note that if your shuffle produces an already sorted deck, you win trivially with 0 moves: the deck is already sorted and 1 is on top! If the shuffle produces a reverse sorted deck, N..1, you win trivially after 1 move!
If someone hands you a different shuffle, you might be playing for a very long time, uncertain whether you will win or lose.
For every deck-size N, there is some number of moves - call it ENOUGH(N) - such that if you haven't won in ENOUGH(N) moves, then you will not win with that deck. For example, if the deck has 12 cards, and you've been playing for 64 moves ... why you might as well quit. We know for sure that any shuffle that wins ends after at most 63 moves for a deck of size 12. ENOUGH(12) is 63. [supposedly, I haven't double checked the brute-force proof]
What is the formula for ENOUGH(N)? or at least an approximate formula?
For values of N up to (the article says) size 18, ENOUGH(N) has been computed by brute force.
Knuth gave a formula KNUTHTOPS(N) and proved that ENOUGH(N) <= KNUTHTOPS(N). His proof was interesting because, asymptotically, KNUTHTOPS(N) is lowest upper bound known. You can confidently stop a losing game after KNUTHTOPS(N) moves -- but it is possible you could have stopped earlier if you had a better formula.
These new guys gave a formula, HALnLINDAWOPS(N), and proved that HALnLINDAWOPS(N) <= ENOUGH(N). HALnLINDAWOPS(N) is interesting for being the highest lower bound known. Don't even think about stopping until you've made at least HALnLINDAWOPS(N) moves or you are guaranteed, in some cases, to quit part way through a winning shuffle.
The number at which you can quit safely, no fear of stopping a winning game, is between HALnLINDAWOPS(N) and KNUTHTOPS(N) (inclusive). The main advance is squeezing that range from below with a new proof.