Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For an explanation of what Bulgarian Solitaire is, look here.

I have worked out the full graphs for $1 \leq \text{number of cards} \leq 13$ in the past, and all of them had just one root loop...except for $8$ cards. In that case, there are two root loops, one of which is $(4,2,2) \to (3,3,1,1)$ (which is also the entire subgraph for that loop). So, here we have a loop of size $2$ and a loop of size $4$. Unlike my previous question, I have no good intuition as to why this is the case.

Which numbers have multiple root loops? How many do they have?
share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

In Jyrki’s notation that’s the cycle from $(4,3^*,2,1^*) = (4,2,2)$ to $(4^*,3,2^*,1) = (3,3,1,1)$ and back. Here $n = 8 = T_4 - 2$, and the decrement $2$ divides $4$. In general, suppose that $n = T_k - m$, where $0<m<k$, and suppose that $m|k$. If $p=k/m$, you’ll have a cycle of length $p$ starting with $$\left(k^*,k-1,k-2,\dots,((m-1)p)^*,(m-1)p-1,\dots,p^*,p-1,\dots,2,1\right),$$ the position in which each of the $m$ multiples of $p$ is starred. The next two values of $n$ for which you’ll get a second cycle are $18 = T_6 - 3$ and $19 = T_6 - 2$; the ‘extra’ cycles for these $n$ are $$(6^*,5,4^*,3,2^*,1) = (5,5,3,3,1,1)$$ $$(6,5^*,4,3^*,2,1^*) = (6,4,4,2,2)$$ and $$(6^*,5,4,3^*,2,1) = (5,5,4,2,2,1)$$ $$(6,5^*,4,3,2^*,1) = (6,4,4,3,1,1)$$ $$(6,5,4^*,3,2,1^*) = (6,5,3,3,2)$$ respectively.

share|improve this answer
add comment

The Bulgarian Solitaire state diagram for $S$ has a single cycle (or fixed point) if and only if $S$ is within 1 of a triangular number. In addition to 18 & 19 mentioned before, the diagram for 17 has two components.

The number of components was given by Brandt in 1982, the first English language publication on the topic (although it does not mention the name, which was popularized by Martin Gardner). Using his notation, write $S = \binom{n+1}{2} - a$ with $0 \leq a \leq n-1$. The number of cycles for Bulgarian Solitaire on $S$ is

$$ \frac{1}{n} \sum_{d|(n,a)} \varphi(d) \binom{n/d}{a/d}$$

where $(n,a)$ denotes the greatest common divisor and $\varphi(d)$ is the Euler totient function. The length of the cycle for each $d$ is $(n+1)/d$.

Some articles on this are freely available, for instance in the Electronic Journal of Combinatorics. If you have access to the College Mathematics Journal (perhaps through JSTOR), there was a survey article in March 2012.

share|improve this answer
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.