In a stack of n distinct cards in order {1,2,3,4,...,n} from top, define distance between 2 cards as the number of cards between them. 2 cards are neighbours if they're adjacent in original stack, if their index differs by 1.
How many card rearrangements (permutations) satisfy the following?
I) The sum of distances between any card and its neighbour/s (call that sum $S_n$ for card $n$), is distinct for all $n$ cards.
II) $S_n$ is distinct for all $n$ and only take on values smaller than $n$.
Edit 1: an example makes the conditions clearer.
Say we have 3 cards in original stack in order 1,2,3 from top. Rearrange cards into order 2,3,1 from top. Then:
Card 1 is distance 1 from its former neighbour card 2. $S_1$=1
Card 2 is distance 1 to card 1 but distance 0 to card 3. $S_2$=1+0=1
Card 3 is distance 0 from card 2. $S_3$=0
Hence this reordering/shuffle does not satisfy the conditions in the question, as both $S_1$ and $S_2$ are 1.
Edit 2: JLee and LaBird kindly wrote programs to generate data(thanks so much!). Using the data I did a quick plot to guess possible relationships between n and the ratio of permutations satisfying condition 1 in respect to the total number of permutations of length n. This is a less than scientific approach, but in the spirit of contribution, i hope this can 'trigger' ways to solve the problem.
Brief comment: It appears that the slope of the log plot is stabilising to around -1/2, though this is a pure guess without more data.
My attempt: I made a list of basic observations, trying to link this problem to known methods, but to little success.
i) Let original order of cards be 1,2,3,4…..,n for simplicity from top of stack . After the order of the cards are randomized, the distance between cards 2 and 3 will contribute to both S2 and S3, as they were neighbours before.
ii) The question is analogous to a frog making n-1 leaps on a 1*n board, labelled 1,2,3,4…..n from left to right. Starting on the square representing the new position of card 1, the frog makes leaps so that on the mth turn, the it is on the square representing the new position of the mth card. The restrictions are that every square must be covered exactly once and the magnitude of the first and last leaps, and the sum of the magnitudes of any 2 consecutive leaps must be distinct.
iii) Cards 1 and n have only 1 neighbour, so after rearranging, S1 and Sn are the distances between card 1 and its former neighbour and card n and its former neighbour, respectively.
iv) In part i) Sn can take on any value from 0 to 2n-5. If a card k stays adjacent to its neighbours, then Sk=0. If Sn>n-3 for some n, then we can deduce that the former neighbouring cards are now both above or both below card n Sn reaches a maximum value of 2n-5 when a card is on the bottom of the deck and its two former neighbours at the top of the deck. Only n of those values need to be used so n-4 will remain unused.
v) For part ii), Sn can take on only values from 0 to n-1. Hence every value must be taken once. This means exactly one card k must remain next to all of its former neighbors in the new arrangement. This is done so Sk can take on the value 0. I’m not sure if such an arrangement is even possible.
vi) At n=4, there are exactly 4 possible values for Sn : (0,1,2,3). For every greater value of n, the possible values of Sn exceeds n.
Are there existing strategies to analyze/tackle problems like this? Can this problem be solved for small n like n=5?
thanks as always
This is not a full answer, but I hope this answer can trigger some thoughts for better answers.
There are two observations I've made:
(1) The number of permutations that satisfy the conditions must be an even number (including $0$). The reason is by symmetry. If ($X_1, X_2, X_3, \dots, X_{n-2}, X_{n-1}, X_n$) is an answer, then ($X_n, X_{n-1}, X_{n-2}, \dots, X_3, X_2, X_1$) must also be an answer.
(2) For $n = 4p+2$ or $n = 4p+3$ where $p$ is an non-negative integer, there will be no solution. The reason is that $\sum S_i$ must be an even number, since when card $x$ is having a distance of $d$ from its former neighbor $y$, $y$ is also having the same distance $d$ from $x$. And this distance $d$ is counted twice -- once inside $S_x$ and once inside $S_y$. Therefore $\sum S_i$ must be an even number. However, condition (II) of the question requires that $\sum S_i = \sum_{i=0}^{N-1}$. This number is odd when $n = 4p+2$ or $n = 4p+3$ (i.e. $n = 2, 3, 6, 7, 10, 11, \dots$). Hence there will be no solution.
Surely, this does not explain why $n = 5$ has no solution (according to my brute-force attempt using a computer program), and how to find the number of permutations that satisfy the condition when $n = 4p$ or $n = 4p+1$.
Added the following after reading the comments from OP:
(1) In fact, we can make a stronger claim that the number of permutations that satisfy the conditions must be a multiple of $4$ (including $0$). The reason is as follows:
If ($X_1, X_2, X_3, \dots, X_{n-2}, X_{n-1}, X_n$) is an answer (call it [a]), then ($X_n, X_{n-1}, X_{n-2}, \dots, X_3, X_2, X_1$) must also be an answer (call it [b]) according to symmetry.
Also, if [a] is an answer, ($n+1-X_1, n+1-X_2, n+1-X_3, \dots, n+1-X_{n-2}, n+1-X_{n-1}, n+1-X_n$) is an answer too (call it [c]). In this case, if we express every $S_i$ in [a] and [c] as two sequences, these two sequence will be exactly the reverse of each other. An example is when $n=4$, as ($1, 3, 4, 2$) is an answer, ($4, 2, 1, 3$) is also an answer (just replacing $i$ as $n+1-i$).
So, if [c] is an answer, then ($n+1-X_n, n+1-X_{n-1}, n+1-X_{n-2}, \dots, n+1-X_3, n+1-X_2, n+1-X_1$) is an answer too (call it [d]), by symmetry to [c].
Now, the only thing we need to prove is that we won't double count the same permutation twice or more. For the above $4$ answers, it may happen that [a] is actually the same permutation as [d], or [b] is actually the same permutation as [c]. This happens when $X_i + X_{n+1-i} = n-1$ for every $i \in [1,n]$. But in such case, the answer will NOT satisfy condition II. The proof is as follows:
If $X_i + X_{n+1-i} = n-1$ for every $i \in [1,n]$, this means when card $1$ is at position $j$ (assume the first card is denoted as position $1$), card $n$ is at position $n+1-j$. Similarly, when card $2$ is at position $k$, card $n-1$ is at position $n+1-k$. Now consider the sum $S_1$, which is actually the distance between card $1$ and card $2$, hence $S_1 = |j-k|-1$. Next, consider the sum $S_n$, which is actually, the distance between card $n$ and card $n-1$, hence $S_n = |(n+1-j)-(n+1-k)|-1 = |j-k|-1$ ($n+1$ must be larger than $j$ and $k$). As $S_1 = S_n$, the solution does not satisfy condition I or II. This applies to any of the $4$ solutions [a], [b], [c] and [d], as long as [a]=[d] or [b]=[c]. So we can safely claim that there is no double-counting, hence the number of permutations that satisfy both conditions must be a multiple of $4$.