Problem

Source: Canada RepĂȘchage 2018/8

Tags: probability, combinatorics



Let $n$ and $k$ be positive integers with $1 \leq k \leq n$. A set of cards numbered $1$ to $n$ are arranged randomly in a row from left to right. A person alternates between performing the following moves: The leftmost card in the row is moved $k-1$ positions to the right while the cards in positions $2$ through $k$ are each moved one place to the left. The rightmost card in the row is moved $k-1$ positions to the left while the cards in positions $n-k+1$ through $n-1$ are each moved one place to the right. Determine the probability that after some number of moves the cards end up in order from $1$ to $n$, left to right.