11
$\begingroup$

Recently, I've been given an interesting type of problem that I am having a difficult time proving. The problem revolves around a game, with the rules as follows:

"You have a deck containing n cards in random order. The top card has some number k on it. Take the top k cards off of the top of the deck, reverse their order, and put them back on top of the deck. A new number, r, is now at the top of the deck. Take r cards off the top of the deck, reverse their order, and put them back on top of the deck. Repeat this process until the game ends (Card #1 is at the top of the deck)."

The supposed outcome of the game is that it will take no more than F(n+1) - 1 "steps" to end the game. I have tried this experimentally, and have been able to verify the result for various values of n, but how to prove it is another story.

$\endgroup$
  • $\begingroup$ When you say "Card #1", do you mean the card with 1 on it or the card which started on top? Presumably the former as the latter may never terminate. I also assume the deck has numbers 1, 2, 3, ... $n$, though it might be worth saying so explicitly. $\endgroup$ – Henry Apr 16 '11 at 2:22
  • $\begingroup$ "Card #1" = The card with "1" on it. Your assumption is correct regarding 1, 2, 3, ... n cards being in the deck. $\endgroup$ – Trip Apr 16 '11 at 2:37
6
$\begingroup$

You can prove the game terminates by induction. A $1$ card deck terminates immediately. Now assume we have proven that it terminates for all decks up to $n$. If we imagine playing a game with $n+1$ cards, if card $n+1$ comes to the top of the deck, it will go to be bottom and can never enter play again. We are then playing an $n$ card game, which we know terminates. If card $n+1$ never comes to the top of the deck, we will never see the card on the bottom of the deck, so we can pretend it isn't there, in which case we are again playing an $n$ card game. So the game always terminates.

Added: I believe that an upper bound for the maximum number of turns is one less than the Fibonacci numbers, $F(n)$ with the index offset by $1$. Let $G(n)$ be the maximum number of turns for $n$ cards. $G(1)=0$ as card $1$ is on top. $G(2)=1$ for order $2,1$. $G(3)=2$ for order $3,1,2$ To find the recurrence, you don't want $1$ on the bottom or you will get it as soon as you find card $n$. So you are playing an $n-2$ card game which ends when you find card $n$ and haven't found card $1$. You play $1$ turn to put card $n$ on the bottom, then play an $n-1$ card game. So the recurrence is $G(n)=1+G(n-1)+G(n-2)$ To prove it by induction, note $G(1)=F(2)-1, G(2)=F(3)-1$ and assume we have proved it up to $n-1$, then $ G(n)=1+G(n-1)+G(n-2)=1+(F(n)-1)+(F(n-1)-1)=F(n+1)-1$

However, this assumes that you can play the $n-1$ card game avoiding $1$ for as many turns as an $n-2$ card game. For $4$ cards this works with the order $2413$ taking $4$ moves, and for $5$ it also works with $31452$ taking $7$. But for $6$ cards it fails. The way to find these is take the maximum series for $n-1$, put card $n$ on the bottom and work backwards. For $6$ you get stuck and $456213$ takes only $10$ turns. I haven't proven that there are no $11$ move decks.

$\endgroup$
  • $\begingroup$ Interesting point. It definitely terminates though... and concentrating on the highest numbered card seems to be a focal point. One thing I've noticed is that any card at the bottom of the pile can be unearthed only by having the high card at the top of the deck. So basically, the worst case scenario is that the "1" is at the bottom of the deck and you have to reveal the high card. $\endgroup$ – Trip Apr 16 '11 at 0:54
  • $\begingroup$ Well, the reason I put "1" at the bottom is that the only way it can come into play is if n is drawn. Then you can do the same thing again with one less card that says "what's the most turns it would take to get n to the top of the deck?" Using this backward induction I seem to be getting n - 1 turns, and can't seem to replicate a game with the Fibonacci offset - 1 for any reasonably high numbered deck of cards. $\endgroup$ – Trip Apr 16 '11 at 1:37
  • $\begingroup$ But if $1$ is on the bottom, you stop the turn after you find $n$. The decks I show are better, but I agree you won't reach my Fibonacci bound. Thanks for an interesting problem. $\endgroup$ – Ross Millikan Apr 16 '11 at 2:01
  • $\begingroup$ @Ross: I'm not sure your inductive argument holds when n+1 is not at the bottom. The "game" you are playing with the remaining cards is not the game you are inducting on, because it does not consist of cards number 1 through n. To take the extreme case Trip suggests, imagine the bottom card is 1, and "n+1 never shows up". Then the resulting n-card game never terminates, because you never see the 1 card. It's not clear in your argument why this cannot be the case. $\endgroup$ – Arturo Magidin Apr 16 '11 at 2:01
  • 1
    $\begingroup$ @Ross: I don't see it; the inductive argument seems to me to work, once you substitute the $n+1$. If $k$ is at the bottom and $n+1$ is not on top, place a sticker with $k$ on it on top of the $n+1$ card; now you are playing with the top $n$ cards number 1 through n, which by induction terminates. If at some point along the line before hitting 1 it hits the "pretend $k$" card, you tear off the sticker and this places $n+1$ on the bottom and you are back to the first case of your induction. If you get to 1 before hitting the "pretend $k$", it terminates as well. $\endgroup$ – Arturo Magidin Apr 16 '11 at 2:29
