Opinion
Computing Applications Last byte

Upstart Puzzles: Take Your Seats

Posted
  1. Article
  2. Author
  3. Footnotes
  4. Figures
Take Your Seats, Figure 2

A popular logic game involves figuring out an arrangement of people sitting around a circular table based on hints about, say, their relationships. Here, we aim to determine the smallest number of hints sufficient to specify an arrangement unambiguously. For example, suppose we must seat Alice, Bob, Carol, Sybil, Ted, and Zoe. If we are allowed hints only of the form X is one to the right of Y, it would seem four hints are necessary. But suppose we can include hints that still refer to two people, or “binary hints,” but in which X can be farther away from Y.

Suppose we have just three hints for the six people: Ted is two seats to the right of Carol; Sybil is two to the right of Zoe; and Bob is three to the right of Ted (see Figure 1 for this table arrangement). We see that we need only three hints to “fix” the relative locations of six people.

However, if we now bring Jack and Jill into the picture, for a total of eight people, then we might ask how many binary hints we would need to fix the arrangement. Consider these five hints: Carol is three seats to the right of Jill; Alice is six to the right of Bob; Ted is four to the right of Zoe; Jill is six to the right of Zoe; and Carol is six to the right of Sybil. What arrangement would these hints produce?

Solution. Alice, Jill, Bob, Zoe, Carol, Jack, Sybil, and Ted. So we used five hints to fix the arrangement of eight people around a circular table.

Getting even more ambitious, suppose we add Christophe and Marie, giving us 10 people, and want the ordering to be like this: Christophe, Jack, Jill, Bob, Marie, Carol, Ted, Zoe, Alice, and Sybil (see Figure 2). Can you formulate seven hints that will fix this arrangement? Can you do it with fewer than seven? Here is one solution using seven hints: Alice is seven seats to the right of Jack; Jack is nine to the right of Jill; Christophe is seven to the right of Bob; Christophe is six to the right of Marie; Bob is eight to the right of Carol; Ted is eight to the right of Alice; and Ted is seven to the right of Sybil.

Here are the upstart challenges, easier, I suspect, than the upstart challenge from my last (Nov. 2014) or next (May 2015) column: Is there an algorithm for finding n–3 binary hints to fix an arrangement of n people around a table for n of at least six? Is that algorithm “tight,” so it is impossible to do better?

Solutions to this and to other upstart challenges are at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html.

Back to Top

Back to Top

Back to Top

Figures

F1 Figure 1. Seating arrangement specified by the hints.

F2 Figure 2. Find seven binary hints that will fix this arrangement.

Back to top

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More