Polychromatic Choreography

A certain modern dance choreographer has her dancers wear k different-colored leotards. For example, when k is 2, half the dancers wear red and the other half wear blue. In general, there are k colors with n dancers wearing each color. The basic algorithmic problem she has to solve is how to instruct her dancers to move from some given configuration to a configuration in which the dancers form disjoint vertical or horizontal line segments, with each line segment consisting of one dancer from each of the k colors in any order—a “perfect lineup.” A movement of one dancer consists of a horizontal or vertical step.

Warm-Up. Consider the following configuration of six dancers on a grid, where three wear blue leotards and three wear red leotards. Can you achieve a perfect lineup in just two moves?

Solution to Warm-Up.

and, moving vertically

Challenge. Starting with two red and two blue dancers, now add two green dancers. We want to create two disjoint segments, each with a red, blue, and green dancer in any order, constituting the perfect lineup in this case. Note the blues and reds are two spaces apart. Where should the two greens start in order to create a perfect lineup in two steps? Show those two steps.

Solution.

Here are the two steps

Upstart 1. Given an initial configurations of k colors, each with an equal number n of dancers of each color on a grid, design an algorithm that uses as few steps as possible to achieve a perfect lineup.

Upstart 2. Given k colors and n dancers of each color and a board of size B x B, find a maximally hard configuration of the dancers; a configuration c is maximally hard if c requires m parallel steps to achieve a perfect lineup and no other configuration requires more than m steps to achieve a perfect lineup.

Figure. Consider k groups of dancers, where the dancers in each group wear leotards of the same color. The choreographer’s goal is to get them to move on the grid in parallel, producing a set of disjoint line segments, each including a dancer of each color.

Upstart 3. Given a maximally hard configuration with cost m, is there any way to add a k+1^st color of n dancers to reduce the number of steps required to achieve a perfect lineup?

Upstart 4. How would these upstarts change if diagonal (and counter-diagonal) segments were allowed?

Back to Top

Back to Top