Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The requirement for "suitably shuffled" is that no $k$ cards appear in same order in $D$ and $D'$.

Elementary shuffling operations are defined, very simply, as :

  1. Interleaving. Split deck in exactly two, parts $D_{top}$, $D_{bottom}$, and place each card of $D_{bottom}$ in between cards of $D_{top}$.
  2. Cutting. Select a consecutive interval of cards $D_{cut}$, from $c_{start}$ to $c_{end}$ inclusive, (which can be from the middle of the deck) of some length less than |$D$|, and place it either on the top, or the bottom. Defined by 3-tuple ( $c_{start}$, $c_{end}$, $top$ or $bottom$ ) (Aside: there also exists an Identity. One identity operation is to select any cut from the top, and place it back on the top. ( 0, $c_{end}$, $top$ ). Which can be ignored for shuffling.)

How many such elementary shuffling operations are required to ensure the number of cards in the same order for both decks is at most $k$?, with $k$ not less than 8

share|cite|improve this question
I don't see a question (assuming that the question is not intended to be "who shuffled this deck?" :-) – joriki Feb 21 '13 at 8:39
Much better, but "such" doesn't make any sense -- you haven't introduced any at that point. Also, if you're looking for the minimal number of operations, you can eliminate the identity, since it merely makes a sequence of operations longer without changing the result. – joriki Feb 21 '13 at 8:50
Well, I'd say the "this" is now rather difficult to parse because the criterion is so far above, but perhaps that's getting too nit-picking. More importantly, what do you mean by "expected" and "on average"? I don't see any random element in the setup. In case you're thinking of the intial state of the deck as a random element, note that the fixed points of a shuffling procedure don't depend on the identity of the cards being shuffled. – joriki Feb 21 '13 at 8:53
Also, I think you should define more explicitly what you mean by fixed points of ordered but not necessarily consecutive subsequences of equal length. My interpretation of that description would be that you pick any $k$ cards from both decks (unshuffled and shuffled), preserving their order, and then count the number of matches between the two resulting ordered $k$-tuples of cards. If this is what you have in mind, note that it's unnecessarily complicated; you could equivalently demand just that no set of $k$ cards appear in the same order in both decks. – joriki Feb 21 '13 at 9:05
The question is now much more concise and easier to understand. Now you just have to remove the vestiges of the fixed points in the last paragraph :-) – joriki Feb 21 '13 at 10:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.