Friday puzzle -- another dinner club

This is one of those times...

Where the professor says "the details are left to the student" which means "I don't have a clue how to do it, but there may be a way. We will wait and see" ;-)

Re: Friday puzzle -- another dinner club

I've been kicking around a couple of possible algorithms in my head since last Friday's question. But it's been a busy week and I haven't had time to work through any of them. Maybe if things go well in the lab this morning...

Exactly! *LINK*

While the http://en.wikipedia.org/wiki/Texas_method is a legitimate method of teaching math, I had always heard (possibly apocryphal) stories about professors getting uncredited help with their research this way.

I promise not to publish results of this question without credit to WC!


More on Texas Method

Here goes...

While watching the machines do their thing in the lab this afternoon, I started thinking of this as a graph-theory problem and I think I can prove that a solution exists.

Consider the group as a graph with people represented as vertices and relationships represented as edges.

A "stranger" relationship between two vertices is represented by a red line and a 'friend' relationship by a blue line.

For a group-size of N we will have N vertices, each of which will have N-1 red edges. Since the problem defines N as odd, each vertex will be connected by an even number of red edges.

We will construct seating arrangements as a Hamiltonian circuit, following red edges to visit each vertex once and returning to the starting point.

The list of vertices visited in our circuit will be the seating plan for the night. After dessert, we will color all of the traversed edges blue.

At this point, each vertex in the graph will have exactly 2 fewer red edges (i.e. two fewer stranger relationships in the group).

As long as every vertex in the group has the same (non-zero) number of red edges, we can construct a new Hamiltonian circuit for a seating arrangement.

After seating (N-1)/2 - 1, each vertex will have exactly 2 remaining red edges. Just enough for a final seating.

Existence proof accepted

Graph theory is one (of many) hole in my math education. What you say sounds reasonable as an existence proof. But how about a constructive one? Certainly some paths could complete the circuit without touching everyone. I presume that the graph theory says it is possible to find a path that does touch everyone, which seems reasonable. But how do you find that path? E.g., how do you avoid seating someone in the 12th chair that, down the road, means that someone has to be left out?

Re: Existence proof accepted

As they say in Texas, "the implementation is left as an exercise to the reader."

Actually, I think the upshot of the proof is that there is no incorrect sequence of legal seating arrangements that precludes a complete set of introductions. Any legal seating arrangement leaves at least one other legal seating arrangement until all members have met.

No, that doesn't get you a list of tonight's place-cards, but it does simplify the algorithm design considerably. Changing the mind-set from permutation algorithms to graph-walking algorithms gives me a more straightforward approach that should be computable in LogN time.

Finding time to actually code it up is another story. We'll see how the weekend goes.

On further thought

I was a little too optimistic. I believe it is possible to make a bad choice in the sequence of seating arrangements that would effectively divide the graph into two or more sub-graphs.

These sub-graphs would each still have their own Hamiltonian circuits. It would still be possible to generate seating arrangements involving all members that would meet all other constraints but would require the members of the sub-graphs to sit at separate tables.

One could argue that they have already met all the people at the other tables, so there is no need to sit with them, but that's not the way the problem is set up.

This turns it from an N-LogN problem back into an N! problem. It may be possible to reduce the computation time with a suitably optimized path generating heuristic, but I'm not sure I could prove that one existed.

Closing in...

The first step in solving a problem such as this is constructing an appropriate model. For this problem, we needed two things: a round-table and a seating schedule.

I spent a good part of the weekend milling some walnut and roughing out parts for the round table (see photo). I still need to debug the interfaces, integrate it with the tabletop subsystem and refine the user interface a bit.

I also spent some time prototyping a seating schedule. I started with a simple recursive graph-walking algorithm, with no provisions for detecting a fragmented graph. The simple aproach actually works quite well for most cases. I tried it with odd-sized groups up to 35 members and it generated a complete set of seating schedules for all cases except N=15, 21 and 25.

The failure mode in all these cases was as predicted: the graphs were fragemented into several sub-graphs, each of which was independently solvable. Interestingly, in all three failure cases, it was able to generate full seating schedules for all but the final night.

Below is a complete seating schedule generated for a group of 23. If I get some time later in the week I'll extend the algorithm to handle graph fragmentation.

N=23:

Night 0: A B C D E F G H I J K L M N O P Q R S T U V W

Night 1: A C E G I K M O Q S U W B D F H J L N P R T V

Night 2: A D G J M P S V B E H K N Q T W C F I L O R U

Night 3: A E I M Q U B F J N R V C G K O S W D H L P T

Night 4: A F K P U C H M R W E J O T B G L Q V D I N S

Night 5: A G M S B H N T C I O U D J P V E K Q W F L R

Night 6: A H O V F M T D K R B I P W G N U E L S C J Q

Night 7: A I Q B J R C K S D L T E M U F N V G O W H P

Night 8: A J S E N W I R D M V H Q C L U G P B K T F O

Night 9: A K U H R E O B L V I S F P C M W J T G Q D N

Night 10: A L W K V J U I T H S G R F Q E P D O C N B M