1
$\begingroup$

As Arturo Magidin pointed out, my induction in the last answer doesn't hold, so here is a proof of termination. There are a finite number of orders of $n$ cards without $1$ on top, specifically $n!-(n-1)!.$ If the game does not terminate, we must have a loop that comes back to a previously seen order. Consider $m$, the largest card seen in the course of playing through the loop. After we see it, it goes to position $m$ and no other card in the loop can retrieve it, and we will never see $m$ again. Therefore there is no loop.

$\endgroup$
  • $\begingroup$ Your argument is essentially fine; you just need to refine the induction a bit. See my last comment on that answer; that argument may also help you do the upper bound. $\endgroup$ – Arturo Magidin Apr 16 '11 at 2:23
  • $\begingroup$ This makes sense, but is there any way to show that that the F(n+1) - 1 rule holds as the maximum number of moves needed to terminate any game? I'm yet to find anything over n = 5 that will make these bounds work. $\endgroup$ – Trip Apr 16 '11 at 2:27
0
$\begingroup$

We had this exact problem as an exercise and after a lot of thinking in the past few days I think I finally found a proof that I want to present here:

For $n \in \mathbb{N}$ and $k \in [n]$, define a more general game $A_{n,k}$, where we this time have $k$ $1$-cards and $n-k$ other pairwise distinct cards that are all in $\{2,...,n\}$. Other than that, the rules shall be the same.

Let $\alpha_{n,k} := max(\{r \in \mathbb{N}\mid r$ is the number of rounds we play for some $A_{n,k} $ game$\})$. I claim that $\alpha_{n,k} \le f_{n+2-k}-1$ for all $n \in \mathbb{N}$, $k \in [n]$ and want to prove this using induction on $n$.

For the induction base we have $\alpha_{1,1} = 0 = f_2 -1$. Note that also trivially $\alpha_{n,n} = 0 = f_2-1$ and $\alpha_{n,n-1} = 1 = f_3 -1$ for all $n \ge 2$.

Now consider $\alpha_{n,k}$ for some $n \ge 2, k\in[n-2]$, so suppose we are given an $A_{n,k}$ game that needs $\alpha_{n,k}$ rounds. First, suppose the $n$-card is not present in that game (implying $k>1$). Then clearly, the last card of the initial deck will never move and we have at the worst case an $A_{n-1,k-1}$ game, and so we get $\alpha_{n,k} \le \alpha_{n-1,k-1} \le f_{n+2-k} -1$ for free. Thus, assume the $n$-card is present. If the last card of the initial deck is a $1$, we win one step after $n$ appears at the top and until then, the last card plays no role. Thus, pretending that the $n$-card is another $1$-card, this becomes an $A_{n-1,k}$ game, so $\alpha_{n,k} \le \alpha_{n-1,k} + 1 \le f_{n+1-k} \le f_{n+2-k}-1$ as $k\in [n-2]$ implies $f_{n-k} \ge f_2 = 1$. Thus, we can assume the last card is not a $1$. Once the $n$-card comes to the bottom, we clearly have an $A_{n-1,k}$ game left, so we ask how many rounds do we need to get $n$ to the top? Assuming that $n$ is not at the bottom already, we again pretend that the $n$-card is another $1$-card and since the last card plays no role until $n$ reaches the top, this becomes an $A_{n-1,k+1}$ game, since the last card is not a $1$. Thus $\alpha_{n,k} \le \alpha_{n-1,k} + \alpha_{n-1,k+1} + 1$ where the $+1$ comes from the step where $n$ goes from top to bottom. Hence $\alpha_{n,k} \le f_{n+1-k}-1 + f_{n-k}-1 + 1 = f_{n+2-k}-1$.

In particular $\alpha_{n,1} \le f_{n+1}-1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.