The Dinner and Dialogue Club has planned a series of small meetings. Each meeting would consist of two or three members enjoying friendly conversation with each other while eating food from different places all over the world. Each member is scheduled to meet exactly four times. No pair of members will meet twice, but some pairs might not meet at all.

The first thing the club did was schedule and arrange the meetings so that each member knew whom to meet and when. When it came to choosing restaurants, someone suggested that each member eat at two restaurants with eastern food, and two with western food (each restaurant is either one or the other). They liked the idea, but to their dismay, the idea was not possible without rearranging at least some of the meetings.

What possible meeting schedule might cause this to happen? How many members are there in this club, at the least?

Having trouble understanding?  Consider this simpler problem, and its solution.

Let's say that instead of four meetings, each member attends exactly two meetings.  Member A goes to meeting 1 and 2; member B goes to meeting 2 and 3; member C goes to meeting 3 and 1.

Suppose someone suggested that each member eat at one eastern restaurant, and one western restaurant.  This would be impossible, no matter where the meetings take place.  For example, if meeting 1 was at an eastern restaurant, 2 and 3 must be at western restaurants, but then member B would be going to two western restaurants.

Now try and find a schedule in which each member attends 4 meetings, and where it is impossible for each member to attend two western and two eastern restaurants.

Don't bother trying to prove that there is no solution, because there is in fact a solution.

Posted by Tristan on 2005-11-03 17:47:50