This is a follow up to Arranging a long line of cards:
Annie has a very long line of cards, numbered from 1 to 2016, such that every odd card is face-up and every even card is face-down. The only way she can modify the line is by taking any segment of consecutive cards that has an even number of face-up cards and reversing the order of the cards in this segment (note that none of the cards are flipped). She can make modifications as many times as she wants.
Annie was sad after BaSzAt used a parity argument to convince her that it was impossible to have all face-up cards be next to each other. But, as they say, one door closes, many others open. Make Annie happy again by showing her how many different arrangements she can make with the line of cards.
Note: Two arrangements are considered distinct if a position contains a face-up card in one and a face-down card in another. That is to say, all face-up cards and face-down cards are indistinguishable.
The main observation for this puzzle was taken from a problem from the XVI Open Team Programming Collegiate Cup.
Hint 1:
Try finding a property Annie's moves cannot change. That property should be common to all reachable arrangements.
Strong Hint 2:
You already know parity matters. If you make pairs using the face-up cards, you should be able to classify the face-down cards into two groups. Then count the size of each group.
Answer
Based on both hints, and using the results of @Jonathan Allan's answer, I think I finally got an answer in the general form of
$\binom{\frac{n}2-1}{\frac{n}4}\cdot\binom{\frac{n}2}{\frac{n}4}$, where $n$ is the number of cards, divisible by $4$.
For $n=2016$ this gives $\binom{1007}{504}\cdot\binom{1008}{504}$, which equals the huge number suggested by @Jonathan Allan.
I haven't tried to generalize the formula for $n$s which don't have a factor of $4$. My reasoning below uses some ideas which need that the number of face-up cards, which is $\lceil n/2 \rceil$, to be even. Fortunately - and probably not at all accidentally - the actual case of $n=2016$ satisfies this comfortable condition. Even better, in this case $n/2$ is integer itself, no need for the ceiling.
Short explanation:
Divide the face-down cards in two groups according to if they have a total number of even or odd face-up cards in the line to the left of them.
With Annies moves, the cardinality of these groups does not change, and if two card-permutation have the same cardinalities, they can be reached with an iteration of valid reversals.
Thus the answer is how many permutations of $n/2=1008$ identical face-up and $n/2=1008$ identical face-down cards are there where $n/4=504$ face-down cards have an even number of face-up cards to the left of them, and $n/4=504$ have an odd number of these, just as in the initial setup of the alternating sequence of face-up, face-down cards.
Detailed explanation:
The second hint almost gives away
where to look for the solution: it was a natural idea to divide the face-up cards in two groups, by turns based on the natural order they appear, so every oddth face-up card is in one group, and the eventh face-up cards are in the other. If there are $n$ cards in total, we have $n/2$ face-up cards, now divided in two groups of $n/4$.
For a better understanding, let me mark face-down cards with '-', an oddth face-up card with 'O', and an eventh face-up card with 'E'. With this notation the original setup of the $2016$ cards looks like
O-E-O-E-O-E-...O-E-
Furthermore, generally any setup of the $n$ cards - even the ones which cannot be reached from the original setup - consists of $n/2$ '-'s, and $n/4$ 'O's and $n/4$ 'E's. In valid setups 'O's and 'E's follow each other by turns, starting with an 'O'. For example the following is a valid setup for $n=12$:
--O-E--OEO-E
(Please note, that after a reversal, the 'O's and 'E's need to be fixed, that is, after reversing the sequence from the second to the ninth card in the above setup does not lead to -EO--E-O-O-E , but to -OE--O-E-O-E .)
So what happens during a reversal? At this point, it is important to notice, that
the original condition of having an even number of face-up cards in the sequence to be reversed means, that if and only if the beginning of the sequence to be reserved is after an oddth face-up card, but before its consecutive eventh face-up card, then the end of the sequence will fall also after an oddth and before the next eventh one. That is, if I mark the start and end of the sequence to be reversed with '|', either both '|'s are between an 'O' and its following 'E' (and maybe some '-'s which we can ignore now), or both are between an 'E' and its following 'O' (minor remark: or it can be the special case of being before the first 'O' or after the last 'E', but these cases behave totally regularly as well, no trick needed).
So it either looks like something like this:
-OE--O|-EO-E-O--|E
or this:
-|OE--O-EO-E-|O--E
We will come back to this soon, but have to do a short intermission.
The first hint strengthened my impression, that
this is a typical problem which involves finding conservative quantities. Let's focus on the number of '-'s, and let's divide those in two groups too.
Some of those are in between an 'O' and the next 'E', while others fall after an 'E' but before its consecutive 'O' (or again, are at the very beginning/end of the line). Let these be our two groups, which I will refer to as "being in an 'OE'-sequence" and "being in an 'EO'-sequence", respectively. How do the cardinalities of these groups change during a reversal?
They don't! (Hooray!)
That's easier to understand if you now look back at the two chosen sequences in the previous paragraph, and realize, that '-'s which were in an 'OE'-sequence, will be in an 'OE' sequence after the reversal too, as the parity of the last face-up card in the sequence to be reversed is the same as the parity of the last face-up card before the sequence, and so on.
We also have to show, that
two setups which have the same number of face-down cards being in an 'OE'-sequence (and the same number of face-down cards being in an 'EO'-sequence, and the same number of face-up cards) can be actually reached from each other by legal moves of Annie.
I need to add here, that because of the invertibility of the reversing it does not really matter which setup is the one we are trying to reach from the other one. If there is a setup $C$ which we can reach from both $A$ and $B$, then $B$ can be reached from $A$ as well, with the sequence of reversals leading from $A$ to $C$, and the reversed sequence of reversals leading from $B$ to $C$.
Let's consider two setups, which are both valid, having the same number of these 'OE'-sequence face-down cards, but are not identical. This latter means that there is at least one position, in which one of them has a face-up card, and the other has a face-down card. Let's look at the leftmost of these positions.
The setup with the face-down card in this position has to have at least two face-up cards to the right from this position, otherwise the two setups could not have the same amount of face-down cards being in an 'OE'-sequence.
So we can reverse this setup at the sequence starting from the face-down card being at the leftmost difference's position, and ending at the second face-up card to the right from there.
After the reversal we get a setup which will also have a face-up card in the position where there was a difference before (because of the face-down card being there), so we managed to resolve the leftmost difference without changing anything to the left of it. Thus if there is still a difference between the newly-got and the other setup, it has to be in a position which is to the right from this previous difference. As the length of the setups is finite, repeating this iteratively, we will actually end up having the same setups using valid moves.
So there is only the enumeration left.
In the setup which Annie starts from (O-E-O-E-...O-E-), there are just as many '-'s in 'OE'-sequences as in 'EO'-sequences, both $n/4=504$.
There are also $n/4=504$ 'O's followed by an 'E', that is, $n/4=504$ places to put '-'s into an 'OE' sequence.
The number of 'E's followed by an 'O' is $n/4-1=503$, but a '-' is in an 'EO'-sequence also at the very beginning or at the very end of the line, so that means $n/4-1+2=n/4+1=505$ possible places.
Because of these placements can be made independently of each other, the number of all the matching configuration can be calculated by multiplicating the two combinations with repetitions: $\binom{\frac{n}{4}+\frac{n}{4}-1}{\frac{n}{4}}\cdot\binom{(\frac{n}{4}+1)+\frac{n}{4}-1}{\frac{n}{4}}=\binom{1007}{504}\cdot\binom{1008}{504}$
EDIT: Solution for every $n$
How does the number of face-up and face-down cards, the parity of the former, the cardinality of the groups of the latter, and thus the expression change when $n$ is not divisible by $4$?
I think all the reasoning still holds, the only difference is, that $n/4$ is not an integer.
The number of face-up cards is $\lceil \frac{n}{2} \rceil$;
they always start with the first (an oddth one), so the number of oddth face-up cards is $\lceil \frac{n}{4} \rceil$,
while the number of eventh face-up cards is $\lceil \frac{n-2}{4} \rceil$.
The number of face-down cards in the default setup is $\lceil \frac{n-1}{2} \rceil$;
$\lceil \frac{n-1}{4} \rceil$ of them being in an 'OE'-sequence,
and the rest $\lceil \frac{n-3}{4} \rceil$ being in an 'EO'-sequence.
The former can be rearranged after any of the 'O's, that's $\lceil \frac{n}{4} \rceil$ possible positions,
while the others can be put after every 'E', or to the very beginning, giving $\lceil \frac{n-2}{4}+1 \rceil$ possibilities.
The final formula changes to $\binom{\lceil \frac{n}{4} \rceil + \lceil \frac{n-1}{4} \rceil - 1}{\lceil \frac{n-1}{4} \rceil}\cdot\binom{\lceil \frac{n-2}{4}+1 \rceil + \lceil \frac{n-3}{4} \rceil - 1}{\lceil \frac{n-3}{4} \rceil}$.
Notice that the generic formula
matches @Jonathan Allan's brute force calculations for even $n$s, and also supports his idea for $n$s which have a remainder of $3$ divided by $4$: for those $f(n)=f(n+1)/2$.
However, for $n$s which are $1$ modulo $4$: $f(n)=f(n-1)\cdot2$ seems to hold.
A counterexample for his calculation is $n=5$, where $f(n)=4$ (instead of $3$), and the reachable setups are UDUDU, DUDUU, UUDUD, and DUUUD
No comments:
Post a Comment