perplexus.info :: General : Dinner and Dialogue

Dinner and Dialogue (Posted on 2005-11-02)

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?

Submitted by Tristan

Rating: 3.6667 (3 votes)

Solution: (Hide)

The best solution found so far has 8 members. The solution is represented in the below diagram, where each line represents a member, and the numbers at the intersections represent meetings between these members.

1-----------4-----------7--10 \\_ | / | \ \_ | / | \ \_ | / | \ \_ | / | 2----\_5------8-------11 \ |\_ / | \ | \ / | 3---6---9----------12 \ | / \_ | \ | / \_ | \|/ \_ | 0 \_ | \| 13
Proof:
Without loss of generality, assume meeting 0 has eastern food. Out of meetings 1 through 9, exactly six meetings should have western food. It follows that meetings 10, 11, and 12 all have eastern food. But then, the person who meets at 10, 11, 12, and 13 would eat at three eastern restaurants.
Note that the member meeting at 1, 5, 9, and 13 is not necessary for the proof. However, this member is necessary so that two people go to meeting 13 (since each meeting requires two or three people).
This is not a proof that 8 is the minimum number of members.

Comments: ( You must be logged in to post comments.)

Subject	Author	Date
re(2): Least number of members ?	Penny	2005-11-08 03:22:27
re: Least number of members ?	Tristan	2005-11-07 19:19:54
Least number of members ?	Penny	2005-11-05 16:28:37
Solution for the Conversing Club (computer program used)	Penny	2005-11-05 16:05:44
More First Thoughts	goFish	2005-11-05 02:08:19
re: Solution	Tristan	2005-11-05 01:36:54
Solution	Jeramie	2005-11-04 21:14:09
First thoughts	goFish	2005-11-04 06:38:31
No Subject	Tristan	2005-11-03 17:47:50

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (5)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info