Decision Support Puzzles for Applied Mathematicians
February 2011 - Best Host
Serving as host for dinner requires several skills to pull off a successful evening. One of your duties, aside from preparing dinner and selecting the drinks, is to make sure your guests enjoy themselves.
Image 1 shows a dinner table with 6 seats for your guests. Some guests, however, do not get along with each other. If two guests who do not get along are seated next to each other, it will create conflict at dinner. As host, you must arrange the guests in a seating order that minimizes conflict.
Andrew will only sit next to Dave and Frank; Betty will only sit next to Cara and Erica; Cara will only sit next to Betty and Frank; Dave will only sit next to Andrew and Erica; Erica will only sit next to Betty and Dave; Frank will only sit next to Andrew and Cara. In the example seating arrangement above, there are 3 conflicts (Andrew and Betty, Cara and Dave, Erica and Frank).
Question: What seating arrangement will minimize the conflict at dinner?