9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ is Annie allowed to make this kind of modification only once on the initial line of 1, 2, 3, ..., 2016, or can she do that iteratively? $\endgroup$ – elias Apr 13 '16 at 13:49
  • $\begingroup$ @elias - iteratively, otherwise the answer would definitely be $507,528$ and generally, for $n$ cards, $\binom {\lfloor \frac n2 \rfloor}{2} \forall n\space \text{even; }\binom {\lfloor \frac n2 \rfloor}{2}+\lfloor\frac n4\rfloor \forall n\space \text{odd}$ $\endgroup$ – Jonathan Allan Apr 13 '16 at 15:07
  • $\begingroup$ - by the way that would be for exactly one modification, no less no more. $\endgroup$ – Jonathan Allan Apr 13 '16 at 15:14
  • $\begingroup$ @Jonathan Allan, I might be wrong, but I think you missed the fact, that the segment to be reserved does not have to start or finish with a face-up card, which introduces a multiplicative factor. I don't think your expression is correct for n=4, where we are starting from an UDUD-sequence, for which one possible reverse by the endpoints 1 and 3 ends in UDUD, while another possibility is with the endpoints 1 and 4, resulting in DUDU. These are considered to be two different arrangements, while your expression suggests 2 choose 2 = 1. Am I missing something? $\endgroup$ – elias Apr 13 '16 at 15:32
  • $\begingroup$ @elias That is counting arrangements distinct from each other and the original, to include such possibilities as your reversal of 1-3 just add one (the original sequence). $\endgroup$ – Jonathan Allan Apr 13 '16 at 15:37
6
+50
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ In the "We also have to show, that" section (the bit I was struggling with for many different properties including this one), we need to do some more work. Consider these two (valid and reachable) arrangements when n=12: UDDUDUUUDUDD and UDDUUDUDUUDD. The longest differing sub-sequences are DUUUD vs UDUDU (not meeting either the "one must start U and end D", or "the number of Us are even" criteria); I chose a case where it is fairly obvious we can reach one from the other (the sub-sequences are two valid sequences at n=5, where the issue first occurs - but here n is also divisible by 4). $\endgroup$ – Jonathan Allan Apr 16 '16 at 3:10
  • $\begingroup$ My proof for that part is indeed a bit bigger (if it helps, it is a constructive proof, in that I show a procedure that turns any sequence with the property into some other sequence with the property). If no one gets it by the time the bounty expires, I'll self-answer :) $\endgroup$ – ffao Apr 16 '16 at 3:47
  • $\begingroup$ great catch, @Jonathan Allan, thanks for pointing that out $\endgroup$ – elias Apr 16 '16 at 5:32
  • $\begingroup$ how about this? both of the two differing longest subsequences contain at least 2 Us (otherwise the cardinality of 'OE'-Ds do not match in them), one of them has to start with D (as they are different in that position). reverse that from that D till the second U to the right from it (this has to be inside the differing subsequence). that way we've made the differing subsequence at least one shorter, as now both of those start with U. $\endgroup$ – elias Apr 16 '16 at 5:50
  • $\begingroup$ The otherwise part needs more justification, and sounds false to me. Also, if the target sequence has a D in that position, you can't flip the target, so that needs some explaining too. This looks really close to my solution, but you're thinking too much about "longest differing subsequence", which is hard to reason about. How about "first mismatched position"? $\endgroup$ – ffao Apr 16 '16 at 15:07
5
$\begingroup$

I will put this out there, since enumeration seems to hold, although I can't quite see how it's the answer yet (i.e. what the base choices actually are that lead to this result).

2374900560376293141456553462186136331692852407693053341194431845090881037499667661716882167650216497427053837114742888075860735310016913024710396783404700935254664950606166063430929046134536699534564681273623667851713345412895920650283804495643513793381675461312621119142534166875590139481028064979873614701389678906624275674231390540832548173297869608772068352266151818836125100903346849370463859742015959947535866602512044716665325781085467249458970382066583380505267178091770321807797307742138936437968266643275715138413921308298612496540809596353779141513058515473620946661883664884035478756250880000

What is this?

