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?
No entries found