Sunday, December 14, 2008

Mathematician at work.

Some friends gave me a puzzler I have been working on for about a week. You may find it challenging, maybe it will just make your brain hurt. For me, it's fun, and I can use it to give a little insight into how some mathematicians work.

Let's say you have 36 people at a seven day conference. Every evening at dinner, the group is split into six tables of six. Is it possible to arrange the seating so that every person is at a table with every other person on one and only one evening?


The case for 36 is a tough problem and I haven't solved it yet. What I have done is look at similar problems with less people. Consider if we only had 9 people at the conference, and every evening they were split into three tables of three each. Any given person at the conference has eight colleagues and every evening that person will have two dinner companions, so if the problem is solvable, we will need four evenings of three tables of three people each to have every one have dinner with everybody else.

This drawing is the complete graph on nine vertices, known to mathematicians as K9. The mathematical way to ask the question is this: can the edges of K9 be decomposed into twelve distinct copies of K3? K3 is the complete graph on three vertices, also known as a triangle, or to graph theorists as a 3-cycle.


The answer for this simpler problem is yes and the drawing here shows how. If we label the vertices 1 through 9, starting at the top and going clockwise, here are the lists of people at the tables each evening.

Evening #1: 123::456::789 (drawn in red)
Evening #2: 147::258::369 (drawn in green)
Evening #3: 159::267::348 (drawn in blue)
Evening #4: 168::249::357 (drawn in pink)

Notice how all the triangle shapes in any single color are identical to one another, just rotated to cover different vertices. I've also solved the problem of 16 people at tables of 4 over five nights, and in the solution I found, we don't have that nice symmetry on every evening.

This way of working is fairly common among mathematicians, exploring smaller versions of a problem and trying to find a pattern that can be turned into a method for solving larger versions. Sometimes, the method breaks down, and there is a largest version of the problem that can be solved, and all larger versions are impossible. As it currently stands, I have no idea if the problem of 36 people at 6 tables can be solved or not. For people who really love math, that actually makes it more fun.

2 comments:

FranIAm said...

I love you but the maths... I am just not so sure yet.

Matty Boy said...

Hi, Fran. I am well aware that I have readers who like the maths and others who merely tolerate it. What I like about this problem is that it is so easy to state and so challenging to solve. That happens a lot in math.