0
$\begingroup$

Is this question well posed? If not, can you improve it? If so, what is the solution?

I am holding a dinner party for 12 people. Their names are A, B,...L. The seats are numbered: 1, 2, ... 12. The people are sitting at a circular table.

They start off being seated as follows: A is in seat 1, B is in seat 2, ... L is in seat 12. This is denoted a follows: A->1; B->2;...;L->12.

Notice that in this arrangement A is sitting next to B and L.

The people will switch seats twice during the dinner. So they can sit next to a total of 6 different people.

Provide two seatings that will maximize the number of people a person sits next to.

Improve this question
New contributor
user128807 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
2
  • 1
    $\begingroup$ The question is clear enough, though likely to get closed as it is just a specific computation which a computer can do quickly. Here is one solution. The first seating is to seat them in order $(0,1,2,3,4,5,6,7,8,9,10,11)$. The second seating is $( 0,5,10,3,8,1,6,11,4,9,14,7 )$; i.e., every person sits next to the person who was 5 steps away from them in the previous seating. And the third seating is $(0,2,4,6,8,10,1,5,7,11,3,9,0)$. I found this by using the FindHamiltonianCycle[] command in Mathematica to find a cycle in the graph of permissible partners. $\endgroup$
    – David E Speyer
    Commented 2 hours ago
  • 1
    $\begingroup$ More generally, if $n=2r+1$, then you can have $r$ seatings such that everyone is next to all $2r$ guests, see en.wikipedia.org/wiki/Hamiltonian_decomposition#Complete_graphs for the solution. I haven't found a reference for the even case yet. $\endgroup$
    – David E Speyer
    Commented 2 hours ago

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .