THE CYCLING OF PARTITIONS AND COMPOSITIONS UNDER REPEATED SHIFTS

In ''Bulgarian Solitaire,'' a player divides a deck of n cards into pi les. Each move consists of taking a card from each pile to form a sing le new pile. One is concerned only with how many piles there are of ea ch size. Starting from any division into piles, one always reaches som e cycle of partitions of n. Brandt proved that for n = 1 + 2 + ... + k , the cycle is just the single partition into piles of distinct sizes 1, 2,..., k. Let D-B(n) denote the maximum number of moves required to reach a cycle. Igusa and Etienne proved that D-B(n) less than or equa l to k(2) - k whenever n less than or equal to 1 + 2 + ... + k, and eq uality holds when n = 1 + 2 + ... +k. We present a simple new derivati on of these facts. We improve the bound to D-B(n) less than or equal t o k(2) - 2 k - 1, whenever n < 1 + 2 + ... +k with k greater than or e qual to 4. We present a lower bound for D-B(n) that is likely to be th e actual value. We introduce a new version of the game, Carolina Solit aire, in which the piles are kept in order, so we work with compositio ns rather than partitions. Many analogous results can be obtained, (C) 1998 Academic Press.