Given some even number of cards, $n=p\times 2$, the number of possible arrangements Annie may produce seems to fit with $\binom{p-1}{\lfloor\frac {p-1}2 \rfloor} \binom{p}{\lfloor\frac p2 \rfloor}$.

...

For odd $n$ the number of arrangements possible is:
double the number possible with $n-1$ if $n\mod4 = 1$; or
half of the number possible with $n+1$ if $n\mod4 = 3$
(Matching elias's final result for $n<=24$).

Running some bit manipulation code the results I get for even numbers of cards are as follows
(counts of new arrangements found at each depth of Annie's choices as laid out in the question):


 n = 4 -> arrangements = 2:
 depth = 1: 1
 depth = 2: 1
 ...
 n = 6 -> arrangements = 6:
 depth = 1: 1
 depth = 2: 3
 depth = 3: 2
 ...
 n = 8 -> arrangements = 18:
 depth = 1: 1
 depth = 2: 6
 depth = 3: 9
 depth = 4: 2
 ...
 n = 10 -> arrangements = 60:
 depth = 1: 1
 depth = 2: 10
 depth = 3: 28
 depth = 4: 18
 depth = 5: 3
 ...
 n = 12 -> arrangements = 200:
 depth = 1: 1
 depth = 2: 15
 depth = 3: 66
 depth = 4: 82
 depth = 5: 33
 depth = 6: 3
 ...
 n = 14 -> arrangements = 700:
 depth = 1: 1
 depth = 2: 21
 depth = 3: 135
 depth = 4: 275
 depth = 5: 210
 depth = 6: 54
 depth = 7: 4
 ...
 n = 16 -> arrangements = 2450:
 depth = 1: 1
 depth = 2: 28
 depth = 3: 246
 depth = 4: 740
 depth = 5: 905
 depth = 6: 444
 depth = 7: 82
 depth = 8: 4
 ...
 n = 18 -> arrangements = 8820:
 depth = 1: 1
 depth = 2: 36
 depth = 3: 416
 depth = 4: 1736
 depth = 5: 3126
 depth = 6: 2500
 depth = 7: 880
 depth = 8: 120
 depth = 9: 5
 ...
 n = 20 -> arrangements = 31752:
 depth = 1: 1
 depth = 2: 45
 depth = 3: 660
 depth = 4: 3640
 depth = 5: 9030
 depth = 6: 10626
 depth = 7: 6020
 depth = 8: 1560
 depth = 9: 165
 depth = 10: 5
 ...
 n = 22 -> arrangements = 116424:
 depth = 1: 1
 depth = 2: 55
 depth = 3: 1000
 depth = 4: 7050
 depth = 5: 23100
 depth = 6: 37632
 depth = 7: 31430
 depth = 8: 13250
 depth = 9: 2675
 depth = 10: 225
 depth = 11: 6
 ...
 n = 24 -> arrangements = 426888:
 depth = 1: 1
 depth = 2: 66
 depth = 3: 1455
 depth = 4: 12750
 depth = 5: 53250
 depth = 6: 114492
 depth = 7: 131922
 depth = 8: 81780
 depth = 9: 26625
 depth = 10: 4250
 depth = 11: 291
 depth = 12: 6

$\endgroup$
  • $\begingroup$ Brute forcing small cases is a good start. I added a hint to help with proving your observation. $\endgroup$ – ffao Apr 11 '16 at 17:42
  • 2
    $\begingroup$ By the way, I think 0 choose 0 is defined as 1, so you don't need the p>1 bound. $\endgroup$ – ffao Apr 11 '16 at 17:54
  • $\begingroup$ See also: oeis.org/A005566 $\endgroup$ – Bolo Apr 11 '16 at 20:07
  • 1
    $\begingroup$ @Jonathan Allan, I'm afraid your formula is not correct for odd $n$s. see the final remark in my answer which addresses this in details $\endgroup$ – elias Apr 15 '16 at 14:12
  • 1
    $\begingroup$ @elias - yes there was a bug in how I initialised my words when n was odd (making a face down cards come first in those cases!). Matches your results now. $\endgroup$ – Jonathan Allan Apr 16 '16 at 1:43

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.