Communications of the ACM

Last byte

Upstart Puzzles: Take Your Seats

By Dennis Shasha
Communications of the ACM, February 2015, Vol. 58 No. 2, Page 104
10.1145/2699303
Comments

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

Back to top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2015 ACM, Inc.

---

No entries found