Last byte

# ­Upstart Puzzles: Chair Games

View as: Print Mobile App ACM Digital Library In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook

A group of people is sitting around your dinner table with one empty chair. Each person has a name that begins with a different letter: A, B, C ... Because you love puzzles, you ask them to rearrange themselves to end up in alphabetical order in a clockwise fashion, with one empty chair just to the left of the person whose name begins with A. Each move involves one person from one chair to the empty chair k seats away in either direction. The goal is to minimize the number of such moves.

Warm-up. Suppose you start with eight people around the table, with nine chairs. The last name of each person begins with the letter shown, and you are allowed to move a person from one chair to an empty chair three chairs away in either direction (see Figure 1). Can you do it in four moves?

##### mtuacm

Maybe I'm missing something, but why can't the first example be solved in two moves?

F from 3 to 6
C from 9 to 3

I noticed that both example solutions have the people moving counter-clockwise only, but the problem says they can move in either direction. Is this just a coincidence? If counter-clockwise movement only is a requirement, then the printed solution to the first problem would be correct.

Displaying 1 comment

### Create a Web Account

If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.

### Join the ACM

Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.

### Subscribe to Communications of the ACM Magazine

Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.